数据结构—＞带你深入了解单链表（基础篇）

✅作者���介：大家好，我是橘橙黄又青，一个想要与大家共同进步的男人

个人主页：橘橙黄又青-CSDN博客

前面我们学习了顺序表，今天我们来学习与顺序表类似的单链表

1.什么是链表

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。 ⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状 态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？ 最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。 那在在链表⾥，每节“⻋厢”是什么样的呢？ 与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分： 当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。 图中指针变量 plist保存的是第⼀个节点的地址，我们称plist此时“指向”第⼀个节点，如果我们希 望plist“指向”第⼆个节点时，只需要修改plist保存的内容为0x0012FFA0。

 

结合前⾯学到的结构体知识，我们可以给出每个节点对应的结构体代码： 假设当前保存的节点为整形： 代码：

struct SListNode{ int data; //节点数据 struct SListNode* next; //指针变量⽤保存下⼀个节点的地址};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个节点的地址（当下⼀个节点为空时保存的地址为空）。 当我们想要从第⼀个节点⾛到最后⼀个节点时，只需要在前⼀个节点拿上下⼀个节点的地址（下⼀个 节点的钥匙）就可以了。

 2. 链表的打印

那给定的链表结构中，如何实现节点从头到尾的打印？

看图：

代码：

//打印void SLTPrint(SLTNode* phead) {SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//开辟空间SLTNode* SLTBuyNode(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、节点⼀般是从堆上申请的 3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

 前面简单学习打印，接下来我们进入单链表的增，删，查。

3，单链表的基础应用

 这里我们介绍一下我的单链表代码：

typedef int SLTDataType;//链表是由节点组成typedef struct SListNode{SLTDataType data;struct SListNode* next;}SLTNode;

创建一个这样的空间链表： 

3.1链表的尾插

代码展示：

void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，新节点作为pheadif (*pphead == NULL) {*pphead = newnode;return;}//链表不为空，找尾节点    //创建代跑变量SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail就是尾节点ptail->next = newnode;}

 图片展示：

值得注意的是开辟的空间next是指向nuLL的 

 

3.2链表的头插

代码展示：

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

图片展示： 

3.3链表的头删

代码：

void SLTPopFront(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头结点释放掉SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}

思路：

3.4链表的尾删

代码：

void SLTPopBack(SLTNode** pphead) {assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点，有多个节点if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;return;}SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next)//找尾节点{prev = ptail;ptail = ptail->next;}prev->next = NULL;//销毁尾结点free(ptail);ptail = NULL;}

 把尾节点释放掉，置为空

3.5链表的查找

代码:

//查找SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {assert(pphead);//遍历链表SLTNode* pcur = *pphead;while (pcur) //等价于pcur != NULL{if (pcur->data == x) {return pcur;}pcur = pcur->next;}//没有找到return NULL;}

这个也是很简单，遍历链表，有就返回，无返回空。 

3.6链表在指定位置之前插入数据

代码：

//在指定位置之前插入数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode = SLTBuyNode(x);//pos刚好是头结点if (pos == *pphead) {//头插SLTPushFront(pphead, x);return;}//pos不是头结点的情况SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev -> newnode -> posprev->next = newnode;newnode->next = pos;}

思路：

 

插入代码就在上面啦。 

 

3.7链表在指定位置之后插入数据

代码：

//在指定位置之后插入数据void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;}

但是这里要注意了：

思路：

 

3.8删除pos节点

 代码：

//删除pos节点void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);assert(pos);//pos刚好是头结点，没有前驱节点，执行头删if (*pphead == pos) {//头删SLTPopFront(pphead);return;}SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}

 思路：

3.9删除pos之后的节点

代码：

//删除pos之后的节点void SLTEraseAfter(SLTNode* pos) {assert(pos);//pos->next不能为空assert(pos->next);//pos  pos->next  pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;}

思路：

 

3.10销毁链表

堆销毁很重要，创建链表也要学会销毁链表

 代码：

//销毁链表void SListDesTroy(SLTNode** pphead) {assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;}

解释：

创建带跑指针，把下一个节点地址记录下来，释放原来第一个节点空间，再把下一个节点地址给带跑指针。

好啦，我们今天就讲到这里，喜欢就点一个赞吧，感谢观看。