数据结构——链表
目录
轻松无痛玩转链表
链表基础知识
链表的概念
链表是一种常见的数据结构，用于线性方式存储数据。链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
基本特点
- 动态大小：链表的大小可以在运行时动态变化，不需要在创建时指定固定的大小。
- 元素连接：每个元素（通常称为节点）存储数据，并包含一个或多个指针指向列表中的其他节点。
- 无需连续内存：由于元素通过指针连接，它们不需要在内存中连续存放，这使得内存使用更加灵活。
- 插入和删除操作：在链表中插入或删除节点通常比数组更快，因为这些操作不需要移动其他元素。
分类
1.单向与非单向
2.带头与非带头（有没有哨兵节点）
哨兵节点就是一个存储非有效数据的虚拟节点，他不是数据结合的一部分，可以简化删除操作，避免空链表，统一处理逻辑。
3.循环与非循环
常见的链表就有不带头单向非循环链表和带头双向循环链表。
基本操作（接口）
- 插入：在链表的特定位置添加新节点。
- 删除：移除链表中的特定节点。
- 搜索：查找链表中的特定值。
- 遍历：按顺序访问链表的所有节点。
所以总的来说，链表适用于当数据结合频繁变化，需要快速插入和删除，内存空间分散的场景。
单链表的实现
单链表也就是不带头单向非循环链表。
定义
//方便后续更改类型 typedef int SLTDataType; //定义链表节点 typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;创建新节点
//创建新节点 SLTNode* SLTCreateNode(SLTDataType x) { //malloc出一个节点 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc"); exit(1); } //赋值 newnode->data = x; newnode->next = NULL; return newnode; }增、删、查、改操作
尾插
只需要在链表末尾增添节点，修改指针就可以了。
//尾插 void SLTPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); //先创造一个新节点 SLTNode* newnode = SLTCreateNode(x); //空链表的情况 if (*pphead == NULL) { *pphead = newnode; } else { //非空链表 //找到尾节点 SLTNode* ptail = *pphead; while (ptail->next) { ptail = ptail->next; } ptail->next = newnode; } }细节：因为涉及到phead指针的修改，所以参数得传二级指针。
（*pphead == phead）
找到尾节点需要判断当前节点的下一节点是否为空。（ptail->next）
所以总的来说，尾插需要注意三点。
1.不要忘记链表为空的情况。
2.传phead的二级指针。
3.找尾节点。
头插
头插非常简单，创建新节点，然后链接在链表头部就行。
//头插 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //先创造一个新节点 SLTNode* newnode = SLTCreateNode(x); newnode->next = *pphead; *pphead = newnode; }尾删
要注意判断只有一个节点的情况和判断链表为空的情况（assert(pphead && *pphead)）。
//尾删 void SLTPopBack(SLTNode** pphead) { assert(pphead && *pphead); //只有一个节点的情况 if ((*pphead)->next == NULL)//->运算符优先级高于* { free(*pphead); *pphead = NULL; } else { //找到尾节点以及上一个节点 SLTNode* ptail = *pphead; SLTNode* prev = *pphead; while (ptail->next) { prev = ptail; ptail = ptail->next; } prev->next = NULL; free(ptail); ptail = NULL; } }头删
删除头节点前要把下一个节点存储起来，还是要注意判断链表为空的情况。
//头删 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* newhead = (*pphead)->next; free(*pphead); *pphead = newhead; }在pos位置之前插入
注意：
1.注意判断空链表，不能再空节点前插入。
2.pos不能为空。
3.pos是头节点的情况。
//在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //链表不能为空链表，不能在一个空节点前插入一个节点 assert(pphead && *pphead); //不能插入一个空节点 assert(pos); //pos是头节点的情况，头插 if (*pphead == pos) { SLTPushFront(pphead, x); } else { SLTNode* newnode = SLTCreateNode(x); //找到pos的前一个节点 SLTNode* prev = *pphead; while (prev->next != pos)//如果pos是头节点，那么这个循环就达不到目的 { prev = prev->next; } newnode->next = pos; prev->next = newnode; } }在pos位置之后插入
//在指定位置之后插入数据 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = SLTCreateNode(x); //下面两行代码顺序不能乱 newnode->next = pos->next; pos->next = newnode; }注意判断pos位置不能为空。
查找
遍历链表就可以了
//查找 SLTNode* SLTfind(SLTNode* phead, SLTDataType x) { //空节点返回null，不用assert SLTNode* pcur = phead; while (pcur) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }删除pos节点
找到pos的下一个节点，pos的前一个节点，更改指针，free掉pos节点就行了。
注意判断链表为空和pos节点为空的情况。
//删除pos节点 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); //pos是头节点 if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos)//如果pos是头节点，那么这个循环就达不到目的 { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }删除pos之后的节点
注意判断pos之后的节点是不是空节点。
//删除pos之后的节点 void SLTEraseAfter(SLTNode* pos) { assert(pos && pos->next); SLTNode* del = pos->next; pos->next = del->next; free(del); del = NULL; }销毁链表
遍历链表就行，把要删除的节点提前存起来就行，注意判断链表为空的情况。
//销毁链表 void SLTDesTroy(SLTNode** pphead) { assert(pphead && *pphead); SLTNode* pcur = *pphead; while (pcur) { SLTNode* next = pcur->next; free(pcur); pcur = next; } *pphead = NULL; }双链表的实现
定义
typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode;初始化（创造哨兵节点）
//申请一个节点 LTNode* CreateNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail!"); exit(1); } node->data = x; //双向链表是带头双向循环的，所以初始情况哨兵节点前指针和后指针要指向自己，不然不是循环 node->next = node->prev = node; return node; } //初始化 创造一个哨兵位 void LTinit(LTNode** pphead) { // *pphead = CreateNode(-1); }增、删、查、改操作
尾插
//尾插 void LTPushBack(LTNode* phead, LTDataType x) { //双向链表是空链表时，指的是只有一个哨兵位 //保证链表不是空链表 assert(phead); //创造新节点 LTNode* newnode = CreateNode(x); //有效节点的最后一个节点通过phead的prev指针找到 LTNode* ptail = phead->prev; //新节点的前指针指向有效节点的最后一个节点ptail newnode->prev = ptail; //新节点的后指针指向头节点phead newnode->next = phead; ptail->next = newnode; phead->prev = newnode; }
细节：这里的phead不用传二级指针，因为不涉及phead的改变，包括接下来的头插也是。
头插
头插指的是插入到第一个有效节点的前面，也就是哨兵位节点的后面。
//头插,插在哨兵位之后，第一个有效节点之前 void LTPushFront(LTNode* phead, LTDataType x) { //保证有一个哨兵位 assert(phead); LTNode* newnode = CreateNode(x); newnode->prev = phead; newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; }
尾删
删除有效节点的最后一个节点，注意判断链表为空的情况（没有有效节点，只有哨兵位）。
//尾删,删的是有效节点 void LTPopBack(LTNode* phead) { //链表不能为空且得有有效节点 assert(phead && phead->next != phead); LTNode* del = phead->prev; del->prev->next = phead; phead->prev = del->prev; free(del); del = NULL; }
头删
删除有效节点的第一个节点，注意判断链表为空的情况。
//头删 void LTPopFront(LTNode* phead) { assert(phead && phead->next != phead); LTNode* del = phead->next; del->next->prev = phead; phead->next = del->next; free(del); del = NULL; }在pos位置之后插入数据
//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = CreateNode(x); newnode->prev = pos; newnode->next = pos->next; //这里顺序不能颠倒 pos->next->prev = newnode; pos->next = newnode; }注意后两句代码的顺序是一定不能颠倒的。
查找
寻找指定数据，返回该节点，遍历链表即可。
注意判断链表为空的情况。
//找指定数据 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead && phead->next != phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }删除pos节点
//删除pos节点 void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }销毁链表
//销毁链表 void LTDesTroy(LTNode* phead) { //从一个有效节点开始销毁 LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = NULL; }遍历链表，逐个销毁，然后销毁哨兵位就行了。
顺序表和链表的区别
拜拜，下期再见😏
摸鱼ing😴✨🎞
