几种基础数据结构的比较

**对于计算机而言，它只知道利用内存地址去访问内存中的变量，我们人为分出了两种存储形式，一种是连续存储（也就是数组），一种是链式存储（链表），至于其他的数据结构其实都是对这两种存储形式的利用。任何一种数据结构都可以用两种存储形式去实现，只有合适不合适的问题，没有能不能的问题，因为最终都是利用内存地址去访问内存。**队列，栈我们平时都用数组实现，但是用链表也可以，比如树我们大部分情况下用链表实现，但是其实像完全二叉树用数组去实现也完全没问题。

这篇博客主要是**通过一些例子去分析这些情况下我们需要什么数据结构的什么特性，为了更好地满足这些特性，我们需要用数组还是链表去实现。**对于所有的内容都不会去细讲，更不会涉及具体实现，因为都很基础，但真要展开讲也会变成长篇大论，我们更主要的是从一个更高的层面看他们的一些特性。

什么是数据结构

我个人认为，数据结构可以分两部分说。

一种是数据的存储结构，也就是顺序存储还是链式存储。

一种是数据的逻辑结构，及一组相同类型的数据之间的特殊关系以及为了维持这种关系定义的一系列特殊的增删查改操作。

如何选择设计一个数据结构

不同的数据结构适用于不同的场景，数组的连续性可以让我们高效地随机访问，但是插入和删除就比较费时，扩容也比较麻烦，而链表虽然不能高效地随机访问，但是插入和删除很简单，也没有扩容这一说。我们设计数据结构的时候就是反复利用这两点来做文章。

比如拉链式的散列表利用哈希函数快速获得数组下标，然后利用链表实现快速插入和删除。

比如利用堆（一种完全二叉树）来实现将链表搜索的O(n)简化为O(logn)等。

我们平时选择一个数据结构的思考过程应该是这样的：

• 我们这个场景需要选择什么样的算法，如逆波兰就是需要先进后出

• 这个算法需要什么特性的数据结构，如果只需要入栈出栈，那就选择栈。

• 再根据我们具体的需求，是否需要频繁扩容缩容，是否对访问时间有高要求等等选择数据结构合适的存储方式。

其实这个过程与数据结构产生的过程是相反的。

无论是数组还是链表，对于计算机而言都是利用内存地址去访问内存中的数据，只不过数组的内存地址是连续的，所以我们可以通过首地址加偏移量的形式直接计算出要访问的数据的内存地址，而链表的内存地址是不连续，需要链表中的每一个节点记录下一个节点内存地址，而不是通过偏移量计算得出的。

所以说数组还是链表其实是我们人为对计算机存储空间的一种利用形式的不同。

而不同的数据结构可以说是我们赋予这些相同类型数据之间的一些特殊关系，这些关系能够帮助我们算法更高效地执行，所以需要特殊的插入删除方式去维持这种关系。如只能FIFO的数组我们叫队列，必须左子节点小于父节点，右子节点大于父节点的我们叫二叉搜索树。

数组和链表

数组和链表既是计算机内存中存储数据的两种方式，也是最基本的数据结构，用来进行最基本的数据存储。

队列

队列的特性就是先进先出（FIFO），它的操作就是入队和出队，入队就是在队尾添加一项，出队就是从队首弹出一项。

比如我们JavaScript中的EventLoop，或者Vue中的nextTick都是这种形式。

每次事件触发后都将回调函数放入到一个队列中，然后不断循环从头遍历队列，依次从头部取出回调函数来执行。

当我们需要运用到先进先出的特性时，我们就可以使用队列这种数据结构。

而队列的实现，使用数组和链表都没有问题，正常情况下，它的插入和删除都只需要O(1)。

但是如果利用数组来实现，由于数组的连续内存的特性，导致我们必须事先指定好这个数组的大小，然后去申请一块连续的内存，所以如果一旦队列的长度需要超过一开始的队列长度，那就存在一个扩容问题，我们需要申请一块更大的内存，然后把数据拷贝过去，再回头把这块内存释放掉，这个时候插入的时间复杂度就会变成O(n)。

而如果使用链表则不会存在扩容问题，因为它的内存是不连续的，我们可以在入队时单独为入队的数据申请内存。但是由于它的内存是不连续的，所以我们没有办法通过首地址加偏移量的方式计算出每个节点的地址，就需要额外的空间去记录每个节点的地址，也就是我们每个节点都要记录下一个节点的地址。

所以说具体是使用数组还是链表具体还要看需求，如果队列长度固定或者不怎么变化，用数组比较好，因为连续的内存空间对于缓存比较友好，但如果队列长度会不断变化，需要存储的数据也比指针所需的空间大得多，其实链表更好一点。

关于队列的其他内容可以去看我的另一篇关于队列的文章

栈

栈的特点是先进后出，它的操作就是入栈和出栈，入栈也可以叫做压栈，就是从栈顶压入一项，出栈就是从栈顶弹出一项，也就是入栈和出栈是从同一头。

比如leetcode上面的这道逆波兰表达式求值，它的解题思路就是非常经典的栈的应用。

同样的，栈的实现也是既可以用数组实现，也可以用链表实现。

关于栈就不多做分析了，其实和队列是大同小异的。

跳表

我们上面也说过，链式的问题就在于对于随机访问的时间复杂度是O(n)。

即便是链表中的数据已经是从小到大排好序的，也没法像数组那样利用二分法在O(logn)的时间夫复杂度找到需要的数据。

针对这种问题，计算机领域经典的空间换时间就来了，我们可以每隔k个节点向上抽出第一个节点组成一个新的链表，抽出的节点中保存一个新的指针指向原节点。

这样我们层层抽取，直到某一层只剩一个节点。

这个时候我们再去查找某个数据，就可以先从最上层比较，如果大于当前节点值，就把指针下移一层，再向后比较，找到最后一个小于它的节点，再下沉，一直到最后一层。

这样一来查找的时间复杂度就会下降为以k为底n的对数。

我们常说的redis数据库其使用的就是跳表。

散列表

关于散列表的介绍，可以先去看一下我的这篇关于散列表的文章

看完以后，我们可以大概总结下，散列表完全可以只是一个数组，它利用的最重要的特性就是数组可以根据下标进行O(1)时间复杂度的随机访问，通过散列函数计算出数据应该存储的下标位置，但是由于鸽笼原理（n + 1只鸽子放在n个笼子里，必定有个笼子不止一个鸽子），就算你的散列函数设计的再好，散列冲突是必然存在的。

那我们就要想办法解决散列冲突，一种就是开放寻址法，通过其他方法在散列表中找到另一个空位，另一个就是利用链表的特性，使用拉链法，散列表中的每一项其实都是一个链表的头节点，每次插入数据其实都是在链表中插入。

拉链法就很好地结合了数组和链表的特性，首先利用散列函数计算出数据应该存在的散列表下标，利用数组随机访问的优势快速找到应该存在的链表，然后在链表中找到或者插入。只要我们散列函数设计得好，这个拉链平均长度就不会太长，时间复杂度还可以认为是O(1)。

树

到目前位置，我们可能觉得散列表已经能够很好的支持我们的需求了，为啥还需要出现树呢？

这里我们就要讲一下几点散列表的局限性了：

• 散列中的数据是无序的，也就是说如果要查找某个特定的值，散列可以很好的运作，但是如果我们要找某个范围的所有数据，散列表就没法工作了
• 散列函数很难设计，所以导致散列表的性能很不稳定，而且如果涉及到扩容缩容之类的，更加麻烦。
• 为了尽量避免散列冲突，装载因子不能太大，所以会有部分空间浪费。

二叉搜索树

对于刚才讲的第一点局限性，我们可以使用二叉搜索树(BST)来实现

二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？这些都依赖于二叉查找树的特殊结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

除了插入、删除、查找操作之外，二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。这些操作我就不一一展示了。我会将相应的代码放到 GitHub 上，你可以自己先实现一下，然后再去上面看。二叉查找树除了支持上面几个操作之外，还有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

平衡二叉搜索树

上面讲的二叉搜索树看起来也很好，但是还是有问题。假设我们又1-9九个树，很有可能通过一系列的插入删除操作，变成了从根节点一路左子节点到0，那这个时候二叉搜索树就变成了个链表，效率就会急剧退化成O(n)。

所以我们就需要尽量保证左右子树的高度差别不要太大，这就引出了平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1。

如果我们的BST还是一个平衡二叉树，那就可以很好解决上面这个问题。

当然我们实践中可能用到的更多是红黑树，一种近似平衡的二叉树。

堆（完全二叉树）

堆是一种特殊的树。我们现在就来看看，什么样的树才是堆。

我罗列了两点要求，只要满足这两点，它就是一个堆。

• 堆是一个完全二叉树；

• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

第一点，堆必须是一个完全二叉树。还记得我们之前讲的完全二叉树的定义吗？完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

第二点，堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做“小顶堆”。

对于堆的应用，非常常见的就是TopK的关键词推荐。

对于这个需求，我们可以维护一个节点数为K的小顶堆，然后依次遍历关键词出现的次数，如果次数小于根节点，则继续，如果大于则进行入堆操作。

图

既然又出现了一个新的数据结构，那就必然是有的问题上面的数据结构没法很好地支持。

作为除了树以外的另一种非线性数据结构，图能够表达的关系是交叉的，节点之间的关系不一定是父子关系。

比如我们的社交网络，每个人都是一个节点，两两之间如果存在关系，就连接起来，这种关系是树无法表达的。

当然，图的存储也可以用数组或者链表，数组的话我们可以用邻接矩阵，链表我们可以用邻接表