【数据结构与算法】第8篇：线性表（四）：双向链表与循环链表

一、双向链表1.1 什么是双向链表双向链表Doubly Linked List的每个节点包含三个部分指向前驱节点的指针prev数据域data指向后继节点的指针nexttexthead ↔ [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] ↔ NULL优点可以从前往后遍历也可以从后往前遍历删除节点时不需要知道前驱节点通过prev直接找到插入操作更灵活缺点每个节点多了一个指针占用更多内存操作时多维护一个指针代码稍复杂1.2 节点结构定义ctypedef struct DNode { int data; struct DNode *prev; // 指向前驱 struct DNode *next; // 指向后继 } DNode, *PDNode; typedef struct { PDNode head; // 头结点哑结点 int size; } DList;和单链表一样我们继续使用带头结点的方式让操作更统一。1.3 初始化与销毁cvoid initDList(DList *list) { list-head (PDNode)malloc(sizeof(DNode)); if (list-head NULL) { printf(初始化失败\n); exit(1); } list-head-prev NULL; list-head-next NULL; list-size 0; } void destroyDList(DList *list) { PDNode cur list-head; while (cur ! NULL) { PDNode temp cur; cur cur-next; free(temp); } list-head NULL; list-size 0; }1.4 创建新节点cPDNode createDNode(int value) { PDNode newNode (PDNode)malloc(sizeof(DNode)); if (newNode NULL) return NULL; newNode-data value; newNode-prev NULL; newNode-next NULL; return newNode; }1.5 插入操作双向链表的插入比单链表简单因为可以同时操作前后指针。在指定位置插入cint insertAt(DList *list, int pos, int value) { if (pos 0 || pos list-size) { printf(插入位置不合法\n); return -1; } PDNode newNode createDNode(value); if (newNode NULL) return -1; // 找到要插入位置的原节点pos位置的节点 PDNode cur list-head; for (int i 0; i pos; i) { cur cur-next; } // 此时cur是要插入位置的前一个节点头结点或上一个节点 PDNode next cur-next; // 原来pos位置的节点 // 连接新节点 newNode-prev cur; newNode-next next; cur-next newNode; if (next ! NULL) { next-prev newNode; } list-size; return 0; }头插法在第一个有效节点前插入cvoid insertAtHead(DList *list, int value) { insertAt(list, 0, value); }尾插法cvoid insertAtTail(DList *list, int value) { insertAt(list, list-size, value); }1.6 删除操作双向链表删除节点时不需要遍历找前驱直接通过当前节点的prev就能拿到。cint deleteAt(DList *list, int pos) { if (pos 0 || pos list-size) { printf(删除位置不合法\n); return -1; } // 找到要删除的节点 PDNode cur list-head-next; for (int i 0; i pos; i) { cur cur-next; } PDNode prev cur-prev; PDNode next cur-next; // 断开连接 prev-next next; if (next ! NULL) { next-prev prev; } int value cur-data; free(cur); list-size--; return value; }1.7 遍历正向和反向cvoid printForward(DList *list) { PDNode cur list-head-next; printf(正向 size%d, [, list-size); while (cur ! NULL) { printf(%d, cur-data); if (cur-next ! NULL) printf( - ); cur cur-next; } printf(]\n); } void printBackward(DList *list) { // 先找到尾节点 PDNode cur list-head; while (cur-next ! NULL) { cur cur-next; } printf(反向 [); while (cur ! list-head) { printf(%d, cur-data); if (cur-prev ! list-head) printf( - ); cur cur-prev; } printf(]\n); }1.8 完整演示cint main() { DList list; initDList(list); insertAtTail(list, 10); insertAtTail(list, 20); insertAtTail(list, 30); printForward(list); // [10 - 20 - 30] insertAtHead(list, 5); printForward(list); // [5 - 10 - 20 - 30] insertAt(list, 2, 15); printForward(list); // [5 - 10 - 15 - 20 - 30] deleteAt(list, 2); printForward(list); // [5 - 10 - 20 - 30] printBackward(list); // [30 - 20 - 10 - 5] destroyDList(list); return 0; }二、循环链表2.1 什么是循环链表循环链表Circular Linked List是首尾相连的链表单向循环链表尾节点的next指向头结点双向循环链表尾节点的next指向头结点头结点的prev指向尾节点text单向循环链表 head → [节点1] → [节点2] → [节点3] → ... → [节点n] ↘ ↑_______________________________________________↙ 双向循环链表 head ↔ [节点1] ↔ [节点2] ↔ ... ↔ [节点n] ↔ head特点从任意节点出发都能遍历整个链表适合需要循环处理的场景2.2 单向循环链表的实现ctypedef struct CNode { int data; struct CNode *next; } CNode, *PCNode; typedef struct { PCNode head; // 头指针带头结点 int size; } CList;初始化头结点的next指向自己形成空循环cvoid initCList(CList *list) { list-head (PCNode)malloc(sizeof(CNode)); if (list-head NULL) { printf(初始化失败\n); exit(1); } list-head-next list-head; // 指向自己表示空链表 list-size 0; }插入注意尾节点要指向头结点cvoid insertAtTail(CList *list, int value) { PCNode newNode (PCNode)malloc(sizeof(CNode)); newNode-data value; // 找到尾节点next指向头结点的节点 PCNode cur list-head; while (cur-next ! list-head) { cur cur-next; } cur-next newNode; newNode-next list-head; list-size; }遍历判断结束条件是cur-next ! list-headcvoid printCList(CList *list) { if (list-size 0) { printf(空链表\n); return; } PCNode cur list-head-next; printf([); while (cur ! list-head) { printf(%d, cur-data); if (cur-next ! list-head) printf( - ); cur cur-next; } printf(] - (回到头)\n); }三、经典应用约瑟夫环3.1 问题描述约瑟夫环问题n个人围成一圈从第一个人开始报数数到m的人出列然后从下一个人重新报数直到所有人出列。求出列顺序。3.2 思路分析用循环链表非常合适创建一个包含n个节点的循环链表从某个节点开始遍历每数到m就删除当前节点继续从下一个节点数直到链表为空3.3 代码实现c#include stdio.h #include stdlib.h typedef struct JosephNode { int num; // 编号 struct JosephNode *next; } JosephNode; // 创建约瑟夫环 JosephNode* createJosephus(int n) { if (n 0) return NULL; JosephNode *head (JosephNode*)malloc(sizeof(JosephNode)); head-num 1; head-next NULL; JosephNode *tail head; for (int i 2; i n; i) { JosephNode *newNode (JosephNode*)malloc(sizeof(JosephNode)); newNode-num i; newNode-next NULL; tail-next newNode; tail newNode; } tail-next head; // 形成环 return head; } // 约瑟夫环求解 void josephus(JosephNode *head, int m) { if (head NULL) return; JosephNode *cur head; JosephNode *prev NULL; // 找到尾节点作为prev的初始值 prev cur; while (prev-next ! head) { prev prev-next; } int count 1; while (cur-next ! cur) { // 只剩一个节点时停止 if (count m) { // 删除当前节点 printf(%d , cur-num); prev-next cur-next; free(cur); cur prev-next; count 1; // 重置计数 } else { prev cur; cur cur-next; count; } } // 输出最后一个 printf(%d\n, cur-num); free(cur); } int main() { int n 7, m 3; printf(%d个人数到%d出列顺序, n, m); JosephNode *head createJosephus(n); josephus(head, m); return 0; }运行结果text7个人数到3出列顺序3 6 2 7 5 1 4四、双向链表 vs 单链表操作单链表双向链表头插O(1)O(1)尾插O(n)O(1)维护尾指针中间插入O(n)O(n)但不用找前驱删除已知节点O(n)需要前驱O(1)反向遍历不支持O(n)内存占用1个指针/节点2个指针/节点适用场景单链表简单、省内存适合单向遍历双向链表需要双向遍历、频繁删除已知节点的场景五、小结这一篇我们讲了结构特点应用双向链表每个节点有prev和next删除更高效需要双向遍历的场景循环链表首尾相连从任意点可遍历约瑟夫环、环形缓冲区重点双向链表的插入删除要同时维护prev和next循环链表的遍历结束条件不再是NULL而是回到头结点约瑟夫环是循环链表的经典应用下一篇我们会讲栈和队列它们是受限的线性表但在很多场景下非常有用。六、思考题双向链表的插入操作中如果插入位置是末尾需要注意什么用双向循环链表实现约瑟夫环和用单向循环链表有什么区别为什么双向链表删除节点时不需要找前驱节点尝试实现一个双向链表的反转函数。