【初阶数据结构05】——双向链表专题
文章目录
引言
在单链表专题中，我们深入探索了单链表，学会了如何通过指针将零散的内存节点串联成一条线。单链表的结构简单，但操作时我们常常需要“瞻前顾后”——因为每个节点只知道下一个节点的位置，却不知道上一个节点，导致很多操作（如尾部删除）需要遍历整个链表。
为了解决这个问题，C语言提供了更强大的链表形式：双向链表。它不仅知道下一个节点是谁，还知道上一个节点是谁，就像火车车厢不仅有后门，还有前门，可以双向通行。
今天，我们将学习最常用的双向链表结构——带头双向循环链表。
1. 双向链表的结构
1.1 什么是带头双向循环链表？
让我们把名字拆开看：
- 带头：存在一个特殊的节点，称为“头节点”或“哨兵位”（sentinel）。这个节点不存储有效数据，它的作用是简化边界条件的处理。就像停车场门口的岗亭，它本身不是车位，但帮助我们管理车辆进出。
- 双向：每个节点包含两个指针——
prev指向前一个节点，next指向后一个节点。 - 循环：最后一个节点的
next指向头节点，头节点的prev指向最后一个节点。整个链表形成一个环，从任何节点出发都能遍历整个链表。
1.2 为什么需要哨兵位？
在单链表中，当我们插入或删除第一个节点时，需要修改头指针（一级指针的二级指针问题）。而有了哨兵位后，头指针永远指向这个哨兵节点，所有有效节点都在它之后。这样，插入和删除操作就不需要改变头指针的值，代码逻辑更加统一，边界条件也大大简化。
此外，循环的特性使得我们可以从哨兵位开始，既能正向遍历（next），也能反向遍历（prev），非常灵活。
2. 双向链表的实现
我们将使用 C 语言实现一个带头双向循环链表，提供常见的操作接口。
2.1 节点类型定义
typedef int ListdataType; typedef struct ListNode { ListdataType data; struct ListNode* next; struct ListNode* prev; }Listnode;2.2 函数声明
Listnode* BuyNode(ListdataType x); Listnode* InitList(); //链表初始化，其实就是让链表只含有一个头节点 void PrintList(Listnode* head);//打印链表 void Listpushback(Listnode* head, ListdataType x);//尾插数据 void Listpushfront(Listnode* head, ListdataType x);//头插数据，在第一个有效数据之前插入 void Listpopback(Listnode* head);//尾删 void Listpopfront(Listnode* head);//头删 Listnode* Listfind(Listnode* head, ListdataType x);//在链表中查找数据，返回第一个匹配的节点 void Listinsert(Listnode* pos, ListdataType x);//在指定位置之后插入数据 void Listdelete(Listnode* pos);//删除指定位置的数据 void Listdestroy(Listnode* head);//销毁链表2.3 函数实现
2.3.1 创建新节点（内部辅助函数）
Listnode* BuyNode(ListdataType x)//因为后面会有尾插、头插，所以写一个函数来创建节点 { Listnode* node = (Listnode*)malloc(sizeof(Listnode)); if (node == NULL) { perror("malloc error"); exit(1); } node->data = x; node->prev = node->next = node; return node; }2.3.2 初始化
Listnode* InitList() { Listnode* head = BuyNode(-1); return head; } 2.3.3 打印链表
void PrintList(Listnode* head) { Listnode* pcur = head->next; while (pcur != head) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); }2.3.4 尾插
void Listpushback(Listnode* head, ListdataType x) { assert(head); Listnode* newnode = BuyNode(x); Listnode* pcur = head->prev; newnode->prev = pcur; newnode->next = head; pcur->next = newnode; head->prev = newnode; }分析：利用循环特性，我们不需要遍历就能直接找到尾节点（phead->prev），因此尾插操作的时间复杂度为 O(1)。
2.3.5 尾删
void Listpopback(Listnode* head) { assert(head && head->next != head); Listnode* del = head->prev; del->prev->next = head; head->prev = del->prev; free(del); del = NULL; }2.3.6 头插（在第一个有效节点之前插入）
void Listpushfront(Listnode* head, ListdataType x) { assert(head); Listnode* newnode = BuyNode(x); Listnode* pcur = head->next; newnode->prev = head; newnode->next = pcur; pcur->prev = newnode; head->next = newnode; }2.3.7 头删（删除第一个有效节点）
void Listpopfront(Listnode* head) { assert(head && head->next != head); Listnode* del = head->next; del->next->prev = head; head->next = del->next; }2.3.8 查找
Listnode* Listfind(Listnode* head, ListdataType x) { Listnode* pcur = head->next; while (pcur != head) { if (pcur->data == x) { printf("找到了\n"); return pcur; } pcur = pcur->next; } printf("链表中没有找到%d\n", x); return NULL; } 2.3.9 在指定位置之后插入
void Listinsert(Listnode* pos, ListdataType x) { assert(pos); Listnode* newnode = BuyNode(x); newnode->next = pos->next; pos->next->prev = newnode; newnode->prev = pos; pos->next = newnode; }注意：这个操作在 pos 之后插入，时间复杂度 O(1)。如果我们想在 pos 之前插入，也可以利用双向链表的特性很快实现（只需稍微调整逻辑），但这里我们只实现一种。
2.3.10 删除指定位置的节点
void Listdelete(Listnode* pos) { assert(pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; }2.3.11 销毁链表
void Listdestroy(Listnode* head) { assert(head); Listnode* pcur = head->next; while (pcur != head) { Listnode* del = pcur; pcur = pcur->next; free(del); del = NULL; } free(pcur); pcur = head = NULL; }2.4 测试代码示例
void Test01()//测试初始化、打印、创建节点函数功能 { Listnode* head = NULL; head = InitList(); Listnode* node1 = BuyNode(1); Listnode* node2 = BuyNode(2); Listnode* node3 = BuyNode(3); Listnode* node4 = BuyNode(4); head->next=node1; node1->prev=head; node1->next=node2; node2->prev=node1; node2->next=node3; node3->prev=node2; node3->next=node4; node4->prev=node3; node4->next=head; PrintList(head); } void Test02()//测试插入节点、删除节点函数功能 { Listnode* head=InitList(); Listpushback(head, 1); Listpushback(head, 2); Listpushback(head, 3); Listpushfront(head, 4); PrintList(head); Listpopback(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); } void Test03() { Listnode* head = InitList(); Listpushback(head, 1); Listpushback(head, 2); Listpushback(head, 3); Listpushback(head, 4); Listinsert(Listfind(head, 4), 10); PrintList(head); Listdestroy(head); head = NULL; } int main() { //Test01(); //Test02(); Test03(); return 0; }3. 完整代码展示
3.1 List.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int ListdataType; typedef struct ListNode { ListdataType data; struct ListNode* next; struct ListNode* prev; }Listnode; Listnode* BuyNode(ListdataType x); Listnode* InitList(); //链表初始化，其实就是让链表只含有一个头节点 void PrintList(Listnode* head);//打印链表 void Listpushback(Listnode* head, ListdataType x);//尾插数据 void Listpushfront(Listnode* head, ListdataType x);//头插数据，在第一个有效数据之前插入 void Listpopback(Listnode* head);//尾删 void Listpopfront(Listnode* head);//头删 Listnode* Listfind(Listnode* head, ListdataType x);//在链表中查找数据，返回第一个匹配的节点 void Listinsert(Listnode* pos, ListdataType x);//在指定位置之后插入数据 void Listdelete(Listnode* pos);//删除指定位置的数据 void Listdestroy(Listnode* head);//销毁链表3.2 List.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" Listnode* BuyNode(ListdataType x)//因为后面会有尾插、头插，所以写一个函数来创建节点 { Listnode* node = (Listnode*)malloc(sizeof(Listnode)); if (node == NULL) { perror("malloc error"); exit(1); } node->data = x; node->prev = node->next = node; return node; } void PrintList(Listnode* head) { Listnode* pcur = head->next; while (pcur != head) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); } Listnode* InitList() { Listnode* head = BuyNode(-1); return head; } void Listpushback(Listnode* head, ListdataType x) { assert(head); Listnode* newnode = BuyNode(x); Listnode* pcur = head->prev; newnode->prev = pcur; newnode->next = head; pcur->next = newnode; head->prev = newnode; } void Listpushfront(Listnode* head, ListdataType x) { assert(head); Listnode* newnode = BuyNode(x); Listnode* pcur = head->next; newnode->prev = head; newnode->next = pcur; pcur->prev = newnode; head->next = newnode; } void Listpopback(Listnode* head) { assert(head && head->next != head); Listnode* del = head->prev; del->prev->next = head; head->prev = del->prev; free(del); del = NULL; } void Listpopfront(Listnode* head) { assert(head && head->next != head); Listnode* del = head->next; del->next->prev = head; head->next = del->next; } Listnode* Listfind(Listnode* head, ListdataType x) { Listnode* pcur = head->next; while (pcur != head) { if (pcur->data == x) { printf("找到了\n"); return pcur; } pcur = pcur->next; } printf("链表中没有找到%d\n", x); return NULL; } void Listinsert(Listnode* pos, ListdataType x) { assert(pos); Listnode* newnode = BuyNode(x); newnode->next = pos->next; pos->next->prev = newnode; newnode->prev = pos; pos->next = newnode; } void Listdelete(Listnode* pos) { assert(pos); pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; } void Listdestroy(Listnode* head) { assert(head); Listnode* pcur = head->next; while (pcur != head) { Listnode* del = pcur; pcur = pcur->next; free(del); del = NULL; } free(pcur); pcur = head = NULL; }3.3 test.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" void Test01()//测试初始化、打印、创建节点函数功能 { Listnode* head = NULL; head = InitList(); Listnode* node1 = BuyNode(1); Listnode* node2 = BuyNode(2); Listnode* node3 = BuyNode(3); Listnode* node4 = BuyNode(4); head->next=node1; node1->prev=head; node1->next=node2; node2->prev=node1; node2->next=node3; node3->prev=node2; node3->next=node4; node4->prev=node3; node4->next=head; PrintList(head); } void Test02()//测试插入节点、删除节点函数功能 { Listnode* head=InitList(); Listpushback(head, 1); Listpushback(head, 2); Listpushback(head, 3); Listpushfront(head, 4); PrintList(head); Listpopback(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); Listpopfront(head); PrintList(head); } void Test03() { Listnode* head = InitList(); Listpushback(head, 1); Listpushback(head, 2); Listpushback(head, 3); Listpushback(head, 4); Listinsert(Listfind(head, 4), 10); PrintList(head); Listdestroy(head); head = NULL; } int main() { //Test01(); //Test02(); Test03(); return 0; }4. 总结
双向链表（带头双向循环链表）是链表家族中功能最强大的成员。它通过引入哨兵位和双向指针，使得几乎所有操作（头插、头删、尾插、尾删、指定位置插入删除）都能在 O(1) 时间内完成，代码逻辑也更加简洁统一。
然而，没有完美的数据结构。双向链表牺牲了随机访问的能力，且每个节点需要额外存储两个指针，内存开销比单链表更大。在实际开发中，我们需要根据具体需求权衡利弊，选择最合适的数据结构。
下期预告
掌握了单链表和双向链表后，我们已经能够灵活地组织线性数据。接下来，我们将进入另一个重要的线性结构——栈和队列。它们是对线性表的一种特殊限制，广泛应用于函数调用、表达式求值、消息队列等场景。让我们继续探索数据结构的奇妙世界！
