【初阶数据结构】逆流的回环链桥：双链表
文章目录
本篇是链表专题的双链表，是一种链表数据结构，它的每个节点除了包含数据域（用于存储数据）之外，还包含两个指针域，一个指向前一个节点（prev），另一个指向后一个节点（next）
1.双链表接口实现
这次我们实现的是带头双向循环的链表，不仅有指向前一个节点的prev指针，还有指向下一个节点的next指针，最后一个节点有指向开头的指针next，开头的节点有指向结尾的指针prev，形成循环
双链表定义：
typedefint LTDataType;typedefstructListNode{structListNode* next;structListNode* prev; LTDataType data;}LTNode;有人问为什么每次都要重新定义数据类型，因为每次的节点数据类型不一定是一样的，定义一下方便修改所有地方的数据类型
1.1 双链表节点创建
LTNode*BuyListNode(LTDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){perror("malloc fail");returnNULL;} newnode->data = x; newnode->prev =NULL; newnode->next =NULL;return newnode;}还是和之前的链表节点创建一样，这里不过多叙述
1.2 双链表初始化
LTNode*LTInit(){ LTNode* phead =BuyListNode(-1); phead->next = phead; phead->prev = phead;return phead;}通常我们会在主函数创建一个指针接收一个初始化指针，prev和next都指向自己形成循环，也就是一个哨兵位，也间接规避了链表为空的情况，直接可以PushBack节点
1.3 双链表销毁
voidLTDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* next = cur->next;free(cur); cur = next;}free(phead); phead =NULL;}head是哨兵位需要开始时被访问，所以从phead->next开始，先保存下一个节点的指针，然后释放当前移动指针指向的节点，再把保存过的节点赋值给移动指针实现移动遍历节点，最后再释放哨兵位head
1.4 双链表打印
voidLTPrint(LTNode* phead){assert(phead);printf("<= head =>"); LTNode* cur = phead->next;while(cur != phead){printf(" %d =>", cur->data); cur = cur->next;}printf("\n");}要根据双链表的特性来，双链表有哨兵位，所以打印要从哨兵位的下一个节点开始打印，直到遇到的节点的next指针指向哨兵位
1.5 双链表检查是否为空
intLTEmpty(LTNode* phead){assert(phead);return phead->next == phead ?0:1;}为了方便在增删查改中避免链表为空的情况，and多处需使用到，所以特别写一个判空函数，因为是循环链表，所以指向自己表明链表只有一个哨兵位，则返回0，反则返回1
1.6 双链表尾插
voidLTPushBack(LTNode* phead, LTDataType x){assert(phead); LTNode* newnode =BuyListNode(x); phead->prev->next = newnode; newnode->prev = phead->prev; newnode->next = phead; phead->prev = newnode;}由于是带头循环，所以每个节点都有4条逻辑线连接着，通常先修改两个节点间的链接，再修改循环的链接
1.7 双链表头插
voidLTPushFront(LTNode* phead, LTDataType x){assert(phead); LTNode* newnode =BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead;}无论是什么情况下，都要注意连接的顺序是否会影响到其他步骤的正常赋值，所以头插就需要先链接newnode的next指针，即通常先链接后面的节点
1.8 双链表尾删
voidLTPopBack(LTNode* phead){assert(phead);assert(LTEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev;free(tail); tail =NULL;}首先遇到删除就要注意是不是空链表，存不存在节点来删除，然后要分别存储最后一个节点和倒数第二个节点，方便进行链接释放的操作
1.9 双链表头删
voidLTPopFront(LTNode* phead){assert(phead);assert(LTEmpty(phead)); LTNode* first = phead->next; phead->next = first->next; first->next->prev = phead;free(first); first =NULL;}相同的操作，无论是删除还是销毁，都要记得存储需要释放的节点相关指针，因为需要在删除之后将其连接的的节点连接起来
1.10 双链表查找
LTNode*LTFind(LTNode* phead, LTDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;} cur = cur->next;}returnNULL;}我们在查找时肯定是查找有效的数据，所以我们查找是从哨兵位后一个节点开始的，查找方法也很简单，遍历整个双链表，看看能否找到相应的数据，找得到就返回对应节点，找不到就返回空
1.11 双链表在pos位置插入x
voidLTInsert(LTNode* pos, LTDataType x){assert(pos); LTNode* newnode =BuyListNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; pos->prev = newnode; newnode->next = pos;}因为双向链表有prev，就不用在意是pos前还是pos后插入，这里用的是pos前插入
1.12 双链表在pos位置删除x
voidLTErase(LTNode* phead, LTNode* pos){assert(LTEmpty(phead)); pos->prev->next = pos->next; pos->next->prev = pos->prev;free(pos);}其实和头删尾删的原理是一样的，直接删除，然后将剩余两个断开的节点链接就行了
2.顺序表和链表对比
顺序表和链表各有各的好处
🚩顺序表： 适用于对随机访问性能要求高，元素数量可预估，且不需要频繁进行插入和删除操作的场景
🚩链表： 适用于需要频繁插入和删除元素，元素数量动态变化，难以预估元素数量的场景
3.代码展示
传送门：Gitee双链表代码
3.1 List.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LTDataType;typedefstructListNode{structListNode* next;structListNode* prev; LTDataType data;}LTNode; LTNode*LTInit();voidLTDestroy(LTNode** pphead);voidLTPrint(LTNode* phead); LTNode*BuyListNode(LTDataType x);intLTEmpty(LTNode* phead);voidLTPushBack(LTNode* phead, LTDataType x);voidLTPopBack(LTNode* phead);voidLTPushFront(LTNode* phead, LTDataType x);voidLTPopFront(LTNode* phead); LTNode*LTFind(LTNode* phead, LTDataType x);voidLTInsert(LTNode* pos, LTDataType x);voidLTErase(LTNode* pos);3.2 List.c
#define_CRT_SECURE_NO_WARNINGS#include"List.h"//初始化 LTNode*LTInit(){ LTNode* phead =BuyListNode(-1); phead->next = phead; phead->prev = phead;return phead;}//销毁voidLTDestroy(LTNode* phead){assert(phead); LTNode* cur = phead->next;while(cur != phead){ LTNode* next = cur->next;free(cur); cur = next;}free(phead); phead =NULL;}//打印voidLTPrint(LTNode* phead){assert(phead);printf("<= head =>"); LTNode* cur = phead->next;while(cur != phead){printf(" %d =>", cur->data); cur = cur->next;}printf("\n");}//创建节点 LTNode*BuyListNode(LTDataType x){ LTNode* newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){perror("malloc fail");returnNULL;} newnode->data = x; newnode->prev =NULL; newnode->next =NULL;return newnode;}//判空intLTEmpty(LTNode* phead){assert(phead);return phead->next == phead ?0:1;}//尾插voidLTPushBack(LTNode* phead, LTDataType x){assert(phead); LTNode* newnode =BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode;}//尾删voidLTPopBack(LTNode* phead){assert(phead);assert(LTEmpty(phead)); LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev;free(tail); tail =NULL;}//头插voidLTPushFront(LTNode* phead, LTDataType x){assert(phead); LTNode* newnode =BuyListNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead;}//头删voidLTPopFront(LTNode* phead){assert(phead);assert(LTEmpty(phead)); LTNode* first = phead->next; phead->next = first->next; first->next->prev = phead;free(first); first =NULL;}//查找 LTNode*LTFind(LTNode* phead, LTDataType x){assert(phead); LTNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;} cur = cur->next;}returnNULL;}//在pos处插入xvoidLTInsert(LTNode* pos, LTDataType x){assert(pos); LTNode* newnode =BuyListNode(x); pos->prev->next = newnode; newnode->prev = pos->prev; pos->prev = newnode; newnode->next = pos;}//在pos处删除xvoidLTErase(LTNode* phead, LTNode* pos){assert(LTEmpty(phead)); pos->prev->next = pos->next; pos->next->prev = pos->prev;free(pos);}希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
