【初阶数据结构与算法】线性表之单链表的定义与实现

一、单链表的概念与结构

1.单链表的概念

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

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

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

2.单链表的节点

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

typedef int SLDateType;typedef struct SListNode
{SLDateType data;struct SListNode* next;
}SLTNode;

   在我们定义的这个节点结构中，有两个成员，一个是我们所存放的数据data，由于我们一个节点的下一个节点也是一个这样的结构体，所以指向下一个节点的指针是一个结构体指针，也就是类型为struct SListNode*的指针
   由于我们现在要实现的是单链表，所以它的节点名称就可以叫做SListNode，其中S是single的缩写，翻译出来就是单链表，为了以后不用每次使用这个结构体就要加上struct，我们就又给它取了一个别名SLTNode方便使用
   然后由于我们不知道要存放的数据是什么类型，所以我们这里typedef一个类型来取代，以后如果想要更改类型只需要在这里更改
   我们再次总结一下链表节点的特点，链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点

3.链表的性质

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

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

二、单链表的实现

1.结构准备

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

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDateType;typedef struct SListNode
{SLDateType data;struct SListNode* next;
}SLTNode;

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

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

打印函数

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

void SLTPrint(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

节点申请函数

   在顺序表中我们空间不够时需要一个扩容函数，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组进行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接避免了空间浪费
   节点申请函数的名称一般很有意思，就叫SLTBuyNode，就像我们向操作系统买了一个节点一样，非常形象生动，了解函数名后我们来分析具体实现思路
   它的参数只有一个，就是我们申请一个节点后，新节点要存放的数据，返回值就是节点指针，因为我们最后要用malloc向操作系统要一个节点大小的空间，要返回指向这个节点的地址
   使用节点申请了节点后，我们就把这个节点的数据部分该成我们传过来的参数，它的next指针就置为空指针NULL，最后把这个节点地址返回，具体代码如下：

SLTNode* SLTBuyNode(SLDateType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}

3.链表的头插和尾插

头插函数

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

   有了画图分析，我们这下可以直接写出代码了，如下：

void SLTPushFront(SLTNode** pphead, SLDateType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

   最后我们来分析一下头插函数的时间复杂度，我们没有创建任何循环，时间复杂度仅为O(1)，是非常高效的

尾插函数

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

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

void SLTPushBack(SLTNode** pphead, SLTDateType x)
{assert(pphead);SLTNode* newnode = BuyNode(x);if(*pphead == NULL){*pphead = newnode;}SLTNode* ptail = *pphead;while(ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

4.链表的头删和尾删

头删函数

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

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

void SLTPopFront(SLTNode** pphead)
{//这里除了pphead不能为空//由于是删除函数，所以头节点不能为空//也就是*pphead也不能为空assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

尾删函数

   尾删函数也要考虑两种情况，就是链表只有一个节点和多个节点，当然，如果一个节点都没有肯定是不行的，所以要像头删函数一样断言一下最好
   当链表有多个节点时，我们首先要找到它的尾节点，以及尾节点的前一个节点，因为释放尾节点后，尾节点的前一个节点就是新的尾节点，我们要找到它，把它的next指针改为空，否则的话新的尾节点指向的就是野指针，如图：

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

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);if(*pphead->next == NULL){ free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = *pphead;while(ptail->next){
//循环结束时，prev就是ptail的前一个节点prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;
}

5.查找指定节点

   查找指定节点还是比较简单，我们只需要遍历整个链表，如果找到匹配的数据，那么就把直接返回那个节点，如果链表遍历完之后还是没有找到那个节点，说明没有找到，直接返回空即可
   查找函数其实只需要一级指针就够用了，但是前面所有函数都是传的二级指针，为了保证传参的一致性，我们就还是传二级指针，影响不大，如下：

SLTNode* SLTFind(SLTNode** pphead, SLTDateType x)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while(pcur){if(pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

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

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

删除指定节点

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

void SLTErase(SLTNode**　pphead, SLTNode* pos)
{assert(pphead && *pphead && pos);if(pos == *pphead){SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while(prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

在指定节点前插入节点

   由于我们要在指定节点前插入节点，我们就需要得到指定节点的前一个节点，让它的next指针指向新节点，然后让新节点的next指针指向指定节点，这是一般情况下
   在尾结点之前插入节点上述方法也可行，主要是头节点之前没有节点所以不能使用上面的思路，所以我们要特殊处理一下，如果指定节点就是头结点，那么我们就调用一下头插就可以了，我们就不画图了，相信大家到这个位置了肯定对链表有了一定的认识了
   接下来我们来看看代码：

void SLTInsertFront(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead && pos);if (pos == *pphead){SLTPushFront(pphead, x);return;}SLTNode* newnode = SLTBuyNode(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;
}

在指定节点后插入节点

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

void SLTInsertBack(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);SLTNode* next = pos->next;pos->next = newnode;newnode->next = next;
}

7.链表的销毁

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

void SLTDestroy(SLTNode** pphead)
{SLTNode* pcur = *pphead;while (pcur){SLTNode* del = pcur;pcur = pcur->next;free(del);}*pphead = NULL;
}

   那么本篇文章的分享就到这里就结束啦，这节课我们主要介绍了一下单链表，并且由于第一次接触到单链表这种结构可能有点懵，所以我们没有讲链表的分类，在下一篇文章会介绍，先了解并实现单链表就已经很厉害了
   最后如果有什么问题欢迎私信我，有什么不对的地方也欢迎纠正
   bye~