【初阶数据结构】单链表(C语言实现+动图演示)

文章目录

链表的概念及结构

概念： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接次序实现的。

结构：

注意：

1. 从图中可以看出，链表在逻辑上是连续的，但是物理上不一定连续
2. 现实中结点一般是从堆上申请出来的

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8中链表结构

1. 单向或双向

1. 带头或不带头

1. 循环或非循环

虽然有这么多的链表的结构，但我们实际中最常用的就是两种结构：无头单向非循环链表 和 带头双向循环链表

1. 无头单向非循环链表（单链表）：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

今天我们就介绍实现在面试中常考的一种 —— 单链表

链表的实现

链表的单个结点的定义

首先我们需要对单个结点进行定义

typedefint SLTDataType;typedefstructSListNode{
    SLTDataType data;structSListNode* next;}SLTNode;

就像这个图一样，一个空间存放数据，一个空间存放下一个结点的地址

单链表的接口

我们把链表的主要接口写出来，然后我们一 一去实现这些接口：

//打印单链表voidSListPrint(SLTNode* phead);//销毁链表voidSListDestory(SLTNode** pphead);//创建结点
SLTNode*BuySLTNode(SLTDataType x);//头插voidSListPushFront(SLTNode** pphead, SLTDataType x);//尾插voidSListPushBack(SLTNode** pphead, SLTDataType x);//头删voidSListPopFront(SLTNode** pphead);//尾删voidSListPopBack(SLTNode** pphead);//查找
SLTNode*SListFind(SLTNode* phead, SLTDataType x);//在pos位置之前插入voidSListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在pos位置之后插入voidSListInsertAftre(SLTNode* pos, SLTDataType x);// 删除pos位置voidSListErase(SLTNode** pphead, SLTNode* pos);// 删除pos后面位置voidSListEraseAfter(SLTNode* pos);

创建结点

因为我们在头插、尾插以及在pos位置前后进行插入结点之前，都必须申请一个结点，所以我将创建结点也封装成一个函数接口，在需要创建结点时直接调用，代码实现如下：

//创建节点
SLTNode*BuySLTNode(SLTDataType x){
    SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}

注意： 我们创建结点，由于需要自己手动申请内存，所以我们的结点是在堆上开辟的

单链表的头插

首先，我们来实现一个头插的接口，头插就是在链表的头部插入一个结点
在进行头插的时候我们需要考虑一个问题：

1. 这个接口接收的形参应该是一级指针还是二级指针？
2. 此时链表 为空 或者 不为空，是否有区别？

为了更好理解头插，我们先看一个动图展示

看完动图我们可以知到上面的问题。
形参应该是二级指针。为什么呢？（只要涉及到头结点改变的都是，后面不重复说明）

当我们需要进行头插时，我们需申请一个结点，且这个结点要变为头结点。就如上面动图所展示，head开始指向头结点d1,然后指向d3，最后指向d4，d4成为新的头结点。期间我们head指针的指向发生了改变。
因为head本身是一个一级指针，若我们的形参还是一级指针，那么由于形参是实参的一份临时拷贝，形参的改变不会影响实参，所以需使用传参来改变指针的指向只能通过二级指针来改变，一级指针是不行的。

要改谁就传谁的地址

对于头插而言，链表是否为空是不需要考虑的，只需考虑到传二级指针就可以很好实现了 。

代码实现如下：

//头插voidSListPushFront(SLTNode** pphead, SLTDataType x){assert(pphead);
    SLTNode* newnode =BuySLTNode(x);
    newnode->next =*pphead;*pphead = newnode;}

单链表的尾插

尾插就是在链表的尾部插入一个结点，听起来很简单，但我们需要考虑的问题有：

1. 此时链表是否为空，如果为空，我们需要怎么做，不为空有应该怎么做，这里需要分两种情况讨论。
2. 也需要传二级指针

动图展示：

链表为空时：

链表不为空时：

代码实现如下：

//尾插voidSListPushBack(SLTNode** pphead, SLTDataType x){assert(pphead);

    SLTNode* newnode =BuySLTNode(x);if(*pphead ==NULL)//链表为空{*pphead = newnode;}else{//链表不为空//找尾
        SLTNode* tail =*pphead;while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newnode;}}

单链表的头删

头删时链表不能为空，否则就不能进行删除

动图展示：

代码实现如下：

//头删voidSListPopFront(SLTNode** pphead){assert(pphead);assert(*pphead !=NULL);//暴力解决方式/*if (*pphead == NULL)
    {
        return;//温柔解决
    }*/

    SLTNode* tmp =*pphead;*pphead = tmp->next;free(tmp);
    tmp =NULL;}

单链表的尾删

尾删就是删除链表的最后一个结点，听起来很简单，但我们仍需要注意几点：

1. 只有一个结点
2. 多个结点

注意：尾删时链表不能为空，否则无法进行删除

动图演示：

只有一个结点：

多个结点

代码实现：

//尾删voidSListPopBack(SLTNode** pphead){assert(pphead);//链表不能为空，否则无法进行删除assert(*pphead !=NULL);//1.只有一个节点if((*pphead)->next ==NULL){free(*pphead);*pphead =NULL;}//2.多个节点else{//找尾 -- 删除尾结点，但要记录尾结点的前一个节点的位置        
        SLTNode* tail =*pphead;
        SLTNode* prev =*pphead;//记录尾结点的前一个结点//方法一//while (tail->next != NULL)//{//    prev = tail;//    tail = tail->next;//}//free(tail);//tail = NULL;//prev->next = NULL;//方法二while(tail->next->next !=NULL){
            tail = tail->next;}free(tail->next);
        tail->next =NULL;}}

单链表的打印

完成尾插尾删、头插头删，我们就可以实现打印接口了。

链表的打印就是遍历一遍链表，链表遍历和数组有点不一样，链表的遍历是判断当前位置是否为NULL，是就不打印了，不是就打印，通过·cur = cur->next·来移动当前位置。

代码实现如下：

//打印单链表voidSListPrint(SLTNode* phead){
    SLTNode* cur = phead;while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}

单链表的查找

查找也是相当于遍历链表，从头开始遍历，如果找到该数据，则返回该结点的地址，没找到则返回NULL。

由于仅仅时遍历链表，并没有涉及到头结点的改变，所以不需要传二级指针。

代码实现如下：

//查找
SLTNode*SListFind(SLTNode* phead, SLTDataType x){
    SLTNode* cur = phead;while(cur){if(cur->data == x)return cur;
        cur = cur->next;}returnNULL;}

单链表在pos位置之前插入结点

我们在pos位置之前插入结点，需要考虑以下几点：

1. pos位置是头结点该如何插入？
2. pos位置不是头结点该如何插入？
3. pos需要检查是否为空，为空就不能进行操作
4. 若是pos不在链表内则使用断言中断程序

1 . pos位置是头结点：
当pos位置是头结点时，我们在其前面插入结点就相当于头插，调用头插接口即可

if(pos ==*pphead)//pos位置在头节点，相当于头插{//代码复用SListPushFront(pphead, x);}

2 . pos位置不是头结点：
如果pos位置不是头结点，那我们就需要遍历链表找到pos结点的前一个结点，在进行插入

    SLTNode* newnode =BuySLTNode(x);

    SLTNode* prev =*pphead;while(prev->next != pos){
        prev = prev->next;//暴力检查，若pos不在链表中，则prev为空,pos传错了assert(prev);}
    prev->next = newnode;
    newnode->next = pos;

完整代码如下：

//在pos位置之前插入voidSListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){assert(pphead);assert(pos);if(pos ==*pphead)//pos位置在头节点，相当于头插{/*SLTNode* newnode = BuySLTNode(x);
        newnode->next = *pphead;
        *pphead = newnode;*///代码复用SListPushFront(pphead, x);}else{
        SLTNode* newnode =BuySLTNode(x);

        SLTNode* prev =*pphead;while(prev->next != pos){
            prev = prev->next;//暴力检查，若pos不在链表中，则prev为空,pos传错了assert(prev);}
        prev->next = newnode;
        newnode->next = pos;}}

单链表在pos位置之后插入结点

在pos位置之后插入结点就简单很多了，只需判断pos位置是否为空，甚至不需要传链表的指针

代码实现如下：

//在pos位置之后插入voidSListInsertAftre(SLTNode* pos, SLTDataType x){assert(pos);
    SLTNode* newnode =BuySLTNode(x);
    newnode->next = pos->next;
    pos->next = newnode;}

单链表删除pos位置的结点

在删除pos位置的结点时，我们需要考虑pos位置是否在头结点
是头结点时，等于头删
不是头结点，那我们就需要遍历链表找到pos结点的前一个结点，在进行删除

代码实现如下：

voidSListErase(SLTNode** pphead, SLTNode* pos){assert(pphead);assert(pos);//pos位置不能为空if(pos ==*pphead)//头删{SListPopFront(pphead);}else{
        SLTNode* prev =*pphead;while(prev->next != pos){
            prev = prev->next;}
        prev->next = pos->next;free(pos);//pos = NULL; //无意义，因为传过来的不是二级指针，形参的改变不影响实参//可以在使用的时候，自己置空}}

单链表删除pos位置之后的结点

删除pos位置下一个的结点，只需将pos->next指向下一个的下一个即可，但我们要注意的是，pos位置不能是尾结点，否接就会造成内存非法访问问题。

代码实现如下：

// 删除pos后面位置voidSListEraseAfter(SLTNode* pos){assert(pos);assert(pos->next !=NULL);

    SLTNode* tmp = pos->next;
    pos->next = tmp->next;free(tmp);}

单链表的销毁

链表的销毁也是依靠遍历来完成的，一个一个的销毁。

//销毁voidSListDestory(SLTNode** pphead){assert(pphead);

    SLTNode* cur =*pphead;while(cur !=NULL){
        SLTNode* next = cur->next;free(cur);
        cur = next;}*pphead =NULL;}

总结

单链表在逻辑上是连续的，但在物理上不一定连续，可以做到按需所取，但不支持随机访问。

上述实现单链表是传的二级指针，若不想传二级指针，可以使用以下两种方法：

1.使用带头结点的链表，链表没有元素时头指针指向头结点，不需要对头指针修改
2. 调用函数时以返回值的形式返回头指针，让头指针在调用时赋值（非常麻烦）

完整代码

代码保存在码云上：单链表