【C语言】实现双向链表
目录
（一）头文件
（二） 功能实现
（1）初始化
（2）打印链表
（3） 头插与头删
（4）尾插与尾删
（5）指定位置之后插入
（6）删除指定位置的数据
（7）链表的销毁
正文开始：
在实际应用中，常用的双向链表是双向带头循环链表，本文考虑到实际应用，目的也是实现双向带头循环链表。
（一）头文件
命名"List.h"
本文不加解释的给出头文件，按照头文件来实现双向链表的基本功能：包括打印链表，链表的初始化，头插与头删，尾插与尾删，在指定位置之后插入数据，删除指定位置的数据，链表的销毁等共九个功能。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //链表的数据类型 typedef int LTtype; //双向链表的节点 typedef struct ListNode {LTtype data;struct ListNode* prev;struct ListNode* next; }LTNode;//双向链表带有哨兵位，插入数据之前先插入哨兵位 //初始化》传入头节点 void LTInit(LTNode** pphead);//初始化2>返回头节点 LTNode* LtInit0();//销毁链表 void LTDestory(LTNode** pphead);//尾插 void LTtail_push(LTNode* phead,LTtype x);//头插 //是在头节点之后插入，在头节点之前插入等价于尾插 void LThead_push(LTNode* phead,LTtype x);//打印便于调试 void Print(LTNode* phead);//头删 void LTpophead(LTNode* phead);//尾删 void LTpoptail(LTNode* phead);//查找 //为了找到pos位置 LTNode* LTfind(LTNode* phead, LTtype x);//在pos之后插入数据 void LTinsert(LTNode* pos, LTtype x);//删除pos处的数据 void LTerase(LTNode* pos);
（二） 功能实现
带头相对于不带头有诸多优势：
带头与不带头链表：
带头链表是指在链表的开头增加一个额外的节点，该节点不存储具体的数据，仅用于辅助操作链表。带头链表的带头节点可以简化链表的操作，提高代码的可读性和可维护性。
意义：
带头节点可以避免链表为空的特殊情况处理。在没有带头节点的链表中，如果链表为空，添加、删除等操作都需要额外的处理逻辑。而带头节点的链表中，带头节点一直存在，无论链表是否为空，操作逻辑都是一致的，可以减少代码的复杂性。
局限：
造成额外的空间浪费。
（1）初始化
初始化有两种方法，具体实现如下：
传址初始化
初始化传递链表的地址（二级指针【通过传址，将形参与实参建立联系】），初始化要插入头指针哨兵位（不保存有效的数据），便于简化代码逻辑。
//双向链表带有哨兵位，插入数据之前先插入哨兵位 void LTInit(LTNode** pphead) {*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead; }接受返回值初始化
在函数内申请头节点，最后返回到主函数内：
//初始化2>返回头节点 LTNode* LtInit0() {LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc");exit(1);}phead->data = -1;phead->next = phead->prev = phead;return phead; }
（2）打印链表
以便于调试，理解代码；
与打印单链表一样，不同的是：while的跳出条件是 pcur != phead；
//打印链表 void Print(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n"); }
（3） 头插与头删
插入操作需要申请新节点：
//获取新节点 LTNode* LTbuynewnode(LTtype x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode; }
头插与头删
头插，是在头节点之后插入，在头节点之前插入等价于尾插；
先对新节点进行操作，因为新节点与原节点没有联系，不会因为对指针进行操作而丢失节点，造成数据丢失和内存泄漏；
我们可以直接得到phead，因此先让phead的下一个节点的前驱指针指向newnode，再改变phead的next指针；
（如果反过来，先改变phead的next指向newnode，此时newnode后面的节点就找不到了。）//头插，是在头节点之后插入，在头节点之前插入等价于尾插 void LThead_push(LTNode* phead, LTtype x) {assert(phead);LTNode* newnode = LTbuynewnode(x);//先对新节点进行操作newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}头删
断言传过来的指针不为空，链表不为空，通过assert实现；
通过创建del指针（要被删除的节点），保存旧头节点；
通过创建next指针，保存旧头节点的next节点；
这样命名后进行头删，逻辑清晰，不易出错；
//头删 void LTpophead(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->next;//被删除的节点LTNode* next = del->next;//del的后置节点phead->next = next;next->prev = phead;free(del);del = NULL; }
（4）尾插与尾删
尾插
与头插的逻辑完全相同
//尾插 void LTtail_push(LTNode* phead, LTtype x) {assert(phead);LTNode* newnode = LTbuynewnode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode; }尾删
与头删的逻辑完全相同
//尾删 void LTpoptail(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->prev;//被删除的节点LTNode* prev = del->prev;//del的前置节点prev->next = phead;phead->prev = prev;free(del);del = NULL; }
（5）指定位置之后插入
查找
查找数据值为x的节点，找到返回此节点，找不到返回NULL；
//查找 LTNode* LTfind(LTNode* phead,LTtype x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL; }
在指定位置之后插入数据
根据find找到的pos位置，申请新节点，插入到pos之后
//在pos位置之后插入数据 void LTinsert(LTNode* pos,LTtype x) {assert(pos);LTNode* newnode = LTbuynewnode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode; }
（6）删除指定位置的数据
删除指定位置的数据，需要的指针有pos的前驱节点，pos节点。
//删除pos处的数据 void LTerase(LTNode* pos) {assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL; }
（7）链表的销毁
链表的销毁共有两种方法：
传址销毁
//销毁链表 void LTDestory(LTNode** pphead) {assert(pphead);//哨兵位不为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur);pcur = next;}//释放哨兵位free(pphead);//此时可以改变哨兵位的pphead = NULL;}传值销毁
一级指针phead传递的是值，不是phead的地址，所以在函数中改变phead并不会改变phead的实际值
函数返回后，仍需要手动phead = NULL；//推荐使用一级，为了保持接口的一致性 void LTDestory0(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;//无效的置空，当做是习惯 } //一级指针phead传递的是值，不是phead的地址，所以在函数中改变phead并不会改变phead的实际值 //函数返回后，仍需要手动phead = NULL；
完~
未经作者同意禁止转载