数据结构（三）---链表

不念不忘少年蓝@ 2022-09-07 06:40 239阅读 0赞

## 概念 ##

我们先想一个游戏场景—老鹰抓小鸡。母鸡后面都有序的跟着小鸡们，第一个小鸡被第二个小鸡紧跟着防止掉队。如果有一次第二个被甩出去了后面的小鸡都没有了方向，整个队伍就散了。好在第二个小鸡及时回来补救。这就是一个单链表，在代码层面上显示出来的就是一个数组。单链表的特点就是只有一个或零个前驱有一个或零个后继。例如我们的排队、月份、星座。我们的班级算吗？不算。仔细想想只有一个或者零个。

## 线性表的顺序存储（可以想成最熟悉的数组） ##

顺序结构说白了就是在内存开一片地，占定了一定的空间，数据就按着分配的位置就坐。就好比说现在疫情，之前排队打疫苗一个人排着一个公司。这个人就很重要了，你的排队进度决定了公司的进度。数据存在内存的一片空地中，你就先找到第一个人，后面的人才能跟着找到。解决了寻找的问题就要解决空间的问题。你一个人占了10个位置，但是你采用了5个。那你不是占着茅坑不拉屎吗？对不对。这样就造成了很多的内存碎片，多数情况下都在空着。这个就是线性表的基本形成和问题  
上码  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70]  
线性表的三个属性  
1.存储的位置  
2.最大容量  
3.当前的长度（因为你不会全用完）

我们都知道，数据存在内存中都会有对应的地址。你可以想成是数组的下标0，1,2，3。  
线性表存进去的时候是长这样的(下图）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 1]  
因为我们的数据元素是要占着一定的空间，在这里我们假设一个数据元素占着C的位置，那么 a*1* 就占着C a*2*占着 C+C … 依次类推。  
（LOC代表获取到存储位置的函数）  
第i+1个： LOC(a*i+1*) = LOC(a*i*) + C  
第i个： LOC(a*i*) = LOC(a*1*) + （i-1）\*C  
![在这里插入图片描述][dddd7615b94f445c8eedc141aca89d87.png]

## 顺序结构的增删 ##

我们先好好想想在敲代码。在生活中，我们排队就是一个顺序的链表。假设我们现在在排队，突然有一个人插在你前面。你会干吗。肯定揍他NNd。他一插就算你没意见，你后面的人都会有意见。导致排在你后面的人都会意见。回到链表你添加元素的话是不是就要移动插入点的全部元素，那么操作是不时就多了很多。同理你前面的人有事不排了，那么大家是不是很欢喜。全部人都往前面走了。在最后面添加就正常流程走吧。  
所以总结一下：  
1.找到你的插入点  
2.插进去，后面的元素 就全部往后面移一位  
3.还要确保你的插入点比最大长度小，不然你插哪里去呢。  
如图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 2]  
插入代码，**删除代码就是换一下逻辑，代码还是差不多的**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 3]  
优缺点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 4]  
顺序结构就是我们去占位置，然后按着顺序排队。有人插队就要挨骂，占的位置多了也要挨骂。因为寸土寸金。

## 链式结构（可以想成是一个类） ##

既然顺序结构那么耗时间，位置那么我们就应该用链式结构去解决。  
链式结构就是哪里有空位置我就去哪里，需要我就去用。怎么达到呢？例如我们去喝茶，去银行班业务。是不是都拿着小票。你拿了小票是不是想去哪里就去哪里，只要到你了就回来。那么资源浪费是不是就解决了呢？在链表中也如此。第一个元素拿着第二个元素的地址，你要找第二个元素就问第一个元素不就行了吗？  
以下就是官方解释：为了表示每个数据元素a*i*与其直接后继数据元素a*i+1*之间的逻辑关系。对于a*i*来说，除了存储自己的数据（数据域）以外还要储存下一个数据元素的地址（指针域）。这两部分就组成了节点（Node）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 5]  
对于单链表来说就要长成这个样子，因为第一个也要另外一个人知道它的地址啊。所以要另外存储叫做头指针。存储的信息也就是一些链表的基本信息。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 6]  
注意的地方的  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 7]  
单链表（节点）的创建（不同语言有不同的想法）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 8]  
单链表的读取  
在数组中获取第 i 个数据是很简单的，直接读取就行。那么在单链表中又是怎么读取的呢？以下就是思路：

1.  先声明一个节点，让他指向链表的第一个元素，初始化J从1开始。
2.  当J<i 时，就遍历链表，让p的指针往后移动,直到找到这个数据为止
3.  若该链表没有这个数据则返回null  
    其实就是一个个的去找，他的时间复杂度取决于 i 的位置在哪 最坏的情况就是O（n）。此时是不是就发现了很麻烦，动不动就用for。熊掌与鱼不可兼得  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16]  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_17_color_FFFFFF_t_70_g_se_x_16]  
    单链表的插入  
    之前我们解释单链表的时候就说过，他们都是根据一定的逻辑连在一起的，头结点的指针域指向下一个节点。我们要执行插入的话就可以依据这个原理进行。将前一个节点的指针域给要插入的节点中的指针域，前一个指针的指针域变为要插入的节点的地址。是不是很绕，看看图吧  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_16_color_FFFFFF_t_70_g_se_x_16]  
    先进行s->next = p->next 再是 p->next = s 插进去变成  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 1]

> 注意的一点就是不能够换顺序，为什么呢？你想想如果你一开始p的指针域就指向了s，然后s的指针域又拿到了p的指针域的值。那么s指针域存的值不就是自己的地址吗？兜兜转转小丑竟是我自己。  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 2]

单链表的删除  
删除操作其实和插入操作是差不多的。也是基于指针。能看懂前面的描述的话。现在我们要删除q节点。本来p的指针域是指向q，那么现在只需要将q的指针域的值给给到p的指针域就行了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_18_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
对比一下链表的基本操作和数组的基本操作，相对来说是不是效率高了许多，这在当时的计算机发展中确实是一个历史性的进步。

双向链表。但链表搞懂了吗？搞懂了就想一下。什么是循环链表。顾名思义循环。就是最后一个结束之后又回到了头。现在就是在单链表的基础上将末节点的指针域设置为头指针的地址，这样就做到了循环。再深入一点就开辟多一个指针域来存储前驱的地址。虽然是新的概念但是写法和逻辑都是差不多的，只是判断条件改变了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70]: /images/20220829/7dec94219ca94db6856965a9f17ec56e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 1]: /images/20220829/2286824dc2a448d68f62abb75bb01ab0.png
[dddd7615b94f445c8eedc141aca89d87.png]: /images/20220829/140beb720e5640af92ce8b67d58ede76.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 2]: /images/20220829/4387d386ad374437984f52fc1a62948a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 3]: /images/20220829/51a3da291a1c4dbc98d6694e6d370e6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 4]: /images/20220829/b2153595f8da42639f1fd47472d12ef3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 5]: /images/20220829/ff37855a31194d149e80dccec4997910.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 6]: /images/20220829/869a6d6e39744d4988f5feef34b36ccf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 7]: /images/20220829/350027eb7271464391b2e1064038eef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dvcmszMw_size_16_color_FFFFFF_t_70 8]: /images/20220829/f601a056e8a9481dbc0ebdb47c4f1c9e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/387c35855af44757aee1e64a73a52312.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/2332d013ead74af0b2848108aafa55ad.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7f3ad9040caf49dda6ca601a521bd77e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/d104911a848446379011e20aa5a5f9fd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/dc3cf7b47cdd42a7a9869949ac820a57.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/ebb2296755ef44baaa3f8cd531086eb3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbmV3IG1vbmV5_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/bc502c4a2d174725a12e373d4baf7ba8.png