【数据结构】链表全解析
·
目录
前言
在上篇顺序表文章末尾(【数据结构】顺序表)，我们留了几个问题，主要是道出了顺序表的不足之处，例如，插入数据困难，要不断申请空间，而且会有空间浪费。
那么，有没有一种结构，可以较好的解决这几个问题呢？这就要提到我们今天的主角——链表。
1.链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
与顺序表不同，使用链表存储的数据元素，其物理存储位置是随机的。
应该怎么理解呢？
日常生活中的火车可以较为形象的表示链表结构。火车是由许多节车厢连接而成的的，同时，火车如果要卸下/加装某一节车厢的话，只需要将其中一节断开/插入即可。所以火车就像是用许多链条串起来的一样，可以近似表示链表。
那么，链表的结构到底是什么样子呢？
链表节点至少需要两个成员，一个是指向下一个元素的指针，这个指针所在的区域，我们称为指针域，另一个是要储存的数据，储存数据的区域，我们叫数据域。
所有链表节点(火车的节)串在一起，我们就叫它链表(火车)。
我们从两个角度去理解，一种是逻辑结构，一种是物理结构。
逻辑结构：
相当于，每一个元素都指向着后面的元素。
物理结构：
这是内存中实实在在的结构，一个链表节点可以分为数据域和指针域，指针域中存放着下一个链表节点的地址，通过这个地址，我们就可以找到下一个链表节点。
总结一下：
1.链表在逻辑上是连续的，但在物理储存结构一般上不连续。
2.链表的空间一般都是动态内存开辟的。
2.链表的分类
1.根据链表的指向，可以分为单向和双向。
单向：
双向：
2.根据有无哨兵位节点，可以分为带头和不带头。
哨兵位，主要的作用是让链表有头节点，同样是链表节点，但是不储存有效数据。
plist所指向的就是一个哨兵位，从哨兵位下一个起，才是有效数据。
带头：
不带头：
3.根据最后一个链表节点是否指向第一个节点，可以分为循环和非循环。
循环：
非循环：
根据这三种分法，我们可以排列组合出八种不同的链表。
本文主要讲解两种常用的链表：不带头单向非循环链表和带头双向循环链表
3.不带头单向非循环链表
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
这类结构一般在OJ题目中出现的比较多，因为它的结构最简单，所以，缺陷也就越大，经常会有很多问题。
3.1 不带头单向非循环链表的结构
typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;这个结构很简单，这里不过多赘述，上文的例子都是这种结构，不太理解的同学可以结合代码和上文图片在纸上画一画。
3.2 不带头单向非循环链表的接口函数
所有接口函数：
// 链表数据打印
void SListPrint(SLTNode* phead);
// 尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
// 头插
void SListPushFront(SLTNode** pphead, SLTDataType x);
// 尾删
void SListPopBack(SLTNode** pphead);
// 头删
void SListPopFront(SLTNode** pphead);
// 数据查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
// 在pos位置之后去插入一个节点
void SListInsertAfter(SLTNode* pos, SLTDataType x);
// 在pos位置之前去插入一个节点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SListInsert1(SLTNode** pphead, int pos, SLTDataType x);
// 删除pos节点
void SListErase(SLTNode** pphead, SLTNode* pos);
void SListErase1(SLTNode** pphead, int pos);
// 删除pos之后的节点
void SListEraseAfter(SLTNode* pos);
// 链表销毁
void SListDestroy(SLTNode** pphead);
可以看到参数传的都是二级指针，为什么呢？
因为不带头链表的头节点随时可能被头插，头删等操作更换，所以必须要传二级指针来保证头节点地址会随着这些操作变更，也即要将头节点的地址传回去。
链表节点申请及链表的打印，销毁
SLTNode* BuyListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("BuyListNode"); exit(-1); } newnode->data = x; newnode->next = NULL; return newnode; }先开辟一个动态空间，判断不为空后，将数据放到新开辟的节点中，再返回节点的地址。
void SListDestroy(SLTNode** pphead) { SLTNode* next = *pphead; while (*pphead) { next = (*pphead)->next; free(*pphead); *pphead = next; } }遍历链表，只要 *pphead 不为空，也就是链表不指向空，就继续释放。
void SListPrint(SLTNode* plist) { assert(plist); while (plist) { printf("%d ", plist->data); plist = plist->next; } }也是一样的操作，遍历链表即可，这里不用传二级指针是因为不用改变头指针的值。
链表插入元素
根据添加位置不同，可分为以下 3 种情况：
- 插入到链表的头部（头节点之后），作为首元节点；
- 插入到链表中间的某个位置；
- 插入到链表的最末端，作为链表中最后一个数据元素；
无论什么情况还是分两步走：
- 先让新节点的 next 指向插入位置的节点；
- 再让插入位置前的节点 next 指向新节点。
具体实现：
普通插入：
//传递指针版 void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); SLTNode* newnode = BuyListNode(x); if (pos == *pphead) { newnode->next = *pphead; *pphead = newnode; } else { SLTNode* cur = *pphead; while (cur->next != pos) { cur = cur->next; } newnode->next = pos; cur->next = newnode; } } //传递下标版 void SListInsert1(SLTNode** pphead, int pos, SLTDataType x)//第一个节点序数为0 { assert(pphead); SLTNode* posPrev = *pphead; SLTNode* newnode = BuyListNode(x); if (pos == 0) { newnode->next = *pphead; *pphead = newnode; } else { for (int i = 0; i < pos - 1; i++) { if (!posPrev) { return; } posPrev = posPrev->next; } newnode->next = posPrev->next; posPrev->next = newnode; }两种插入方式都可以，看自己喜好。
值得注意的是，当进行头部插入时，要改变头指针的值，这里也解释了为什么要传递二级指针，因为如果传递一级指针改变的是头指针的临时拷贝，并不能改变头指针。
如果了解了插入的原理，我们就可以把剩下的插入都写出来了
在插入位置之后插入：
void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode; }我们发现这次的就不用传递二级指针，因为不会改变头指针的值，而且代码少得多，说明单链表不适合前插，但是适合尾插。
尾插：
void SListPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuyListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
头插：
void SListPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuyListNode(x); newnode->next = *pphead; *pphead = newnode; }
链表删除元素
无论删除哪个节点都可以分为三步：
- 保存被删除节点后的节点的地址；
- 释放被删除节点；
- 连接被删除节点前的节点和被删除节点后的节点。
普通删除：
void SListErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(*pphead); assert(pos); if (pos == *pphead) { *pphead = (*pphead)->next; free(*pphead); } else { SLTNode* posPrev = *pphead; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = pos->next; free(pos); pos = NULL; } }删除pos之后的节点：
void SListEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* next = pos->next->next; free(pos->next); pos->next = next; }头删：
void SListPopFront(SLTNode** pphead) { assert(pphead); assert(*pphead); SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }尾删：
void SListPopBack(SLTNode** pphead) { assert(pphead); assert(*pphead); if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
链表元素查找
查找方法：
一般就是遍历链表，如果找到，返回该链表节点的地址或者下标，未找到，返回NULL。
SLTNode* SListFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* pos = phead; while (pos) { if (pos->data == x) { return pos; } pos = pos->next; } return NULL; }这里给出，返回地址的写法，大家可以自己试着写一下返回下标的写法。
3.3 不带头单向非循环链表的全部代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* plist)
{
assert(plist);
while (plist)
{
printf("%d ", plist->data);
plist = plist->next;
}
}
SLTNode* BuyListNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("BuyListNode");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
assert(phead);
SLTNode* pos = phead;
while (pos)
{
if (pos->data == x)
{
return pos;
}
pos = pos->next;
}
return NULL;
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
if (pos == *pphead)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
newnode->next = pos;
cur->next = newnode;
}
}
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if (pos == *pphead)
{
*pphead = (*pphead)->next;
free(*pphead);
}
else
{
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);
pos = NULL;
}
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next->next;
free(pos->next);
pos->next = next;
}
void SListDestroy(SLTNode** pphead)
{
SLTNode* next = *pphead;
while (*pphead)
{
next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
void SListInsert1(SLTNode** pphead, int pos, SLTDataType x)//第一个节点序数为0
{
assert(pphead);
SLTNode* posPrev = *pphead;
SLTNode* newnode = BuyListNode(x);
if (pos == 0)
{
newnode->next = *pphead;
*pphead = newnode;
}
else
{
for (int i = 0; i < pos - 1; i++)
{
if (!posPrev)
{
return;
}
posPrev = posPrev->next;
}
newnode->next = posPrev->next;
posPrev->next = newnode;
}
}
void SListErase1(SLTNode** pphead, int pos)
{
assert(pphead);
assert(*pphead);
if (pos == 0)
{
SLTNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
else
{
SLTNode* next = *pphead;
for (int i = 0; i < pos - 1; i++)
{
if (!next)
{
return;
}
next = next->next;
}
SLTNode* tmp = next->next->next;
free(next->next);
next->next = tmp;
}
}4.带头双向循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了
4.1 带头双向循环链表的结构
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;
其实就是双向链表的结构，带头和循环还得靠我们初始化实现。
4.2 带头双向循环链表的接口函数
链表的初始化和销毁
初始化要完成两件事：
- 为头节点开辟空间
- 让头结点的next 和prev 指针指向自己，并返回头节点地址
LTNode* ListInit() { LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); if (phead == NULL) { exit(-1); } phead->next = phead; phead->prev = phead; return phead; }
销毁：
由于循环链表不会指向NULL，所以用头节点作为遍历结束的标志。
所以要先释放掉保存有效数据的节点，再释放头节点。
void ListDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* nextNode = cur->next; free(cur); cur = nextNode; } free(phead); phead = NULL; }
链表插入元素
我们发现，
- 要将双新节点先与其直接后继节点建立双层逻辑关系，新节点的直接前驱节点与之建立双层逻辑关系
- 头部插入变为了在头节点后插入，所以怎么改变都不会影响头节点，可以只传一级指针。
- 中间插入基本没什么变化
- 尾部插入变成了在头节点前插入，与尾节点和原尾节点之间要建立双重逻辑关系。
普通插入：
void ListInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* Prev = pos->prev; Prev->next = newnode; newnode->prev = Prev; newnode->next = pos; pos->prev = pos; }用普通插入直接实现尾插和头插。
尾插：
void ListPushBack(LTNode* phead, LTDataType x) { ListInsert(phead->prev, x); }头插：
void ListPushFront(LTNode* phead, LTDataType x) { ListInsert(phead->next, x); }
链表删除元素
双链表删除结点时
- 只需拿到要删除的节点，然后将该节点从表中摘除；
- 建立被删除节点前后节点的双向联系即可。
普通删除：
void ListErase(LTNode* pos) { assert(pos); assert(pos->next != pos);//保证链表不为空 LTNode* next = pos->next; LTNode* prev = pos->prev; free(pos); pos = NULL; prev->next = next; next->prev = prev; }用普通删除函数实现尾删和头删。
尾删：
void ListPopBack(LTNode* phead) { ListErase(phead->prev); }头删：
void ListPopFront(LTNode* phead) { ListErase(phead->next); }
链表的查找和打印
两者逻辑大致相同
- 首先遍历链表，查找函数遇到所要找的节点停止，并返回此节点的地址；
- 遇到头节点停止遍历，查找函数遇到头节点代表未找到，返回NULL。
打印：
void ListPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next;//记得要推进循环 } printf("\n"); }查找：
LTNode* ListFind(LTNode* phead, LTDataType x) { assert(phead); assert(phead->next != phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
4.3 带头双向循环链表的全部代码
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* ListInit()
{
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
exit(-1);
}
phead->next = phead;
phead->prev = phead;
return phead;
}
LTNode* BuyListNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;//记得要推进循环
}
printf("\n");
}
void ListDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* nextNode = cur->next;
free(cur);
cur = nextNode;
}
free(phead);
phead = NULL;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* Prev = pos->prev;
Prev->next = newnode;
newnode->prev = Prev;
newnode->next = pos;
pos->prev = pos;
}
void ListErase(LTNode* pos)
{
assert(pos);
assert(pos->next != pos);
LTNode* next = pos->next;
LTNode* prev = pos->prev;
free(pos);
pos = NULL;
prev->next = next;
next->prev = prev;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
ListInsert(phead->prev, x);
}
void ListPopBack(LTNode* phead)
{
ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, LTDataType x)
{
ListInsert(phead->next, x);
}
void ListPopFront(LTNode* phead)
{
ListErase(phead->next);
}
5.顺序表和链表的对比
关于高速缓存：
后记
我们用了两篇文章，讲述了顺序表和链表，接下来，我们就要讲到它们的应用了。
我在函数栈帧中讲过，栈是一种后进先出的结构，那么这种特性如何用我们学过的两种结构实现呢？
大家可以用这两种结构试一试。
tips：主要是接口函数的实现。
以上就是本次的分享内容了，喜欢我的分享的话，别忘了点赞加关注哟！
如果你对我的文章有任何看法，欢迎在下方评论留言或者私信我鸭！
我是白晨，我们下次分享见！！！
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
25
0- 0
已为社区贡献2条内容
所有评论(0)