启航数据结构算法之雅舟，悠游C++秘境——单链表之美好构筑 ...

   人无完人，持之以恒，方能见真我！！！
共同进步！！
  
  
一、单链表的概念与结构

1.单链表的概念

   链表是⼀种物理存储结构上⾮一连、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接序次实现的，我们可以使用生活中的例子打个简单的比喻，如图：
  

   举的例子就是我们生活中的火车，淡季时⻋次的⻋厢会相应淘汰，旺季时⻋次的⻋厢会额外增长⼏节，只必要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的
    链表实在大致也是这样，它的每个节点都通过next指针连接起来，每个节点看起来就像一个又一个车厢，整个链表看起来就像一辆火车，如图：
  

   在真正的链表中也是前后相互连接的，只是它们连接起来的依据是地址，前一个节点通过存储后一个节点的地址来找到后一个节点，这就涉及到了我们链表中单个节点的结构了，我们接下来继承来学习
  2.单链表的节点

   与顺序表差别的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“节点”，结点的组成主要有两个部分：当前结点要生存的数据和生存下⼀个结点的地址（指针变量），这样我们的一个节点就可以在生存数据的基础上，通过它所存储的下一个节点的地址找到它的下一个节点
    链表不像顺序表那样，直接定义出一个确定的结构，链表是由一个一个节点组成，以是我们必要定义的是节点的结构，前节点和后节点建立肯定的关系，这样所有节点组合起来就抽象出来了我们的链表
    接着我们来看单链表一个节点的结构是怎么定义的，如下：

1. typedef int SLDateType;
3. typedef struct SListNode
4. {
5.         SLDateType data;
6.         struct SListNode* next;
7. }SLTNode;

复制代码

  在我们定义的这个节点结构中，有两个成员，一个是我们所存放的数据data，由于我们一个节点的下一个节点也是一个这样的结构体，以是指向下一个节点的指针是一个结构体指针，也就是类型为struct SListNode*的指针
    然后由于我们不知道要存放的数据是什么类型，以是我们这里 typedef 一个类型来取代，以后如果要用单链表就可以在这里快速更改
    我们再次总结一下链表节点的特点，链表中每个结点都是独⽴申请的（即必要插⼊数据时才去申请⼀块结点的空间），我们必要通过指针变量来生存下⼀个结点位置才气从当前结点找到下⼀个结点
  3.链表的性质

   链表和顺序表从本质上有所区别，它们都属于线性表，也就是在逻辑上它们都是一连的，但是物理上一个一连一个不愿定一连，接下来我们就来总结一下关于链表自己的一些性质：
   

• 链表属于链式结构，它在逻辑上是一连的，在物理结构上不⼀定一连
  
• 结点⼀般是从堆上申请的，也就是链表的节点是malloc来的
  
• 从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能一连，可能不一连，以是链表物理上可能是不一连的
  
• 当我们想要生存⼀个整型数据时，现实是向操作系统申请了⼀块内存，这个内存不仅要生存数据，也必要生存下⼀个结点的地址（当不存在下⼀个结点时，它的next指针生存的是空指针）
  
• 当我们想要访问链表的所有数据时，只必要得到头结点即可，根据头结点的next指针可以找到下一个节点，下一个节点也可以通过自己的next指针找到再下一个节点，以是得到头结点我们就可以访问整个链表
  

  二、单链表的实现

1.结构准备

   在我们实现链表的各种方法之前，我们必要在我们的SList.h定义好单链表的结构，然后把必要用到的头文件包罗一下，然后再在上面我们也已经介绍过了，这里直接给出代码：

1. #include <stdio.h>#include <stdlib.h>#include <assert.h>typedef int SLDateType;
3. typedef struct SListNode
4. {
5.         SLDateType data;
6.         struct SListNode* next;
7. }SLTNode;

复制代码

2.链表的打印和节点申请

   为了方便我们调试以及插入节点，我们要先办理链表的打印和节点申请，而我们在使用链表时，一般都是直接在主函数中创建一个叫plist的节点指针，把它当作链表的头结点，它只是一个指针，最开始初始化成空指针即可，不必要专门写一个初始化函数，在我们插入数据后，它就指向我们的头结点
  打印函数

   实在链表的打印很简单，我们之前也讲过，只要知道一个链表的头结点就可以访问整个链表，这里我们函数只必要接收一个链表的头节点，然后对它举行打印，我们取的函数名为SLTPrint
   具体方法就是，创建一个节点指针pcur指向我们的头结点，然后创建一个循环，只要pcur不为空，那么就打印pcur指向的节点的数据，然后让pcur走到下一个节点，也就是pcur = pcur->next
   然后跳出循环后再打印一个NULL，由于单链表的最后一个节点之后是空指针，为了体现我们打印到了最后，我们就再打印一个NULL
   最后我们还要注意一个点，由于后面我们要实现的方法函数都是传的二级指针，虽然打印函数传一级指针就够了，但是为了保持我们传参的一致性，以是这里我们打印函数还是传二级指针，也就是头结点的地址，函数具体代码如下：

1. void SLTPrint(SLTNode** pphead)
2. {
3.         assert(pphead);
4.         SLTNode* pcur = *pphead;
5.         while (pcur)
6.         {
7.                 printf("%d-> ", pcur->data);
8.                 pcur = pcur->next;
9.         }
10.         printf("NULL\n");//因为链表最后一个节点指向空，所以可以打印出来
11. }

复制代码

节点申请函数

   顺序表中我们空间不够时必要一个扩容函数，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组举行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接制止了空间浪费
    节点申请函数的名称一般很故意思，就叫SLTBuyNode，就像我们借钱向操作系统买了一个空间
    它的参数只有一个，就是我们申请一个节点后，新节点要存放的数据，返回值就是节点指针，由于我们最后要用malloc向操作系统要一个节点巨细的空间，要返回指向这个节点的地址
    使用节点申请了节点后，我们就把这个节点的数据部分该成我们传过来的参数，它的next指针就置为空指针NULL，最后把这个节点地址返回，具体代码如下：

1. //申请新节点
2. SLTNode* SLTBuyNode(SLDataType x)
3. {
4.         SLTNode* newnode = (SLTNode*)malloc(sizeof(SLDataType));
5.         if (newnode == NULL)
6.         {
7.                 perror("malloc fail\n");
8.                 return NULL;
9.         }
10.         newnode->data = x;
11.         newnode->next = NULL;
12.         return newnode;
13. }

复制代码

3.链表的头插和尾插

头插函数

   我们在使用链表时，一般是直接创建一个phead的节点指针当作链表的头结点，它只是一个指针，最开始初始化为空指针，而不必要初始化函数
    后面将这个头结点传给各种函数来对链表举行操作，以是这里我们直接介绍头插函数对链表举行插入操作，而不是写初始化函数
    由于我们头插函数是向链表的最开头插入节点，以是会改变头结点的指向，让头节点指向插入的新节点，也就是会改变实参phead，以是我们在传参时必要传phead的地址，也就是二级指针，我们给它取名为pphead，体现它是指针的指针
    头插比尾插简单许多，头插只必要做一步，就是将新节点的next指针指向本来的头结点，然后让头节点走到新节点上成为新的头结点，我们来画个图理解一下：
  

1. void SLTPushFront(SLTNode** pphead, SLDateType x)
2. {
3.         assert(pphead);
4.         SLTNode* newnode = SLTBuyNode(x);
5.         newnode->next = *pphead;
6.         *pphead = newnode;
7. }

复制代码

尾插函数

   尾插函数实在也很简单，关键是我们要尾插，起首就要找到尾结点，本来链表中的尾结点的next指针指向空，现在我们让它指向我们的新节点，由于新节点的next指针在申请节点函数中，已经默认被置为了空，以是不消管，如图：
  

   但是上图的情况是建立在原链表不为空的情况下的，如果原链表为空，那么就没有尾结点，也就没有尾结点的next指针，上面的思路就有问题
    以是我们必要特别处置处罚一下，如果原链表为空，那么就直接让我们的新节点直接酿成原链表的头结点，接下来我们就来分析一下如何使用代码完成上面的思路
    起首是如果链表中还没有节点，那么就直接让头结点指向我们申请的新节点，以是我们是有可能要改变头结点的，也就是可能更改我们的phead指针的指向，以是我们要传二级指针，取名为pphead
    如果链表中已经有了节点，那么我们要找到链表的尾节点，尾节点最大的特点就是它的next指针指向空，以是我们创建一个叫ptail的节点指针，让它指向头结点，然后开始循环遍历，结束条件就是ptail指向的节点的next指针为空
    如果ptail的next指针不为空，那么就让ptail=pail->next，我们接着就来实现一下尾插的代码，如下：

1. void SLTPushBack(SLTNode** pphead, SLTDateType x)
2. {
3.         assert(pphead);
4.         SLTNode* newnode = BuyNode(x);
5.         if(*pphead == NULL)
6.         {
7.                 *pphead = newnode;
8.         }
9.         SLTNode* ptail = *pphead;
10.         while(ptail->next)
11.         {
12.                 ptail = ptail->next;
13.         }
14.         ptail->next = newnode;
15. }

复制代码

4.链表的头删和尾删

头删函数

   链表的头删也不难，只必要把当前的头结点释放掉，然后让头结点指向本来头结点的下一个节点，如图：
  

   但是我们要意识到一个问题，就是如果我们直接释放掉当前的头结点，能不能让头结点指向下一个节点，很明显直接这样是不可的，由于头结点指向的空间已经被释放了，也就不能找到它的next指针，从而找到下一个节点
    以是我们必要先把创建一个节点指针变量next，让它将头结点的下一个节点记录下来，现在我们就可以直接释放头结点，释放完之后让phead重新走到我们存下来的next的位置
    其次另有一种情况我们要想想，就是链表中只有一个节点我们上面的思路是否可行，我们定义一节点指针next指向头结点的下一个节点，由于只有一个节点，以是头结点的next指针指向空，我们的节点指针next就生存的是空
    然后我们把头节点释放，让头结点走到next这个节点指针，也就是让头结点酿成空指针，刚好体现我们的链表为空了，由于头结点为空了，以是链表只有一个节点是可行的
    最后由于我们要修改实参phead的指向，以是我们要传二级指针，也就是pphead，有了以上的分析，我们就可以直接上手写代码了，如下：

1. //头删
2. void SLTPopFront(SLTNode** pphead)
3. {
4.         assert(pphead);//这个肯定不能为空
5.         assert(*pphead);//这里是删除函数，所以头结点不能为空，不然空链表没有删除的必要
6.         SLTNode* next = (*pphead)->next;//保存下一个节点
7.         free(*pphead);
8.         *pphead = next;
9. }

复制代码

尾删函数

   当然我们还是要断言两次，由于空链表没有删除的必要
    尾删函数也要思量两种情况，就是链表只有一个节点和多个节点
    当链表有多个节点时，我们起首要找到它的尾节点，以及尾节点的前一个节点，由于释放尾节点后，尾节点的前一个节点就是新的尾节点，我们要找到它，把它的next指针改为空，否则的话新的尾节点指向的就是野指针，如图：
  

   我们再来看看如果链表只有一个节点上面的操作是否可行，由于链表只有一个节点，以是那个节点既是头也是尾，我们释放掉它之后，没有前一个节点，也就不能实现上面的思路，让尾节点的前一个节点的next指针置为空
    以是我们可以特别处置处罚一下，如果链表中只有一个节点，那么就直接释放头结点，然后将头结点置为空，如果链表中有多个节点，那么就实现上面我们分析的思路，我们还是要注意一点，由于可能修改头结点的指向，以是我们要传耳机指针，如下：

1. void SLTPopBack(SLTNode** pphead)
2. {
3.     assert(pphead && *pphead);
4.     if(*pphead->next == NULL)
5.     {
6.         free(*pphead);
7.         *pphead = NULL;
8.         return;
9.     }
10.     SLTNode* ptail = *pphead;
11.     SLTNode* prev = *pphead;
12.     while(ptail->next)
13.     {
14. //循环结束时，prev就是ptail的前一个节点
15.        prev = ptail;
16.        ptail = ptail->next;
17.     }
18.     free(ptail);
19.     ptail = NULL;
20.     prev->next = NULL;
21. }

复制代码

5.查找指定节点

   查找指定节点还是比较简单，我们只必要遍历链表，如果找到匹配的的数据，就返回相应的节点，如果遍历整个链表都没有找到，那就直接返回NULL
    查找函数，不必要修改头节点的指向，本质上是可以传一级指针的，但为了包管我们代码的团体风格，以是这里我们还是传二级指针

1. SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
2. {
3.     assert(pphead && *pphead);//链表不为空才有查找的必要
4.     SLTNode* pcur = *pphead;
5.     while(pcur)//循环找节点
6.     {
7.        if(pcur->data == x)
8.        {
9.           return pcur;
10.        }
11.        pcur = pcur->next;
12.     }
13.     return NULL;//循环结束没找到返回NULL
14. }

复制代码

6.指定节点位置的删除和插入

   指定位置节点的删除和插入一般是配合着查找方法一起使用的，我们使用查找函数去找我们想要删除的数据，然后得到对应的节点， 随后我们就可以通过这个节点来举行删除和插入操作
  删除指定节点

   要删除链表中指定的节点，我们就必须要有链表的头结点，以及要删除的节点，由于要删除的节点可能是头节点，以是有可能会改变头结点的指向，以是我们还是要传二级指针
    起首我们来讨论最常见的情况，就是我们要删除的节点不是头节点也不是尾节点，由于要删除指定的节点，以是我们要找到这个指定节点的前一个节点和后一个节点，在删除后方便将指定节点的前一个节点和后一个节点连接起来
    如果我们要删除的时尾节点时，我们发现上面的思路也是可行的，由于尾节点的下一个节点就是NULL，以是删除尾节点后直接将NULL拿给上一个节点就可以了
    如果我们要删除头节点，这时就必要特别处置处罚了，由于它没有前一个节点，以是我们直接调用头删函数就可以了，具体代码如下

1. //指定位置删除
2. void SLTErase(SLTNode** pphead, SLTNode* pos)
3. {
4.         assert(pphead && pos);//断言pos是否传对
5.         if (pos == *pphead)
6.         {
7.                 SLTPopFront(pphead);//是头结点的情况特殊处理
8.                 return;
9.         }
10.         //pos在中间以及最后的情况
11.         SLTNode* prev = *pphead;
12.         //循环找pos
13.         while (prev->next != pos)
14.         {
15.                 prev = prev->next;
16.         }
17.         //循环结束，找到pos
18.         prev->next = pos->next;
19.         free(pos);
20.         pos = NULL;
21. }

复制代码

在指定节点前插入节点

   由于我们要在指定节点前插入节点，我们就必要得到指定节点的前一个节点，让它的next指针指向新节点，然后让新节点的next指针指向指定节点，这是一般情况下
    在尾结点之前插入节点上述方法也可行，主要是头节点之前没有节点以是不能使用上面的思路，以是我们要特别处置处罚一下，如果指定节点就是头结点，那么我们就调用一下头插就可以了

1. void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDateType x)
2. {
3.         assert(pphead && pos);
4.         if (pos == *pphead)
5.         {
6.                 SLTPushFront(pphead, x);
7.                 return;
8.         }
9.         SLTNode* newnode = SLTBuyNode(x);
10.         SLTNode* prev = *pphead;
11.         while (prev->next != pos)
12.         {
13.                 prev = prev->next;
14.         }
15.         prev->next = newnode;
16.         newnode->next = pos;
17. }

复制代码

在指定节点后插入节点

   在指定节点后插入节点实在更加简单，由于是在指定节点之后插入，并且指定节点存在，那么它肯定有前一个节点，并且根据我们在上面的经验，有没有后一个节点都不紧张，直接插入就可以了
    我们还是简单理一下思路，起首找到指定节点的下一个节点，让指定节点的next指针指向新节点，让新节点的next指针指向指定节点的下一个节点，我们这个时间也可以发现，如果指定节点后面是空，这个思路也没有问题，最后我们来看看代码：

1. void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
2. {
3.         assert(pphead);
4.         SLTNode* newnode = SLTBuyNode(x);
5.         SLTNode* next = pos->next;
6.         pos->next = newnode;
7.         newnode->next = next;
8. }

复制代码

7.链表的销毁

   在上面我们实现了操作链表的各种方法，当然另有一些方法，比如删除指定节点之后的节点，删除之前的节点等等方法，可以自行去实现一下，思路都差不多
    在这里要讲的是，当我们使用完链表之后要对链表举行销毁，由于我们的节点都是通过malloc动态申请过来的，必须要释放，以免造成内存走漏
    销毁的方法也不难，就是遍历链表，只要链表不为空就循环释放节点，关键是我们在释放前要把下一个节点记录下来，如果直接释放了当前节点，那么就找不到下一个节点了，以是我们要把下一个节点生存下来才释放当前节点，代码如下：

1. void SLTDestroy(SLTNode** pphead)
2. {
3.         SLTNode* pcur = *pphead;
4.         while (pcur)
5.         {
6.                 SLTNode* del = pcur;
7.                 pcur = pcur->next;
8.                 free(del);
9.         }
10.         *pphead = NULL;
11. }

复制代码

  那么本日的单链表就讲到这里，单链表还是必要时间去消化的，盼望大家收获多多，bye~~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。