图解！链表真的很简单。

港控/mmm° 2022-09-09 02:19 190阅读 0赞

大家好呀，我是蛋蛋。

[数组的文章][Link 1]中给臭宝们说过，连续的内存使得数组在进行插入和删除时需要移动大量元素，这就意味着要耗费时间。

在数据结构与算法中，快男才是大家的最爱，像插入和删除这么持久的蓝孩子显然不受待见。

后来，大家就想方设法帮助它们变快。

那么有没有这么一种数据结构可以达成这一目的呢？

链表就这么被整出来了。  
![在这里插入图片描述][989a4d4f01254643918e68d1b1b62ecb.png_pic_center]  
相比于数组，链表是稍微复杂一些的数据结构，但是不难，只要跟着本蛋就能学会。

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

### 链表 ###

**首先什么是链表？**

**线性表的链式存储结构生成的表，叫做链表。**

**那么什么是链式存储结构咧？**

链式存储结构是指**用一组任意的存储单元存储线性表的数据元素，通过指针连接串联起来。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 1]

这里的“任意”指的就是，**存储单元可以连续也可以不连续**，这就意味着**它们可以是内存中任何未被占用的地方。**有味儿点讲就是只要内存这个厕所里空着的茅坑，你就随便蹲。

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

链表中的存储单元叫做**节点**。它和数组中只存数据信息不同，每个节点分为两部分：**数据域和指针域**。数据域存储的数据，指针域存储着同一个表里下一个节点的位置。

因为链表家族里的兄弟姐妹太多，在这里咧我只讲常见的几种链表结构：单链表、双向链表。

毕竟再多，我写的就累死了。。

### 单链表 ###

n 个节点可以链接成一个链表，如果**链表中的每个节点只包含一个指针域，这个链表就叫做单链表。**

单链表的指针域指向的是下一个节点的地址，我们把指向下个节点地址的指针叫做**后继指针**。  
![在这里插入图片描述][61834eb8994f4561b16309eee5a66719.png_pic_center]  
单链表的第一个节点的存储位置叫做**头指针，最后一个节点的后继指针为空**，一般用 NULL 或者 “^” 表示。  
![在这里插入图片描述][7b03d5c5c0554df7ae5603f005b2707b.png_pic_center]  
除了上面的，有时候为了操作方便，会在单链表的第一个节点前面加一个节点，称之为**头节点**。这个头节点一般不存储任何内容，它的指针域指向单链表的第一个节点。  
![在这里插入图片描述][7afe58c36e0c4b13a3b5a7a604b33448.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 3]

> 臭宝：停停停！又是头指针又是头节点的，有点懵。。。  
> 蛋蛋：莫慌，有我。

#### 头指针与头节点的区别 ####

**头指针**，顾名思义，是指向链表第一个结点的指针，如果有头结点的话，那么就是指向头结点的指针。

\*\*它是链表的必备元素且无论链表是否为空，头指针都不能为空，因为在访问链表的时候你总得知道它在什么位置，这样才能通过它的指针域找到下一个结点的位置，也就是说知道了头指针，整个链表的元素我们都是可以访问的。

所以头指针必须要存在，这也就是我们常说的**标识**，这也就是为什么我们一般用头指针来表示链表。

**头结点**，是放在第一个元素的节点之前，它的数据域一般没有意义，并且它本身也不是链表必须要带的。

**它的设立是单纯是为了操作的统一和方便**，其实就是为了在某些时候可以更方便的对链表进行操作，有了头结点，我们在对第一个元素前插入或者删除结点的时候，它的操作与其它结点的操作就统一了。  
![在这里插入图片描述][13f890295a234a98aff6d2b10c2a28e4.png_pic_center]  
除此以外，还有一种啥也没有，空空空空～**空链表**。  
![在这里插入图片描述][30db2b0629e14511b946da8f8a499ac8.png_pic_center]  
不知道臭宝们发现了没，不管是带头节点，还是不带头节点，或者是空的链表，它们都是有头指针的，这正印证了我在上面提到过的“**头指针是链表的必备元素，无论链表是否为空，头指针都不能为空**”。

别说话，夸我~

#### 单链表的操作 ####

和数组一样，单链表也有查找、插入和删除等操作。因为链表的存储空间是不连续的，所以链表的插入和删除操作是很快速的。

##### 插入操作 #####

假设我们要完成一个插入操作：在节点 p 后面插入节点 s。

正确的做法是，只需要将节点 s 插入到节点 p 和节点 p.next 之间就可以，说起来很简单，具体操作请看下图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 4]  
从上图中可以看出，单链表的插入其实根本不需要惊动其它的节点，只需要让 s.next 的指针和 p.next 的指针稍作改变。**让节点 s 的后继指针指向 p 的后继节点，然后 p 的后继指针指向节点 s，这里切记，插入操作的顺序一定不能改变**。

可以看出插入操作的时间复杂度是 O(1)。

##### 删除操作 #####

假设我们要完成一个删除操作：删除节点 p 的后继节点 q。

其实也简单，就是将 p 的后继指针绕过 q，直接指向 q 的后继节点即可，具体操作如下图。

![在这里插入图片描述][2208367df50748769d73a5fd24c12580.png_pic_center]  
由上图看出，同样只需要一步就可以实现删除操作，直接让 p.next 指向 q.next 即可，所以删除操作的时间复杂度为 O(1)。

##### 查找操作 #####

当然啦，有快的地方就有慢的地方，元素的查找就是链表美中不足的地方。

数组在内存中排排坐不同，链表的在内存中的地址是分散的，只能通过前一个节点的 next 才知道当前节点的位置，所以在链表中想要找第 i 个元素，只能傻傻的从头开始找，直到找到第 i 个元素位置。

从这可以看出，链表中查找操作的时间复杂度是 O(n)。

#### 单链表实际应用场景 ####

单链表说了这么多也差不多了，辣么有个问题，我学了这个玩意能用在哪呢？

easy！

单链表的应用的话一般能用在 **2 种场景**下：

(1) 第 1 种基操。 在你应用的场景中，插入和删除的操作特别多，你不想因为这俩操作浪费你太多的时间，此时用单链表，可以改善插入和删除操作浪费的时间。

(2) 第 2 种骚操。在你应用的场景种，不知道有多少个元素，那这个时候你用单链表，每来一个新的元素你就链在表里，这种情况是用链表处理的绝佳方式。也是很容易被大家忽略的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70][]

### 双向链表 ###

**双向链表**，顾名思义，两个方向向的链表。**相比起单链表来说，它多了一个前驱指针 prev，指向前驱节点**。这样双向链表既可以往前走，也可以往后走。  
![在这里插入图片描述][a417331f70b442e1b94b6ff38af593af.png_pic_center]  
![在这里插入图片描述][b33e0104357b4941860a27e93058ee86.png_pic_center]  
从上面两张图看，双向链表多了一个前驱指针，使得在内存上比单链表占用更多的空间，但是**双向链表在查询链表元素的时候会更加方便**，比如可以在 O(1) 的时间内超找到当前节点的前驱节点，这是典型的用空间换时间。

> 空间换时间，在内存够用的情况下，为了追求更快的执行速度，选择空间复杂度较高，时间复杂度较低的数据结构或者算法。

既然用了时间换空间，那双向链表比单链表快在哪个地方呢？那这个还是从插入、删除操作说起。

可能在这臭宝们拿起键盘会说，单链表的插入和删除都已经是 O(1) 了，还要怎么快？

其实准确点来说，**插入和删除是 O(1)，更多的是针对插入或删除这单个动作来说的，在实际情况下，一切都有前置条件**。在某些前置条件下的实际应用场景，双向链表比单链表更快。

下面开始表演。

#### 插入操作优势 ####

插入操作，无非就是 2 种情况：

*  在 “data域等于某个特定值”的节点前或者后插入一个新的节点。
 *  在给定的节点前或者后插入一个新的节点。

针对第 1 种，这俩时间复杂度都差不多。都是分两个步骤：

第一步找到 data 域等于某个特定值的节点，无论单链表还是双向链表都需要从头开始一个一个的遍历，这一步的时间复杂度都是 O(n)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 5]  
第二步就是插入操作。如果都是向后插入的话，那时间复杂度都是 O(1)，如果是向前插入的话，那单链表慢一些，它需要再重新找到特定值节点的前驱节点，这个时间又花费 O(n)，而双向链表不用，因为它有前驱节点，直接就能找到特定值节点的前驱节点，这个时间花费的是 O(1) 。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 6]  
针对第 2 种情况，其实他就是第 1 种情况中的第二步，已经找到了要插入的节点，如果都是向后插入的话，单链表和双链表的时间复杂度都一样，都是 O(1)。差别就差向前插入，向前插入的话就需要知道当前节点的前驱节点，单链表需要重新遍历到当前节点的前驱节点，总的时间复杂度是 O(n)，而双向链表一下子就能找到它的前驱节点，时间复杂度是 O(1)。

这就是双向链表优势于单链表的地方。

#### 删除操作优势 ####

删除操作，和插入操作差不多，也基本上是 2 种情况：

*  删除 “data域等于某个特定值”的节点。
 *  删除给定的节点。

第 1 种情况就不说了，单链表和双向链表都一样，都是从头开始一个个的遍历，时间复杂度都是 O(n)。

第 2 种情况，删除给定的节点，这就要求需要知道这个节点的前驱节点。单链表需要从头开始找，直到“node.next = 当前节点”的适合，才是找到了当前节点的前驱节点 node，这个过程的时间复杂度是 O(n)。而双向链表直接就知道它的前驱节点，只需要时间复杂度是 O(1) 就可以搞定。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 7]

--------------------

常见的链表到这就讲完啦，当然在这基础上衍生出来的像循环链表、循环双向链表都还没说，一次整太多怕你们消化不良。

我会在之后的刷题环节中慢慢给大家都整明白，保证把臭宝们伺候的明明白白~

链表这东西呢，不要怕，虽然看起来有些复杂，但其实就那几板斧，学链表的时候多在纸上画画，各种关系无所遁形，啥都就整明白了，不信你试试。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 8]  
当然啦，能看到这的都是真爱，**一键三连留言么么哒**给我刷起来～

我是蛋蛋，我们下次见！  
![在这里插入图片描述][fe0ab2424c734401925878dd94e9ec08.gif_pic_center_pic_center]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI0NjAxMDU5NA==&mid=2475918890&idx=1&sn=b5dbd85bbe358d7b1668e2d9c27e2122&chksm=ff22e1a7c85568b122279e836dec029dcc9b6a8049cf84c659ccff6f69eb29e6187912b1de66&token=2021865527&lang=zh_CN#rd
[989a4d4f01254643918e68d1b1b62ecb.png_pic_center]: /images/20220829/af93ad7763a349bdaac949973c0e0f50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/c6bda43bf7ba4acda58e6bc685279c37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/d3951383b58542fc8dc7cd81e7fd1612.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/52ee57075a7143129e4f91ea170ae45d.png
[61834eb8994f4561b16309eee5a66719.png_pic_center]: /images/20220829/97718d715e0947c7a213801c8097148a.png
[7b03d5c5c0554df7ae5603f005b2707b.png_pic_center]: /images/20220829/5b68a406d6ec40c3b9c86540218a3be3.png
[7afe58c36e0c4b13a3b5a7a604b33448.png_pic_center]: /images/20220829/4b7df385d04a4806a749c46dbf6fe304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220829/72254c0a5242487ab9ae1d110f099400.png
[13f890295a234a98aff6d2b10c2a28e4.png_pic_center]: /images/20220829/335531ef32554cbaaca2a9896b60a073.png
[30db2b0629e14511b946da8f8a499ac8.png_pic_center]: /images/20220829/293e69adfaaf43839cbdbb9c9dd41d93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220829/7f718177aacc41b098d331a3a8fe175a.png
[2208367df50748769d73a5fd24c12580.png_pic_center]: /images/20220829/9eec268cd9b444cda6fb2a68e862e6e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70]: /images/20220829/2f5b2d8304ea42f9ac98141eda692f80.png
[a417331f70b442e1b94b6ff38af593af.png_pic_center]: /images/20220829/cbe43a79faf94eb7bcb5b924edc7094f.png
[b33e0104357b4941860a27e93058ee86.png_pic_center]: /images/20220829/b6eb5f7ff1ab467eb9937f140a4d3deb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20220829/1fe972e936494ef99d0ac77b1743cef9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20220829/2a84a1a48d49465aa94b8f98d066cddf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20220829/84958a2b76944ec49431474b8a25e513.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0ODY0MTQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20220829/6f06e6bd1c604ff5aa88b7401e16caa7.png
[fe0ab2424c734401925878dd94e9ec08.gif_pic_center_pic_center]: /images/20220829/2aa9e2913b1448128d6bdce3a42c30b7.png