C语言双向链表详解Doubly Linked List ·哨兵位/带头双向循环 · 前驱后继双指针 · 数据结构的最优形态一、为什么需要双向链表单链表有两个痛点只能从头往后走——找前驱必须重新遍历O(n)删除指定节点要传二级指针可能动头指针双向链表每个节点加一个 prev 前驱指针前后都能走指定位置插入删除 O(1)。二、两种最常用的链表课程强调实际开发中最常用的两种链表**单链表**不带头、不循环——实现简单**双向循环链表**带头、带哨兵位——操作最方便这节讲后者带头双向循环链表。单链表phead → [data|next] → [data|next] → NULL双向循环phead(哨兵) ⇄ [data|prev|next] ⇄ [data|prev|next] ⇄ (回到phead)三、节点结构data next prevtypedef int LTDataType;typedef struct ListNode {LTDataType data;struct ListNode* next; //后继指针struct ListNode* prev; //前驱指针} LTNode;四、哨兵位设计核心思想双向链表带一个哨兵位头结点数据域为 -1仅作标记好处巨大空链表 只剩哨兵位phead-next phead**所有操作传一级指针**——头指针永远不变对比单链表的二级指针插入/删除统一逻辑不用分空/非空讨论// BuyNode中node-next node-prev node; ←自环LTNode* LTInit() {LTNode* phead LTBuyNode(-1); //哨兵位return phead;}⚠ 易错哨兵位 next/prev 初始化为 NULL 是错的必须指向自己自环否则循环结构断裂。五、尾插四步连指针void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode LTBuyNode(x);//插入到phead和phead-prev之间newnode-prev phead-prev; // ①新节点前驱原尾newnode-next phead; // ②新节点后继头phead-prev-next newnode; // ③原尾的后继新节点phead-prev newnode; // ④头的前驱新节点}⚠不能交换顺序先改 newnode 的指针①②再改原链表指针③④。反了节点就丢了。六、头插 / 尾删 / 头删//头插插在哨兵位后面void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead-next; //新节点后继原第一个newnode-prev phead;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);}七、指定位置插入/删除核心优势双向链表在 pos 之后插入不需要找前驱——prev 指针直接拿到//在pos之后插入LTInsertO(1)void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;}//删除pos节点无需知道头指针O(1)void LTErase(LTNode* pos) {assert(pos);pos-next-prev pos-prev; // pos后继的前驱 pos前驱pos-prev-next pos-next; // pos前驱的后继 pos后继free(pos);}这正是双向链表 vs 单链表的核心优势已知节点位置时 O(1) 插入删除。八、打印与销毁//遍历结束条件pcur回到哨兵位void LTPrint(LTNode* phead) {LTNode* pcur phead-next;while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; }printf(\n);}//销毁逐个释放最后释放哨兵位void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur phead-next;while (pcur ! phead) {LTNode* next pcur-next; //先存下一个free(pcur);pcur next;}free(phead); //最后释放哨兵位}九、链表分类总览从三个维度给链表分类方向单向 / 双向是否循环循环 / 非循环是否带头哨兵带头 / 不带头推荐组合**单链表不带头不循环 双向循环链表带头**——头尾两把刷子。十、常见错误清单①哨兵位 next/prev 初始化为 NULL应自环指向自己②指针连接顺序颠倒 → 节点丢失先改新节点再改原链表③删除/尾删不判断是否只剩哨兵位 → 误删哨兵④销毁时忘记先存 next → 释放后无法继续遍历⑤ LTErase 中 free 后 posNULL 只改形参——调用后不要再使用 posYesterday is history, tomorrow is a mystery, but today is a gift. That is why it is called the present.—— 乌龟大师, 功夫熊猫— END — C语言：双向链表详解
C语言双向链表详解Doubly Linked List ·哨兵位/带头双向循环 · 前驱后继双指针 · 数据结构的最优形态一、为什么需要双向链表单链表有两个痛点只能从头往后走——找前驱必须重新遍历O(n)删除指定节点要传二级指针可能动头指针双向链表每个节点加一个 prev 前驱指针前后都能走指定位置插入删除 O(1)。二、两种最常用的链表课程强调实际开发中最常用的两种链表**单链表**不带头、不循环——实现简单**双向循环链表**带头、带哨兵位——操作最方便这节讲后者带头双向循环链表。单链表phead → [data|next] → [data|next] → NULL双向循环phead(哨兵) ⇄ [data|prev|next] ⇄ [data|prev|next] ⇄ (回到phead)三、节点结构data next prevtypedef int LTDataType;typedef struct ListNode {LTDataType data;struct ListNode* next; //后继指针struct ListNode* prev; //前驱指针} LTNode;四、哨兵位设计核心思想双向链表带一个哨兵位头结点数据域为 -1仅作标记好处巨大空链表 只剩哨兵位phead-next phead**所有操作传一级指针**——头指针永远不变对比单链表的二级指针插入/删除统一逻辑不用分空/非空讨论// BuyNode中node-next node-prev node; ←自环LTNode* LTInit() {LTNode* phead LTBuyNode(-1); //哨兵位return phead;}⚠ 易错哨兵位 next/prev 初始化为 NULL 是错的必须指向自己自环否则循环结构断裂。五、尾插四步连指针void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode LTBuyNode(x);//插入到phead和phead-prev之间newnode-prev phead-prev; // ①新节点前驱原尾newnode-next phead; // ②新节点后继头phead-prev-next newnode; // ③原尾的后继新节点phead-prev newnode; // ④头的前驱新节点}⚠不能交换顺序先改 newnode 的指针①②再改原链表指针③④。反了节点就丢了。六、头插 / 尾删 / 头删//头插插在哨兵位后面void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead-next; //新节点后继原第一个newnode-prev phead;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);}七、指定位置插入/删除核心优势双向链表在 pos 之后插入不需要找前驱——prev 指针直接拿到//在pos之后插入LTInsertO(1)void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;}//删除pos节点无需知道头指针O(1)void LTErase(LTNode* pos) {assert(pos);pos-next-prev pos-prev; // pos后继的前驱 pos前驱pos-prev-next pos-next; // pos前驱的后继 pos后继free(pos);}这正是双向链表 vs 单链表的核心优势已知节点位置时 O(1) 插入删除。八、打印与销毁//遍历结束条件pcur回到哨兵位void LTPrint(LTNode* phead) {LTNode* pcur phead-next;while (pcur ! phead) { printf(%d-, pcur-data); pcur pcur-next; }printf(\n);}//销毁逐个释放最后释放哨兵位void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur phead-next;while (pcur ! phead) {LTNode* next pcur-next; //先存下一个free(pcur);pcur next;}free(phead); //最后释放哨兵位}九、链表分类总览从三个维度给链表分类方向单向 / 双向是否循环循环 / 非循环是否带头哨兵带头 / 不带头推荐组合**单链表不带头不循环 双向循环链表带头**——头尾两把刷子。十、常见错误清单①哨兵位 next/prev 初始化为 NULL应自环指向自己②指针连接顺序颠倒 → 节点丢失先改新节点再改原链表③删除/尾删不判断是否只剩哨兵位 → 误删哨兵④销毁时忘记先存 next → 释放后无法继续遍历⑤ LTErase 中 free 后 posNULL 只改形参——调用后不要再使用 posYesterday is history, tomorrow is a mystery, but today is a gift. That is why it is called the present.—— 乌龟大师, 功夫熊猫— END —