数据结构是指逻辑意义上的数据组织方式及其相应的处理方式. (1) 什么是逻辑意义? 数据结构的抽象表达非常丰富,而实际物理存储的方式相对单一. 比如, 二叉树在磁盘中的存储真的是树形排序吗? (2) 什么是数据组织方式? 逻辑意义上的组织方式有很多,比如树, 图, 队列, 哈希等. 树可以是二叉树, 三叉树, B+树等; 图可以是有向图或无向图; 队列是先进先出的线性结构; 哈希是根据某种算法直接定位的数据组织方式. (3) 什么是数据处理方式? 在既定的数据组织方式上,以某种特定的算法实现数据的增加, 删除, 修改, 查找和遍历. 不同的数据处理方式往往存在着非常大的性能差异.
数据结构是算法实现的基石, 它是一种体现基础逻辑思维的内功心法, 也是计算机从业人员能力图谱中的重要一项.
从直接前趋和直接后继个数的维度来看, 大体可以将数据结构分为以下四类:
(1) 线性结构: 0至1个直接前趋和直接后继, 当线性结构非空时,有唯一的首元素和尾元素, 除两者外, 所有的元素都有唯一的直接前趋和直接后继. 线性结构包括 顺序表, 链表, 栈 , 队列等; 其中栈和队列是访问受限的结构. 栈是后进先出, 即Last-In, First-Out, 简称 LIFO; 队列是先进先出, 即 First-In,First-Out,简称 FIFO .
(2) 树结构 0至1个直接前趋和0至n 个直接后继(n大于或等于2) . 树是一种非常重要的有层次的非线性数据结构, 像自然界的树一样. 由于树结构比较稳定和均衡,在计算机领域中得到广泛应用.
(3) 图结构 0至n 个直接前趋和直接后继(n大于或等于2). 图结构包括简单图, 多重图, 有向图和无向图等.
(4) 哈希结构 没有直接前趋和直接后继. 哈希结构通过某种特定的哈希函数将索引与存储的值关联起来,它是一种查找效率非常高的数据结构.
不同的数据组织方式和处理方式带来了一个新的问题: 如何衡量数据处理的性能? 数据结构的复杂度分为空间复杂度和时间复杂度两种. 在存储设备越来越便宜的情况下, 时间复杂度成为了重点考量的因素. 算法时间复杂度是一种衡量计算性能的指标, 反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能够反映出算法性能的优劣与否. 而这个量级通常用大写的 O 和一个函数描述, 如 O(n^3)表示程序执行时间随输入规模呈现三次方倍的增长, 这是比较差的算法实现. 从最好到最坏的常用算法复杂度排序如下: 常数级O(1), 对数级O(log n), 线性级O(n), 线性对数级O(nlog n), 平方级O(n^2), 立方级O(n^3) , 指数级O(2^n)等.
数据结构的各种类型没有好坏之分,它只有与场景, 数据量结合起来综合考虑, 才有实际的意义. 场景包括操作类型及其频率, 数据量的大小决定它选择什么样的数据结构类型. 到底是写为主, 还是读为主,或者说读写均衡. 其中写是以插入为主, 还是删除为主; 读是以遍历为主, 还是查询单个元素为主. 数据量的不同也会决定不同的数据结构的使用效率, 比如ConcurrentHashMap, 根据不同的数据量选择用链表或者 红黑树存储.
