数据结构 | 再也不怕被问链表了

Dear 丶 2021-11-11 14:26 647阅读 0赞

> 在上篇文章我们已经简单介绍过了数组，分析过了《数组为什么这么快》，相比于数组，链表是一种稍微复杂点的数据结构。掌握起来比数组也稍微难一些，不过不要怕，跟着我一起来，相信我们可以一步步拿下数据结构跟算法，今天我们先从链表开始，加油！！！

### 文章目录 ###

*   *   *   *   *  数组跟链表的区别：
                 *   *  内存分布区别：
                     *  增删，查询的时间复杂度区别：
                 *  单链表：
                 *  双链表：
                 *  循环链表：

##### 数组跟链表的区别： #####

首先，我们对比下数组跟链表的区别

###### 内存分布区别： ######

1.  数组在内存中的分配是连续的，对内存要求比较高
2.  链表相反，它并不需要一块块连续的内存，它通过指针将一组零散的内存快串联起来使用

我们可以举个例子：当我们申请一个32M大小的内存，但是现在内存中没有一块连续的内存大于或等于32M的内存块，可以画图表示如下：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70]

在这种情况下如果我们申请的数据结构是一个数组，那么内存的分配就会失败，反之如果我们申请的是一个链表的话就不会失败，因为链表的结构可以通过指针将这4个8M的内存块串联起来使用。

###### 增删，查询的时间复杂度区别： ######

1.  查询，数组时间复杂度为O(1)，这里特指的是通过数组下标访问，不是指在数组中查询指定的值，具体可以参考我之前的文章：[数据结构|数组为什么这么快？][Link 1]
    
    链表的时间复杂度为O(n)，如果我们需要在链表中访问一个元素，受链表底层数据结构的影响（不连续，通过指针串联）所以必须要一个个节点的遍历，不难得出时间复杂度为O(n)
2.  增删，数组的增加或删除一个节点的时间复杂度为O(n)，而链表的时间复杂度为O(1)。这里需要特别指出，我们在这里所说的增删特指单纯的删除动作。这是什么意思呢？大家可以看下面的图：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 1]  
    如果我们删除上图中下标为3的元素，对于数组而言，其实我们需要做的就是将4，5两个元素向前移动一个位置。所以对于数组删除的时间复杂度是没有影响的，O(n)。但是对于链表而言的话，我们需要先找到下标为2的这个元素，然后将下标为2的元素指向下标为4的元素。在查找下标为2的元素的这个过程中，我们知道链表的时间复杂度已经为O(n)了，虽然后面指针的断裂及再次指向下一个元素，时间复杂厚度为常量级，但是整个过程时间复杂为O(n)。所以我们下次在面试的时候就应该好好说清楚啦~

##### 单链表： #####

如图所示就是一个单链表：![在这里插入图片描述][20190806005747827.png]

这里我们需要注意的主要是以下几点：

1.  每个节点都保存了指向后一个节点的指针
2.  头节点：链表就好比一条线，如果我们想捋清楚这条线，就一定要有一个线头，头节点就是这个线头，通过这个节点我们可以遍历整个链表，它记录了链表的基地址，及下一个元素的地址
3.  尾节点：比较特殊的是，它指向了null

##### 双链表： #####

图示如下：

![在这里插入图片描述][20190806005758452.png]

我们可以跟单向链表做一个比较：

1.  每个节点都保存了不仅仅是指向下一个节点的指针（后置指针），还有前一个元素的指针（前置指针）
2.  头节点：保存了指向第二个元素的节点，前置指针指向null
3.  尾节点：保存了指向倒数第二个元素的节点，后置指针指向null

**到此，我们分析下相比于单向链表，双向链表用于解决什么问题呢?**

我们对比单链表跟双链表的结构可以发现，双向链表可以支持O(1)的时间复杂度找到前置节点，正是这样的特点，也使得双向链表在某些情况下的插入，删除等操作都比单链表要高效。

我们可以分析这么一个场景，比如我们现在要删除一个给定指针指向的节点：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 2]

我们现在要删除p指针指向的节点，不管对于单链表还是双链表我们操作的步骤都是将Q指向M，同时将Q与P，P与M之间的链断掉。但是对于单链表而言，无法直接找到Q，因为没有保存一个指向上一个元素的指针，所以必须要从头遍历。而对于双向链表而言，P本身就保存了指向Q的一个前置指针。相比而言，双向链表的效率就大大提高了。

另外我们可以发现，双向链表由于比单链表多保存了一个指针，所以内存的消耗也会高于单链表

##### 循环链表： #####

循环链表其实是一种特殊的单链表，与单链表不同的是，循环链表的尾指针不是指向null，而是指向头节点，图示如下：

![在这里插入图片描述][20190806005819728.png]

与一般的单链表比较，循环链表最大的优点就是从链尾到链头比较方便。当处理的数据具有环形结构特点时，就特别适合采用循环链表。

总结：

到这里，我们已经对链表的各种情况都做了一个分析，也有了一个了解，但是单纯的知道它是什么是没有用的，我们可能更加知道这些数据结构能为我们做什么呢？所以下篇文章我们，我们将一起学习如何应用链表来解决我们的一些实际问题，包括缓存失效算法，约瑟夫问题等~

码字不易，喜欢的朋友加个关注，点个赞吧，万分感谢！

[数据结构与算法|目录汇总][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70]: /images/20211109/a9efd3aacb6c41b59f93a0d19462b3cf.png
[Link 1]: https://blog.csdn.net/qq_41907991/article/details/97844875
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 1]: /images/20211109/17be7c05d0e14bcb916277b1014349ca.png
[20190806005747827.png]: /images/20211109/00f67c3c24184b26b61a7813ed733777.png
[20190806005758452.png]: /images/20211109/528e0b64c659493da5c0ee2ae07bfc2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTA3OTkx_size_16_color_FFFFFF_t_70 2]: /images/20211109/2bb805fb5f0340d2a2e4f13efda9114b.png
[20190806005819728.png]: /images/20211109/1e8693bc9f54468598155643fa095d1e.png
[Link 2]: https://blog.csdn.net/qq_41907991/article/details/98533954