数据结构 | 常见的数据结构是怎样的？

本文简单总结数据结构的概念及常见的数据结构种类 ¹’ ²。

更新：2023 / 04 / 05

可供借鉴的书籍及课程等可参考此处。

总览

概念

数据 是存储在计算机的 内存 里的，在存储时，决定了 数据 顺序和位置关系的便是 数据结构。
数据结构 是 数据 按照特点关系进行存储或者组织的集合。特殊的结构在不同的应用场景中往往会带来不一样的处理效率 ¹。

举一个生活中的例子来说明 数据结构 的概念的话，也就是存手机号码 ²。
在手机没有出现之前我们存电话号码都是在笔记本上手抄，这样每次新记一个电话号码都是在最后一行后面加，然后找的时候就需要在所有的号码中找某一个，查找很不方便。
后来当有了手机之后，每次添加一个新联系人时，系统会根据你的存的人名的姓氏拼音首字母自动加到姓氏那一组，当你要查找某一个人的时候，你可以搜索，也可以直接点击右边的首字母去查找，效率大大提高。
电话号码存在笔记本或者存在手机上，这种存储结构的顺序和位置关系就是 数据结构。选择合适的 数据结构，不但可以提高 内存 的使用率，也可以提高 查找 的效率。查找效率 就是指 算法，数据结构 是为 算法 而生。

分类

数据结构 分为 逻辑结构 和 物理结构。

• 逻辑结构
  指 数据元素 之间 逻辑关系 的 数据结构，这里的 逻辑关系 是指 数据元素 之间的前后间关系，与数据在计算机中的 存储位置 无关。
• 物理结构
  指 数据 的 逻辑结构 在计算机存储空间中的存放形式称为 数据 的 物理结构，也叫做 存储结构。

数据 的 逻辑结构 主要分为 线性结构 和 非线性结构。

• 线性结构
数据结构 的元素之间存在 一对一 线性关系，所有结点都最多只有一个直接前趋结点和一个直接后继结点。
  常见的有 数组、队列、链表、栈。
• 非线性结构
  各个结点之间具有多个对应关系，一个结点可能有多个直接前趋结点和多个直接后继结点。
  常见的有 多维数组、广义表、树 结构和 图 结构等。

数据 的 物理结构（ 或称 存储结构 ），表示 数据 元素之间的逻辑关系，一种 数据结构 的逻辑结构根据需要可以表示成多种存储结构，常用的 存储结构 有：

• 顺序存储
存储顺序 是连续的，在 内存 中用一组地址连续的存储单元依次存储 线性表 的各个数据元素。
• 链式存储
  在 内存 中的存储元素不一定是连续的，用任意地址的存储单元存储元素，元素节点存放数据元素以及通过指针指向相邻元素的地址信息。
• 索引存储
  除建立存储结点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。
• 散列存储
  又称 Hash存储，由节点的关键码值决定节点的存储地址。

常用的数据结构

数据结构 种类繁多，下面将通过图解的方式对常用的数据结构进行理论上的介绍和讲解，以方便大家掌握常用数据结构的基本知识。

数组

数组 可以说是最基本最常见的数据结构。

数组 是一种线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据，可通过 数组 名和下标进行数据的访问和更新。数组 中元素的存储是按照先后顺序进行的，同时在内存中也是按照这个顺序进行连续存放。数组 相邻元素之间的内存地址的间隔一般就是数组数据类型的大小。

如上图所示，数据是按照顺序存储在内存的连续空间内，arr 后面的 [] 代表下标。由于数据是存储在连续空间内的，所以每个数据的内存地址（在内存上的位置）都可以通过数组下标计算出来，从而可以直接访问目标数据，达到随机访问的目的。

链表

链表 是一种物理存储单元上非连接、非顺序的存储结构。

链表 由一系列节点组成，所谓节点是指列表中的每一个元素，每个节点包含两个数据，一个是存储元素的数据域（值），另一个是存储下一个节点地址的指针域。

由于是通过指针进行下一个数据元素的查找和访问，使得 链表 的自由度更高。
这表现在对节点进行增加和删除时，只需要对上一节点的指针地址进行修改，而无需变动其它的节点。不过事物皆有两极，指针带来高自由度的同时，自然会牺牲数据查找的效率和多余空间的使用。

一般常见的是有头有尾的 单链表，对 指针域 进行 反向链接，还可以形成 双向链表 或者 循环链表 。

通俗点说，链表 数据一般都是分散存储在内存中的， 无须存储在连续空间中。可以根据下图来感受链表

链表和数组对比

链表 和 数组 在实际的使用过程中需要根据自身的优劣势进行选择。链表 和 数组 的异同点也是面试中高频的考察点之一。这里对 单链表 和 数组 的区别进行了对比和总结。

跳表

从上面的对比中可以看出，链表 虽然通过增加指针域提升了自由度，但是却导致数据的查询效率恶化。特别是当 链表 长度很长的时候，对数据的查询还得从头依次查询，这样的效率会更低。

跳表 的产生就是为了解决 链表 过长的问题，通过增加 链表 的 多级索引 来加快 原始链表 的查询效率。这样的方式可以让查询的时间复杂度从 O(n) 提升至 O(logn) 。

跳表 通过增加的 多级索引 能够实现高效的动态 插入 和 删除，其效率和 红黑树 和 平衡二叉树 不相上下。目前 redis 和 levelDB 都有用到 跳表。

从上图可以看出，索引级的指针域除了指向下一个索引位置的指针，还有一个 down 指针指向低一级的 链表 位置，这样才能实现跳跃查询的目的。

栈

栈 是一种比较简单的数据结构，常用一句话描述其特性，后进先出。栈 本身是一个 线性表，但是在这个表中只有一个口子允许数据的进出。这种模式可以参考 腔肠动物，即进食和排泄都用一个口。

栈 的常用操作包括 入栈push 和 出栈pop，对应于数据的 压入 和 压出。还有访问栈顶数据、判断栈是否为空和判断栈的大小等。由于栈后进先出的特性，常可以作为数据操作的临时容器，对数据的顺序进行调控，与其它数据结构相结合可获得许多灵活的处理。

队列

队列 是 栈 的兄弟结构，与 栈 的后进先出相对应。
队列 也是一种非常基础的数据结构，其特点是先入先出，也就是常听到的 FIFO（ First in First Out ），如同排队一般，先存入的数据先被压出。常与栈一同配合，可发挥最大的实力。

树

树 结构是一种包括节点（ Node ）和边（ edges ）的拥有层级关系的一种倒挂的树状的数据结构，其数据节点之间的关系也如大树一样，将有限个节点根据不同层次关系进行排列，从而形成数据与数据之间的父子关系：
下面是跟 树 相关的一些概念：

• 根节点（ root ）：树

别看 树 好像很高级，其实可看作是 链表 的高配版。树 的实现就是对链表的指针域进行了扩充，增加了多个地址指向子结点。同时将 链表 竖起来，从而凸显了结点之间的层次关系，更便于分析和理解。

二叉树

树 可以衍生出许多的结构，若将指针域设置为双指针，那么即可形成最常见的 二叉树 ，即每个结点最多有两个子树的 树 结构。
二叉树 根据结点的排列和数量还可进一度划分为 完全二叉树、满二叉树、平衡二叉树、红黑树 等。

完全二叉树、满二叉树

完全二叉树，除了最后一层结点，其它层的结点数都达到了最大值；同时最后一层的结点都是按照从左到右依次排布。
满二叉树，除了最后一层，其它层的结点都有两个子结点。

平衡二叉树

平衡二叉树 又被称为 AVL树，它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵 平衡二叉树。如下图所示：

相关概念：

• 二叉排序树：是一棵空树，或者：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为 二叉排序树。
• 树的高度：结点层次的最大值
• 平衡因子：左子树高度 - 右子树高度

二叉排序树 意味着 二叉树 中的数据是排好序的，顺序为 左结点 < 根节点 < 右结点，这表明 二叉排序树 的 中序遍历 结果是有序的。
平衡二叉树 的产生是为了解决 二叉排序树 在插入时发生 线性排列 的现象，如下图所示：

由于 二叉排序树 本身为有序，当插入一个有序程度十分高的序列时，生成的 二叉排序树 会持续在某个方向的字数上插入数据，导致最终的 二叉排序树 会退化为 链表，从而使得 二叉树 的查询和插入效率恶化。

平衡二叉树 的出现能够解决上述问题，但是在构造 平衡二叉树 时，却需要采用不同的调整方式使得 二叉树 在插入数据后保持平衡。
主要的四种调整方式有 LL（ 左旋 ）、RR（ 右旋 ）、LR（先 左旋 再 右旋 ）、RL（先右旋 再 左旋 ）。

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于 1 时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用 单旋转 进行平衡化，如果这三个结点位于一条折线上，则采用 双旋转 进行平衡化。

单旋转

这里先给大家介绍下简单的 单旋 转操作，左旋 和 右旋。LR 和 RL 本质上只是 LL 和 RR 的组合。

左旋

S 为当前需要 左旋 的结点，E 为当前结点的父节点。
左旋 的操作可以用一句话简单表示：将当前结点 S 的左孩子旋转为当前结点父结点 E 的右孩子，同时将父结点 E 旋转为当前结点 S 的左孩子。

使用 2D 图像展示上述，如下所示：

使用 3D 图像展示上述，如下所示：

右旋

E 为当前需要 右旋 的结点，S 为当前结点的父节点。右单旋 是 左单旋 的镜像旋转。
右旋 的操作同样可以用一句话简单表示：将当前结点 E 的右孩子旋转为当前结点 S 的左孩子，同时将当前结点 S 旋转为左孩子 E 的右孩子。

使用 2D 图像展示上述，如下所示：

使用 3D 图像展示上述，如下所示：

红黑树

平衡二叉树（ AVL ）为了追求高度平衡，需要通过平衡处理使得左右子树的高度差必须小于等于 1。高度平衡带来的好处是能够提供更高的搜索效率，其最坏的查找时间复杂度都是 O(logN)。但是由于需要维持这份高度平衡，所付出的代价就是当对树种结点进行插入和删除时，需要经过多次旋转实现复衡。这导致 AVL 的插入和删除效率并不高。

为了解决这样的问题，能不能找一种结构能够兼顾搜索和插入、删除的效率呢？
答案是 —— 红黑树。如下图所示：

红黑树 具有五个特性：

1. 每个结点要么是红的要么是黑的。
2. 根结点是黑的。
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
4. 如果一个结点是红的，那么它的两个儿子都是黑的。
5. 对于任意结点而言，其到叶结点树尾端 NIL 指针的每条路径都包含相同数目的黑结点。

红黑树 通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树 不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。
C++ 中的 STL 就常用到红黑树作为底层的数据结构。

红黑树 V.S 平衡二叉树

除了上面所提及的树结构，还有许多广泛应用在数据库、磁盘存储等场景下的树结构。比如 B 树、B+ 树等。

堆

堆 通常是一个可以被看做一棵 树 的 数组 对象。堆 的具体实现一般不通过指针域，而是通过构建一个一维数组与 二叉树 的父子结点进行对应，因此 堆 总是一颗 完全二叉树 。

对于任意一个父节点的序号 n 来说（这里 n 从 0 算），它的子节点的序号一定是 2n+1，2n+2，因此可以直接用数组来表示一个 堆。

不仅如此，堆 还有一个性质：堆 中某个节点的值总是不大于或不小于其 父节点 的值。将 根节点 最大的 堆 叫做 最大堆 或 大根堆，根节点 最小的堆叫做 最小堆 或 小根堆。

堆 常用来实现优先队列，在面试中经常考的问题都是与排序有关，比如 堆排序、topK 问题等。由于 堆 的根节点是序列中 最大 或者 最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选 topK 值的目的。

散列表

散列表 也叫 哈希表，是一种通过键值对直接访问数据结构。在初中，我们就学过一种能够将一个 x 值通过一个函数获得对应的一个 y 值的操作，叫做 映射。
散列表 的实现原理正是 映射 的原理，通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现 O(1) 的数据访问效率。在 映射 的过程中，事先设定的函数就是一个映射表，也可以称作 散列函数 或者 哈希函数。

散列函数

散列表 的实现最关键的就是 散列函数 的定义和选择。一般常用的有以下几种 散列函数 ：

• 直接寻址法
  取关键字或关键字的某个线性函数值为 散列地址。
• 数字分析法
  通过对数据的分析，发现数据中冲突较少的部分，并构造 散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造 散列地址。
• 平方取中法
  当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为 散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的 散列地址。
• 取随机数法
  使用一个 随机函数，取关键字的随机值作为 散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法
  取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为 散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

冲突以及冲突的解决

确定好 散列函数 之后，通过某个 key 值的确会得到一个唯一的 value 地址。但是却会出现一些特殊情况。即通过不同的 key 值可能会访问到同一个地址，这个现象称之为 冲突。

冲突 在发生之后，当在对不同的 key 值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的。所以在设计 散列表 往往还需要采用 冲突解决 的办法。

常用的冲突处理方式有很多，常用的包括以下几种：

• 开放地址法（也叫开放寻址法）
  实际上就是当需要存储值时，对 key 哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
• 再哈希法
  在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
• 链地址法
  链地址法 其实就是对 key 通过哈希之后落在同一个地址上的值，做一个 链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。
• 公共溢出区
  建立一个 公共溢出区，当地址存在冲突时，把新的地址放在 公共溢出区 里。

目前比较常用的冲突解决方法是 链地址法，一般可以通过 数组 和 链表 的结合达到 冲突数据缓存 的目的。

左侧数组的每个成员包括一个 指针，指向一个 链表 的头。每发生一个冲突的数据，就将该数据作为 链表 的节点链接到 链表 尾部。这样一来，就可以保证冲突的数据能够区分并顺利访问。

考虑到 链表 过长造成的问题，还可以使用 红黑树 替换 链表 进行冲突数据的处理操作，来提高 散列表 的查询稳定性。

图

图 相较于上文的几个结构可能接触的不多，但是在实际的应用场景中却经常出现。比方说交通中的线路图，常见的思维导图都可以看作是 图 的具体表现形式。

图 结构一般包括 顶点 和 边，顶点 通常用 圆圈 来表示，边 就是这些 圆圈 之间的连线。边 还可以根据 顶点 之间的关系设置不同的权重，默认权重相同皆为 1。此外根据 边 的 方向性，还可将图分为 有向图 和 无向图。

图 结构用抽象的图线来表示十分简单，顶点 和 边 之间的关系非常清晰明了。但是在具体的代码实现中，为了将各个 顶点 和 边 的关系存储下来，却不是一件易事。

邻接矩阵

目前常用的 图 存储方式为 邻接矩阵，通过所有顶点的二维矩阵来存储两个顶点之间是否相连，或者存储两顶点间的边权重。

无向图的 邻接矩阵 是一个 对称矩阵，是因为 边 不具有方向性，若能从此 顶点 能够到达彼 顶点，那么彼 顶点 自然也能够达到此 顶点。
此外，由于 顶点 本身与本身相连没有意义，所以在 邻接矩阵 中 对角线 上皆为 0。

有向图由于 边 具有方向性，因此彼此 顶点 之间并不能相互达到，所以其 邻接矩阵 的对称性不再。

用 邻接矩阵 可以直接从二维关系中获得任意两个 顶点 的关系，可直接判断是否相连。但是在对矩阵进行存储时，却需要完整的一个二维数组。若图中顶点数过多，会导致二维数组的大小剧增，从而占用大量的内存空间。

而根据实际情况可以分析得，图中的顶点并不是任意两个顶点间都会相连，不是都需要对其边上权重进行存储。那么存储的 邻接矩阵 实际上会存在大量的 0。虽然可以通过 稀疏表示 等方式对 稀疏性 高的矩阵进行关键信息的存储，但是却增加了 图 存储的复杂性。

因此，为了解决上述问题，一种可以只存储相连 顶点 关系的 邻接表 应运而生。

邻接表

在 邻接表 中，图 的每一个 顶点 都是一个 链表 的 头节点，其后连接着该顶点能够直接达到的 相邻顶点。相较于 无向图，有向图 的情况更为复杂，因此这里采用 有向图 进行实例分析。

在 邻接表 中，每一个顶点都对应着一条 链表，链表 中存储的是 顶点 能够达到的 相邻顶点。存储的顺序可以按照顶点的编号顺序进行。
比如上图中对于顶点 B 来说，其通过有向边可以到达顶点 A 和顶点 E，那么其对应的邻接表中的顺序即 B -> A -> E，其它顶点亦如此。

通过 邻接表 可以获得从某个 顶点 出发能够到达的 顶点，从而省去了对不相连 顶点 的存储空间。然而，这还不够。对于有向图而言，图中有效信息除了从 顶点 “指出去”的信息，还包括从别的 顶点 “指进来”的信息。这里的 “指出去” 和 “指进来” 可以用 出度 和 入度 来表示。

• 入度：有向图的某个 顶点 作为终点的次数和；
• 出度：有向图的某个 顶点 作为起点的次数和；

由此看出，在对有向图进行表示时，邻接表 只能求出 图 的 出度，而无法求 出入度。这个问题很好解决，那就是增加一个表用来存储能够到达某个 顶点 的 相邻顶点。这个表称作 逆邻接表。

逆邻接表

逆邻接表 与 邻接表 结构类似，只不过图的 顶点 链接着能够到达该 顶点 的 相邻顶点。也就是说，邻接表 时顺着图中的箭头寻找 相邻顶点，而 逆邻接表 时逆着图中的箭头寻找 相邻顶点。

邻接表 和 逆邻接表 的共同使用下，就能够把一个完整的 有向图 结构进行表示。可以发现，邻接表 和 逆邻接表 实际上有一部分数据时重合的，因此可以将两个表合二为一，从而得到了所谓的 十字链表。

十字链表

十字链表 似乎很简单，只需要通过相同的 顶点 分别链向以该 顶点 为终点和起点的 相邻顶点 即可。

但这并不是最优的表示方式。虽然这样的方式共用了中间的 顶点 存储空间，但是 邻接表 和 逆邻接表 的 链表节点 中重复出现的顶点并没有得到重复利用，反而是进行了再次存储。因此，上图的表示方式还可以进行进一步优化。

十字链表 优化后，可通过扩展的 顶点 结构和 边 结构来进行 正逆邻接表 的存储：（下面的弧头可看作是边的箭头那端，弧尾可看作是边的圆点那端）

• data
  用于存储该 顶点 中的数据；
• firstin 指针
  用于连接以当前顶点为弧头的其他顶点构成的链表，即从别的顶点指进来的顶点；
• firstout 指针
  用于连接以当前顶点为弧尾的其他顶点构成的链表，即从该顶点指出去的顶点；

边 结构通过存储两个 顶点 来确定一条 边，同时通过分别代表这两个 顶点 的指针来与 相邻顶点 进行链接：

• tailvex
  用于存储作为弧尾的 顶点 的编号；
• headvex
  用于存储作为弧头的 顶点 的编号；
• headlink 指针
  用于链接下一个存储作为弧头的 顶点 的节点；
• taillink 指针
  用于链接下一个存储作为弧尾的 顶点 的节点；

以上图为例子，对于 顶点 A 而言，其作为 起点 能够到达 顶点 E。因此在 邻接表 中 顶点 A 要通过边 AE（即边 04 ）指向 顶点 E，顶点 A 的 firstout指针 需要指向边 04 的tailvex。同时，从 B 出发能够到达 A，所以在 逆邻接表 中 顶点 A 要通过边 AB（即 边10 ）指向 B，顶点 A 的 firstin指针 需要指向 边10 的 弧头，即 headlink指针。依次类推。

十字链表采用了一种看起来比较繁乱的方式对 边 的方向性进行了表示，能够在尽可能降低存储空间的情况下增加指针保留 顶点 之间的方向性。具体的操作可能一时间不好弄懂，建议多看几次上图，弄清指针指向的意义，明白正向和逆向邻接表的表示。

参考链接

#todo:
[^heap structure]: Heap Data Structure

到了这里，关于数据结构 | 常见的数据结构是怎样的？的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！