【数据结构】单链表（一）

上一篇【数据结构】顺序表-CSDN博客  我们了解了顺序表，但是呢顺序表涉及到了一些问题，比如，中间/头部的插入/删除，时间复杂度为O(N);增容申请空间、拷贝、释放旧空间会有不小的消耗；增容所浪费的空间... 我们如何去解决这些问题？本篇介绍另一个数据结构——链表

1. 链表的概念及结构

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

链表大概是什么样的呢？看下图

链表是由一个一个的节点组成，再顺序表中，数据是连续存放的，我们想找到下一个数据顺着前一个数据找就行了，而链表中数据存放空间是不连续的，所以我们就需要一个指针来保存下一个节点的地址，所以，我们如果要定义链表，只需要定义链表的节点结构就行了

(在【C语言】结构体详解-CSDN博客 的1.3 结构体的自引用 中介绍过)

struct SListNode
{int data;//数据struct SListNode* next;//下一个数据的地址
};

和上一篇一样，创建一个头文件，两个源文件

 也是一样，在头文件SList.h中定义单链表的结构，并对类型和结构体改名

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Type; 
//定义节点结构
typedef struct SListNode
{Type data;struct SListNode* next;
}SLNode;

我们先创建几个节点，在test.c中实现

#include "SList.h" //包含头文件
void SListtest1()
{SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1node1->data = 1;//赋值SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2node2->data = 2;//赋值SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3node3->data = 3;//赋值SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4node4->data = 4;//赋值
}
int main()
{SListtest1();return 0;
}

虽然我们创建好了节点，但是这几个节点现在还不能互相找到，所以我们接下来要将这几个节点连接起来，怎么连接？存下一个节点的地址

void SListtest1()
{SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1node1->data = 1;//赋值SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2node2->data = 2;//赋值SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3node3->data = 3;//赋值SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4node4->data = 4;//赋值//将四个节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;
}

现在就构成了一个链表，有了这个简单的链表，我们来写一个函数打印一下里面的数据

链表的打印

在SList.h中进行函数的声明

void SLPrint(SLNode* ps);//打印

参数是链表的节点的地址 

在SList.c中进行函数的实现

#include "SList.h"
void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向当前链表的第一个节点
}

要打印当然就要循环遍历，写一个while循环，判断条件为pcur，不为NULL进入循环 

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向当前链表的第一个节点while (pcur) //判断第一个节点是否为NULL{//....}
}

 进入循环后打印内容

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向当前链表的第一个节点while (pcur){printf("%d->", pcur->data);//打印内容}
}

打印完一个数据后，要把下一个节点值部分的地址给pcur ，也就是pcur要存node2中2的地址，此时pcur不再指向node1，指向了node2

void SLPrint(SLNode* ps) //打印
{SLNode* pcur = ps;//pcur指向当前链表的第一个节点while (pcur){printf("%d->", pcur->data);//打印内容pcur = pcur->next;//指向下一个节点}printf("NULL\n");
}

在test.c中测试

测试时我们不直接传链表的第一个节点node1，而是再定义一个结构体指针plist去指向node1，让plist作为参数传过去

    SLNode* plist = node1;SLPrint(plist);

虽然有点多此一举，但这样会让我们的代码更完善 

运行结果

 2.链表的插入

实际使用链表的时候我们不会像上面那样一个一个创建，初始时候是一个空链表，会跟顺序表类似进行空间开辟然后插入数据

2.1空间申请创建节点

插入数据前依旧是要判断空间够不够

在SList.h中进行函数的声明

SLNode* SLBuyNode(Type x);//申请空间创建节点

返回值是节点的地址，参数就是要插入的数据

在SList.c中进行函数的实现

SLNode* SLBuyNode(Type x)//申请空间创建节点
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL) //空间申请失败{perror("malloc");return 1;}newnode->data = x;newnode->next = NULL;return newnode;
}

2.2 尾插

在SList.h中进行函数的声明

void SLPushBack(SLNode** ps, Type x);//尾插

参数是链表的节点地址，是一个二级指针，和要插入的数据

我们要给函数传地址，这样形参的改变才能影响实参，对参数的理解如下，这很重要，这里提前展示将要在test.c中测试用的部分代码 

在SList.c中进行函数的实现

尾插要先找到尾节点，再将尾节点和新节点连接起来 ，此时node4的地址部分就不再是NULL 而是新节点的地址

代码如何实现呢 ？先找尾节点

void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* ptail = ps;//定义尾节点，开始时指向头节点while (ptail->next != NULL)//遍历链表数据，找尾节点{ptail = ptail->next;}//跳出循环后ptail指向尾节点
}

然后我们直接调用创建节点的函数，放在找尾节点前面，最后赋值

void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* newnode = SLBuyNode(x);//申请空间创建节点SLNode* ptail = ps;//定义尾节点，开始时指向头节点while (ptail->next != NULL)//遍历链表数据，找尾节点{ptail = ptail->next;}//跳出循环后ptail指向尾节点ptail->next = newnode;//直接赋值
}

 但是呢，链表在没有赋值的时候是空链表，所以我们要讨论空链表的情况，如果是空链表，直接让ps指向新节点newnode，所以最终的代码如下

void SLPushBack(SLNode** pps, Type x)//尾插
{assert(pps);//pps不可以为NULLSLNode* newnode = SLBuyNode(x);//申请空间创建节点if (*pps == NULL) //*pps可以为NULL，表示空链表{*pps = newnode;}else //非空链表{SLNode* ptail = *pps;//定义尾节点，开始时指向头节点while (ptail->next)//遍历链表数据，找尾节点{ptail = ptail->next;}//跳出循环后ptail指向尾节点ptail->next = newnode;//直接赋值}
}

我们再来看test.c中测试的代码

void SListtest2()
{SLNode* plist = NULL;//空链表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//打印
}
int main()
{//SListtest1();SListtest2();return 0;
}

多插入几个数据，运行看结果，插入成功

2.3 头插

 在SList.h中进行函数的声明

void SLPushHead(SLNode** pps, Type x);//头插

同样的，参数也是一个二级指针，还有要插入的数据

在SList.c中进行函数的实现

我们需要做两件事，一个是将newnode和原本的首节点连接在一起，另一件事是*pps要指向新的首节点 

 链表不为NULL时，代码如下

void SLPushHead(SLNode** pps, Type x)//头插
{assert(pps);//pps不能为NULLSLNode* newnode = SLBuyNode(x);//申请空间创建节点newnode->next = *pps;*pps = newnode;
}

当链表为NULL时，分析一下

当前代码也可以实现

在test.c中测试

void SListtest2()
{SLNode* plist = NULL;//空链表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//打印SLPushHead(&plist, 6);//头插SLPushHead(&plist, 7);SLPushHead(&plist, 8);SLPrint(plist);//打印
}

看一下运行结果

3.链表的删除

删除数据，链表就不能为空，不然删啥呢?

 3.1 尾删

在SList.h中进行函数的声明

void SLPopBack(SLNode** pps);//尾删

在SList.c中进行函数的实现

很显然，首先就是找尾节点，找到尾节点之后直接释放吗？node4释放后node3->next里面依然存放着node4的地址，但此时指向的空间已经没了，此时的指针就成了一个野指针 ，所以我们还要将被释放节点的前一个节点的指针置空

所以我们还要找尾节点的前一个节点

void SLPopBack(SLNode** pps)//尾删
{assert(pps && *pps);//pps和链表都不能为空SLNode* prev = *pps;//定义尾节点前一个节点SLNode* ptail = *pps;//定义尾节点while (ptail->next){prev = ptail;ptail = ptail->next;}//此时找到了尾节点和尾节点前一个节点free(ptail);//释放尾节点ptail = NULL;//置空prev->next = NULL;//置空尾节点前一个节点
}

如果这个链表只有一个节点呢，这个代码可行吗？来分析一下

我们把节点释放并置空后，prev->next就不存在了，函数最后一句代码就不能实现，所以，当链表里只有一个节点时，直接释放就行了

void SLPopBack(SLNode** pps)//尾删
{assert(pps && *pps);//pps和链表都不能为空if ((*pps)->next == NULL)//链表只有一个节点{free(*pps);//释放节点*pps = NULL;//置空}else //链表不止一个节点{SLNode* prev = *pps;//定义尾节点前一个节点SLNode* ptail = *pps;//定义尾节点while (ptail->next){prev = ptail;ptail = ptail->next;}//此时找到了尾节点和尾节点前一个节点free(ptail);//释放尾节点ptail = NULL;//置空prev->next = NULL;//置空尾节点前一个节点}
}

在test.c中测试

void SListtest2()
{SLNode* plist = NULL;//空链表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPrint(plist);//打印SLPushHead(&plist, 6);//头插SLPushHead(&plist, 7);SLPrint(plist);//打印SLPopBack(&plist);//尾删SLPrint(plist);//打印
}

看下结果，尾删成功

3.2 头删

在SList.h中进行函数的声明

void SLPopHead(SLNode** pps);//头删

在SList.c中进行函数的实现

我们要删除头节点，跟删除尾节点不一样，如果我们把首节点释放掉，还能找到首节点里的next吗？不能，不能的话就找不到第二个节点以及剩下的节点

我们应该先把下一个节点的信息存储起来

SLNode* Next = (*pps)->next;//存节点

 然后把原头节点释放

free(*pps);

最后让*pps指向新的头节点

*pps = Next;

所以代码如下

void SLPopHead(SLNode** pps)//头删
{assert(pps && *pps);//pps和链表都不能为空SLNode* Next = (*pps)->next;//存节点free(*pps);*pps = Next;
}

当链表只有一个节点时，分析一下，上面的代码也是可以完成的

我们在test.c中测试一下

void SListtest2()
{SLNode* plist = NULL;//空链表SLPushBack(&plist, 1);//尾插SLPushBack(&plist, 2);SLPrint(plist);//打印SLPushHead(&plist, 6);//头插SLPushHead(&plist, 7);SLPrint(plist);//打印SLPopBack(&plist);//尾删SLPrint(plist);//打印SLPopHead(&plist);//头删SLPrint(plist);//打印
}

下篇我们再继续介绍更多内容，拜拜~