一、概述
1. 案例介绍
在现代软件开发中，数据结构的选择对程序的性能和可维护性有着至关重要的影响。数组和链表作为两种最基本的数据结构，分别适用于不同的场景。理解它们的特性和优劣，能够帮助开发者在实际项目中做出更合理的技术选型，从而优化系统性能。
双向链表通过在节点中添加一个指向前驱的指针 (prev)，克服了单向链表只能单向遍历和难以直接访问前驱节点的缺点。它以额外的内存开销为代价，换取了双向遍历能力和在任意已知节点位置进行高效插入、删除操作的能力。这种特性使得双向链表在需要频繁双向操作或在链表中间进行修改的场景中非常有用，是构建更高级数据结构（如双端队列、LRU 缓存）的基础组件之一。
华为开发者空间，是为全球开发者打造的专属开发者空间，致力于为每位开发者提供一台云主机、一套开发工具和云上存储空间，汇聚昇腾、鸿蒙、鲲鹏、GaussDB、欧拉等华为各项根技术的开发工具资源，并提供配套案例指导开发者 从开发编码到应用调测，基于华为根技术生态高效便捷的知识学习、技术体验、应用创新。
2. 适用对象
3. 案例时间
本案例总时长预计 90 分钟。
4. 案例流程
说明：
开通开发者空间，搭建 C/C++开发环境。
打开 VS Code，编写代码运行程序。
5. 资源总览
本案例预计花费 0 元。
二、配置实验环境
1. 开发者空间配置
面向广大开发者群体，华为开发者空间提供一个随时访问的“开发桌面云主机”、丰富的“预配置工具集合”和灵活使用的“场景化资源池”，开发者开箱即用，快速体验华为根技术和资源。
如果还没有领取开发者空间云主机，可以参考免费领取云主机文档领取。
领取云主机后可以直接进入华为开发者空间工作台界面，点击打开云主机 > 进入桌面连接云主机。
2. 配置开发环境
参考案例中心《基于开发者空间，定制C&C++开发环境云主机镜像》“2. 实验环境搭建”、“3. VS Code 安装部署”章节完成开发环境、VS code 及插件安装。
三、双向链表的基本操作
1. 双向链表的初始化
导入必要的头文件。
#include <stdio.h>#include <stdlib.h>
复制代码
定义双向链表的节点。
typedef int ElemType;
typedef struct DuLNode{ ElemType data; struct DuLNode *pre; //指向前驱结点的指针 struct DuLNode *next; //指向后继结点的指针}DuLNode, *DuLinkList;
复制代码
初始化双向链表。
如上图所示，链表的头节点的数据域不存储数据，指向前驱节点的指针域值为 null，指向后继节点的指针域指向第一个真正存储数据的节点。因此双向链表初始化实现如下。
DuLinkList list_init(){ DuLinkList head; //创建一个头结点，使用head指针指向头结点（头指针） head = (DuLinkList)malloc(sizeof(DuLNode)); head->next = NULL; head->pre = NULL; return head;}
复制代码
2. 销毁双向链表
检查头节点指针 head 是否为 NULL，是则打印错误并返回；
遍历整个链表，直到最后一个节点前停止；
头结点的 next 指向 t 的后继结点；（对应上图中的）
t 的后继结点的 pre 指向头结点；（对应上图中的）
释放当前节点 t；
t 指向头节点；
断开 head->next；
释放尾节点 t；
释放头节点；
pTail 置空。
int list_destroy(DuLinkList head, DuLNode **pTail){ //处理头节点为空的情况 if (NULL == head) { printf("[%s %d] head point is NULL\n", __FUNCTION__ , __LINE__); return 0; } //遍历整个链表，直到最后一个节点前停止 DuLNode *t = head->next; if (t == NULL) { printf("The DuLinkList is already an Empty List, so no deletion operation is needed.\n"); free(head); *pTail = NULL; return 0; }
while (t->next != NULL) { //头结点的next指向t的后继结点 head->next = t->next;
//t的后继结点的pre指向头结点 t->next->pre = head; free(t); t = head->next; }
//剩下最后一个尾结点 head->next = NULL; free(t); free(head); *pTail = NULL;
return 1;}
复制代码
3. 双向链表的插入操作
3.1 双向链表头插法
新建一个节点 p 将其前、后继指针域置空，数据域存储需要储存的数据；
如果链表为空，则新插入的节点 p 为尾节点，此时将头节点的 next 指针从原首节点改为指向新节点 p；
如果链表不为空：
int head_insert(DuLinkList head, DuLNode **pTail, ElemType data){ if (NULL == head) { printf("[%s %d] head pointer is NULL ...\n", __FUNCTION__ , __LINE__); return 0; }
//创建一个新的结点 DuLNode *p = (DuLNode *)malloc(sizeof(DuLNode)); p->pre = NULL; p->next = NULL; p->data = data;
//如果链表为空 if (NULL == head->next) { //第一个插入的结点就是尾结点 *pTail = p; head->next = p; p->pre = head; return 1; }
p->next = head->next; p->pre = head; head->next->pre = p; head->next = p;
DuLNode *temp = head->next; while (temp != NULL && temp->next != NULL) { temp = temp->next; } *pTail = temp;
return 1;}
复制代码
3.1.1 双向链表从头节点开始遍历
void print_list_from_head(DuLinkList head){ if (NULL == head) return;
DuLNode *t = head->next; while (t != NULL) { printf("%d ", t->data); t = t->next; } printf("\n");}
复制代码
3.1.2 双向链表从尾节点开始遍历
void print_list_from_tail(DuLNode *tail){ if (NULL == tail) return;
DuLNode *t = tail; //一直遍历到头结点 while (t->pre != NULL) //可能少打印第一个节点数据？ { printf("%d ", t->data); t = t->pre; //向前开始遍历 } printf("\n");}
复制代码
验证：编写main方法分别验证双向链表的初始化，销毁、头插法插入元素、遍历等操作。
注：验证前需要在 VS Code 中导入代码。
导入“双向链表初始化”章节代码；
导入“销毁双向链表”章节list_destroy函数代码；
导入“双向链表头插法”章节head_insert函数代码，以及其子章节“双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历” print_list_from_tail函数代码。
int main() { // 测试1: 初始化链表 printf("===== 测试1: 初始化链表 =====\n"); DuLinkList head = list_init(); DuLNode *tail = NULL; printf("初始化成功，头节点地址: %p\n", (void*)head); printf("当前链表内容（正向）: "); print_list_from_head(head); printf("当前链表内容（反向）: "); print_list_from_tail(tail);
// 测试2: 向空链表头插第一个节点 printf("\n===== 测试2: 向空链表插入10 =====\n"); head_insert(head, &tail, 10); printf("插入后链表内容（正向）: "); print_list_from_head(head); printf("插入后链表内容（反向）: "); print_list_from_tail(tail); printf("尾节点数据: %d\n", tail->data);
// 测试3: 继续头插多个节点 printf("\n===== 测试3: 头插20, 30, 40 =====\n"); head_insert(head, &tail, 20); head_insert(head, &tail, 30); head_insert(head, &tail, 40); printf("插入后链表内容（正向，应显示40->30->20->10）: "); print_list_from_head(head); printf("插入后链表内容（反向，应显示10->20->30->40）: "); print_list_from_tail(tail); printf("尾节点数据（应保持为10）: %d\n", tail->data);
// 测试4: 打印函数边界测试 printf("\n===== 测试4: 打印函数边界测试 =====\n"); printf("测试print_list_from_head(NULL): "); print_list_from_head(NULL); printf("测试print_list_from_tail(NULL): "); print_list_from_tail(NULL);
// 测试5: 销毁链表 printf("\n===== 测试5: 销毁链表 =====\n"); if (list_destroy(head, &tail)) { printf("链表销毁成功\n"); printf("销毁后head指针: %p\n", (void*)head); printf("销毁后tail指针: %p\n", (void*)tail); } else { printf("链表销毁失败\n"); }
return 0;}
复制代码
实验结果：
3.2 双向链表尾插法
新建一个节点 p 将其前、后继指针域置空，数据域存储需要储存的数据；
判断如果链表为空，则 p 节点的前驱指针指向 head 节点，head 的后继指针指向 p 节点；
如果链表不为空，则原尾节点的后继指针指向 p，p 节点的前驱指针指向原尾节点（对应上图中的），将 p 设置成为最新的尾节点（对应上图中的）。
int tail_insert(DuLinkList head, DuLNode **pTail, ElemType data){ if (NULL == head) { printf("[%s %d] head point is NULL\n", __FUNCTION__ , __LINE__); return 0; }
//创建一个新的结点 DuLNode *p = (DuLNode *)malloc(sizeof(DuLNode)); p->pre = NULL; p->next = NULL; p->data = data;
//判断链表是否为空 if (NULL == head->next) { *pTail = p; p->pre = head; head->next = p; return 1; }
(*pTail)->next = p; p->pre= *pTail; *pTail = p;
return 1;}
复制代码
验证：编写 main 函数，测试双向链表尾插法tail_insert函数。
注：验证前需要在 VS Code 中导入代码。
导入“双向链表初始化”章节代码；
导入“销毁双向链表”章节list_destroy函数代码；
导入 “双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历”print_list_from_tail函数代码。
导入“双向链表尾插法”章节tail_insert函数代码。
int main() { // 初始化双向链表 DuLinkList head = list_init(); DuLNode *tail = NULL; // 测试空链表打印 printf("Empty list (head to tail): "); print_list_from_head(head); printf("Empty list (tail to head): "); print_list_from_tail(tail); // 测试尾部插入 printf("\nInserting elements at tail...\n"); for (int i = 1; i <= 5; i++) { if (tail_insert(head, &tail, i)) { printf("Inserted %d: ", i); print_list_from_head(head); } else { printf("Failed to insert %d\n", i); } } // 打印双向链表 printf("\nFinal list (head to tail): "); print_list_from_head(head); printf("Final list (tail to head): "); print_list_from_tail(tail); // 销毁链表 if (list_destroy(head, &tail)) { printf("\nList destroyed successfully.\n"); } else { printf("\nFailed to destroy list.\n"); } // 再次打印确认销毁 printf("After destruction (head to tail): "); print_list_from_head(head); printf("After destruction (tail to head): "); print_list_from_tail(tail); return 0;}
复制代码
实验结果：
3.3 双向链表指定位置插入节点
新建一个节点 p 将其前、后继指针域置空，数据域存储需要储存的数据；
将节点 p 的后继指针指向 t 节点（对应上图中的），将 p 节点的前驱指针指向修改为 t 节点的前驱指针指向（对应上图中的）；
将 t 节点的前一个节点的后继指针改为指向新节点 p（对应上图中的），节点 t 的前驱改为指向新节点 p（对应上图中的）。
#include <stdint.h> // 新增引入头文件，为了使用uint类型
int insert_by_index(DuLinkList head, uint index, ElemType data){ if (NULL == head) //头节点空指针检查 { printf("[%s %d] head point is NULL\n", __FUNCTION__ , __LINE__); return 0; } //初始化并遍历链表，查找插入位置 int i = 1; DuLNode *t = head->next;
while (i < index && t != NULL) { i++; t = t->next; } //检查位置是否合法 if (NULL == t) { printf("[%s %d] index out of range ...\n", __FUNCTION__ , __LINE__); return 0; }
//创建一个新的结点 DuLNode *p = (DuLNode *)malloc(sizeof(DuLNode)); p->pre = NULL; p->next = NULL; p->data = data;
p->next = t; // 将节点p的后驱指针指向t节点 p->pre = t->pre; // 将p节点的前驱指针指向修改为t节点的前驱指针指向 t->pre->next = p; // 将t节点的前一个节点的后驱指针改为指向新节点p t->pre = p; // 节点t的前驱改为指向新节点p
return 1;}
复制代码
验证：编写 main 函数，测试双向链表指定位置插入操作函数insert_by_index。
注：验证前需要在 VS Code 中导入代码。
导入“双向链表初始化”章节代码；
导入“销毁双向链表”章节list_destroy函数代码；
导入 “双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历”print_list_from_tail函数代码。
导入“双向链表指定位置插入节点”章节int insert_by_index函数代码。
int main() { // 初始化双向链表 DuLinkList head = list_init(); DuLNode *tail = NULL; // 先插入一些初始数据（1, 3, 5） printf("Initial insertions...\n"); tail_insert(head, &tail, 1); tail_insert(head, &tail, 3); tail_insert(head, &tail, 5); printf("Initial list: "); print_list_from_head(head); // 应该输出: 1 3 5 // 测试在有效位置插入 printf("\nTesting valid insertions:\n"); printf("Insert 2 at position 2... "); if (insert_by_index(head, 2, 2)) { print_list_from_head(head); // 应该输出: 1 2 3 5 } else { printf("Failed\n"); } printf("Insert 4 at position 4... "); if (insert_by_index(head, 4, 4)) { print_list_from_head(head); // 应该输出: 1 2 3 4 5 } else { printf("Failed\n"); } printf("Insert 0 at position 1... "); if (insert_by_index(head, 1, 0)) { print_list_from_head(head); // 应该输出: 0 1 2 3 4 5 } else { printf("Failed\n"); } // 测试反向打印 printf("\nReverse list: "); print_list_from_tail(tail); // 应该输出: 5 4 3 2 1 0 // 测试无效位置插入 printf("\nTesting invalid insertions:\n"); printf("Insert at position 0... "); if (insert_by_index(head, 0, 99)) { print_list_from_head(head); } else { printf("Failed (expected)\n"); // 应该失败 } printf("Insert at position 10... "); if (insert_by_index(head, 10, 99)) { print_list_from_head(head); } else { printf("Failed (expected)\n"); // 应该失败 } // 销毁链表 printf("\nDestroying list...\n"); if (list_destroy(head, &tail)) { printf("List destroyed successfully.\n"); } else { printf("Failed to destroy list.\n"); } return 0;}
复制代码
实验结果：
4. 双向链表的删除操作
4.1 删除指定的节点（by index）
遍历双项链表，如果要删除的结点恰好是尾结点，则将*pTail 修改为 t 节点的前驱；
如果是中间节点：
#include <stdint.h> // 新增引入头文件，为了使用uint类型int delete_by_index(DuLinkList head, DuLNode **pTail, uint index){ if (NULL == head) { printf("[%s %d] head point is NULL\n", __FUNCTION__ , __LINE__); return 0; }
if (0 == index) { printf("[%s %d] index must > 0\n", __FUNCTION__ , __LINE__); return 0; }
int i = 1; DuLNode *t = head->next; while (i < index && t != NULL) { i++; t = t->next; }
//如果链表遍历完了 if (NULL == t) { printf("[%s %d] index out of range ...\n", __FUNCTION__ , __LINE__); return 0; }
//如果要删除的结点恰好是尾结点 if (t == *pTail) //if (t->next == NULL) { *pTail = t->pre; (*pTail)->next = NULL; free(t); return 1; }
//如果是中间结点 t->pre->next = t->next; t->next->pre = t->pre; free(t); return 1;}
复制代码
验证：编写main函数，测试删除双向链表指定的节点函数delete_by_ index。
注：验证前需要在 VS Code 中导入代码。
导入“双向链表初始化”章节代码；
导入“销毁双向链表”章节list_destroy函数代码；
导入“双向链表头插法”章节head_insert函数代码，以及其子章节“双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历” print_list_from_tail函数代码；
导入“删除指定的节点”章节delete_by_index代码。
int main() { // 初始化双向链表 DuLinkList head = list_init(); DuLNode *tail = NULL; // 测试1：尝试删除空链表 printf("Test 1: Delete from empty list (should fail)\n"); if (!delete_by_index(head, &tail, 1)) { printf("Correctly failed to delete from empty list\n\n"); }
// 插入测试数据：10 -> 20 -> 30 -> 40 -> 50 printf("Inserting test data: 10, 20, 30, 40, 50\n"); head_insert(head, &tail, 50); head_insert(head, &tail, 40); head_insert(head, &tail, 30); head_insert(head, &tail, 20); head_insert(head, &tail, 10); printf("Initial list (head to tail): "); print_list_from_head(head); // 应输出: 10 20 30 40 50 printf("Initial list (tail to head): "); print_list_from_tail(tail); // 应输出: 50 40 30 20 10 printf("\n");
// 测试2：删除头节点(第1个节点) printf("Test 2: Delete head node (index 1)\n"); if (delete_by_index(head, &tail, 1)) { printf("After deletion: "); print_list_from_head(head); // 应输出: 20 30 40 50 printf("Tail to head: "); print_list_from_tail(tail); // 应输出: 50 40 30 20 } printf("\n");
// 测试3：删除尾节点(现在是第4个节点) printf("Test 3: Delete tail node (index 4)\n"); if (delete_by_index(head, &tail, 4)) { printf("After deletion: "); print_list_from_head(head); // 应输出: 20 30 40 printf("Tail to head: "); print_list_from_tail(tail); // 应输出: 40 30 20 } printf("\n");
// 测试4：删除中间节点(第2个节点) printf("Test 4: Delete middle node (index 2)\n"); if (delete_by_index(head, &tail, 2)) { printf("After deletion: "); print_list_from_head(head); // 应输出: 20 40 printf("Tail to head: "); print_list_from_tail(tail); // 应输出: 40 20 } printf("\n");
// 测试5：尝试删除超出范围的索引 printf("Test 5: Delete out-of-range index (should fail)\n"); if (!delete_by_index(head, &tail, 3)) { printf("Correctly failed to delete at index 3\n\n"); }
// 测试6：尝试删除索引0 printf("Test 6: Delete at index 0 (should fail)\n"); if (!delete_by_index(head, &tail, 0)) { printf("Correctly failed to delete at index 0\n\n"); }
// 测试7：删除剩余的两个节点 printf("Test 7: Delete remaining nodes\n"); printf("Delete index 1: "); delete_by_index(head, &tail, 1); print_list_from_head(head); // 应输出: 40 printf("Delete index 1: "); delete_by_index(head, &tail, 1); print_list_from_head(head); // 应输出空行 // 验证链表是否为空 printf("Is list empty now? %s\n", (head->next == NULL) ? "Yes" : "No");
// 销毁链表 list_destroy(head, &tail); printf("List destroyed.\n");
return 0;}
复制代码
实验结果：
4.2 删除指定的元素（by value）
int delete_by_value(DuLinkList head, DuLNode **pTail, ElemType data){ if (NULL == head) { printf("[%s %d] head point is NULL\n", __FUNCTION__ , __LINE__); return 0; }
DuLNode *t = head->next; //遍历整个链表 while (t != NULL) { if (t->data != data) { t = t->next; continue; }
//判断是否需要删除的结点恰好是尾结点 if (t->next == NULL) { *pTail = t->pre; (*pTail)->next = NULL; free(t); return 1; }
//如果是中间结点 //先保存t结点的直接后继 DuLNode *bak = t->next; t->pre->next = t->next; t->next->pre = t->pre; free(t); t = bak; }
return 1;}
复制代码
验证：编写 main 函数，测试删除双向链表指定的元素函数delete_by_value。
注：验证前需要在 VS Code 中导入代码。
导入“双向链表初始化”章节代码；
导入“销毁双向链表”章节list_destroy函数代码；
导入“双向链表头插法”章节head_insert函数代码，以及其子章节“双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历” print_list_from_tail函数代码；
导入“删除指定的元素”章节delete_by_value代码。
int main() { // 初始化链表 DuLinkList head = list_init(); DuLNode *tail = NULL; printf("测试双向链表删除功能...\n\n"); // 测试1：从空链表删除 printf("测试1：从空链表删除（应该无变化）\n"); printf("删除前: "); print_list_from_head(head); delete_by_value(head, &tail, 5); printf("删除后: "); print_list_from_head(head); printf("\n"); // 插入一些元素 head_insert(head, &tail, 3); head_insert(head, &tail, 5); head_insert(head, &tail, 7); head_insert(head, &tail, 5); // 再次插入5 head_insert(head, &tail, 9); // 测试2：删除不存在的值 printf("测试2：删除不存在的值（10）\n"); printf("删除前: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); delete_by_value(head, &tail, 10); printf("删除后: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); printf("\n"); // 测试3：删除中间节点（第一个5） printf("测试3：删除中间节点（第一个5）\n"); printf("删除前: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); delete_by_value(head, &tail, 5); printf("删除后: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); printf("\n"); // 测试4：删除头节点（9） printf("测试4：删除头节点（9）\n"); printf("删除前: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); delete_by_value(head, &tail, 9); printf("删除后: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); printf("\n"); // 测试5：删除尾节点（3） printf("测试5：删除尾节点（3）\n"); printf("删除前: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); delete_by_value(head, &tail, 3); printf("删除后: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); printf("\n"); // 测试6：删除剩余所有节点（7和5） printf("测试6：删除剩余所有节点（7和5）\n"); printf("删除前: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); delete_by_value(head, &tail, 7); delete_by_value(head, &tail, 5); printf("删除后: "); print_list_from_head(head); printf("从尾部打印: "); print_list_from_tail(tail); printf("\n"); // 销毁链表 list_destroy(head, &tail); return 0;}
复制代码
实验结果：
四、综合实验：浏览器历史记录导航
1. 需求分析及代码实现
1.1 功能需求
本程序模拟了现代浏览器中的历史记录导航系统，使用双向链表数据结构实现，主要功能包括：
历史记录管理：记录用户访问的网页 URL 和时间戳。
导航功能：支持前进、后退等基本导航操作。
前进操作：导航到当前页面的下一个访问记录，自动处理边界情况（如已在最新记录时提示无法前进）。
后退操作：导航到当前页面的上一个访问记录，自动处理边界情况（如已在最早记录时提示无法后退）。
智能截断：当从历史记录中间位置访问新页面时，自动删除当前位置之后的所有记录，确保历史记录的线性连续性。
记录维护：提供多种方式管理历史记录
删除当前记录：删除当前正在浏览的页面记录，自动调整前后记录的链接关系，智能选择新的当前页面（优先后继，其次前驱）。
按 URL 删除记录：支持删除所有匹配特定 URL 的记录，URL 比较不区分大小写，批量删除所有匹配项。
清空历史记录：程序退出时自动释放所有内存，确保无内存泄漏。
可视化展示：以不同顺序展示历史记录
正向查看历史：按时间从早到晚顺序显示所有访问记录，格式化输出，包含时间戳和 URL。
反向查看历史：按时间从晚到早顺序显示所有访问记录，便于查看最近的访问历史。
当前页面显示：实时显示当前浏览页面的信息，包括 URL 和访问时间戳。
用户交互
1.2 编写实现
添加必要的头文件和宏，定义结构体。
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>#include <stdbool.h>#include <ctype.h>
#define MAX_URL_LENGTH 100#define MAX_HISTORY 100
typedef struct { char url[MAX_URL_LENGTH]; int timestamp; // 访问时间戳} HistoryEntry;
typedef struct DuLNode { HistoryEntry data; struct DuLNode *pre; struct DuLNode *next;} DuLNode, *DuLinkList;
复制代码
添加浏览器历史记录导航双向链表的初始化函数；
// 初始化链表DuLinkList list_init() { DuLinkList head = (DuLinkList)malloc(sizeof(DuLNode)); if (head == NULL) { perror("内存分配失败"); exit(EXIT_FAILURE); } head->next = NULL; head->pre = NULL; return head;}
复制代码
添加浏览器历史记录导航双向链表的销毁函数；
void list_destroy(DuLinkList head, DuLNode **pTail) { if (head == NULL) return;
DuLNode *current = head->next; while (current != NULL) { DuLNode *next = current->next; free(current); current = next; } free(head); *pTail = NULL;}
复制代码
添加浏览器历史记录导航双向链表的头部插入函数；
bool head_insert(DuLinkList head, DuLNode **pTail, HistoryEntry data) { if (head == NULL) return false;
DuLNode *new_node = (DuLNode *)malloc(sizeof(DuLNode)); if (new_node == NULL) return false; new_node->data = data; new_node->pre = head; new_node->next = head->next;
if (head->next != NULL) { head->next->pre = new_node; } else { *pTail = new_node; // 如果是空链表，新节点也是尾节点 } head->next = new_node; return true;}
复制代码
添加浏览器历史记录导航双向链表的尾部插入函数；
bool tail_insert(DuLinkList head, DuLNode **pTail, HistoryEntry data) { if (head == NULL) return false;
DuLNode *new_node = (DuLNode *)malloc(sizeof(DuLNode)); if (new_node == NULL) return false; new_node->data = data; new_node->next = NULL;
if (*pTail == NULL) { // 空链表 new_node->pre = head; head->next = new_node; } else { new_node->pre = *pTail; (*pTail)->next = new_node; } *pTail = new_node; return true;}
复制代码
添加浏览器历史记录导航双向链表的遍历打印函数；
void print_history_forward(DuLinkList head) { if (head == NULL) return;
printf("\n历史记录(按时间从早到晚):\n"); printf("--------------------------------\n"); DuLNode *current = head->next; while (current != NULL) { printf("[%d] %s\n", current->data.timestamp, current->data.url); current = current->next; } printf("--------------------------------\n");}
// 打印历史记录 (从尾开始)void print_history_backward(DuLNode *tail) { if (tail == NULL) return;
printf("\n历史记录(按时间从晚到早):\n"); printf("--------------------------------\n"); DuLNode *current = tail; while (current->pre != NULL) { // 直到头节点停止 printf("[%d] %s\n", current->data.timestamp, current->data.url); current = current->pre; } printf("--------------------------------\n");}
复制代码
添加浏览器历史记录导航双向链表的删除特定 URL 函数；
// 删除特定URL的历史记录bool delete_history_by_url(DuLinkList head, DuLNode **pTail, const char *url) { if (head == NULL || url == NULL) return false;
bool deleted = false; DuLNode *current = head->next; while (current != NULL) { if (strcmp(current->data.url, url)) { current = current->next; continue; }
DuLNode *toDelete = current; current = current->next; // 先移动到下一个节点 // 调整链表指针 toDelete->pre->next = toDelete->next; if (toDelete->next != NULL) { toDelete->next->pre = toDelete->pre; } else { *pTail = toDelete->pre; // 更新尾指针 } free(toDelete); deleted = true; }
return deleted;}
复制代码
添加浏览器历史记录导航双向链表的删除当前历史记录函数；
// 删除当前记录bool delete_current_history(DuLinkList head, DuLNode **pTail, DuLNode **current) { if (*current == NULL) return false;
DuLNode *toDelete = *current; // 确定新的当前页面 if (toDelete->next != NULL) { *current = toDelete->next; } else if (toDelete->pre != head) { *current = toDelete->pre; } else { *current = NULL; // 没有其他页面了 }
// 调整链表指针 toDelete->pre->next = toDelete->next; if (toDelete->next != NULL) { toDelete->next->pre = toDelete->pre; } else { *pTail = toDelete->pre; // 更新尾指针 } free(toDelete); return true;}
复制代码
添加浏览器历史记录导航双向链表的辅助函数清空控制台和转换大小写；
// 清除控制台void clear_screen() { system("clear || cls");}
// 转换为小写void to_lower_case(char *str) { for (int i = 0; str[i]; i++) { str[i] = tolower(str[i]); }}
复制代码
添加浏览器历史记录导航的浏览器模拟主函数；
// 浏览器模拟主函数void browser_simulation() { DuLinkList history = list_init(); DuLNode *tail = NULL; DuLNode *current = NULL; int time = 1; clear_screen(); printf("=== 浏览器历史记录模拟 ===\n"); // 添加初始历史记录 HistoryEntry initial_entries[] = { {"www.homepage.com", time++}, {"www.news.com", time++}, {"www.mail.com", time++}, {"www.social.com", time++} }; for (int i = 0; i < 4; i++) { tail_insert(history, &tail, initial_entries[i]); } current = tail; // 主循环 int choice; char input_url[MAX_URL_LENGTH]; do { printf("\n当前页面: "); if (current != NULL) { printf("[%d] %s\n", current->data.timestamp, current->data.url); } else { printf("无\n"); } printf("\n1. 访问新网页\n2. 后退\n3. 前进\n4. 删除当前记录\n" "5. 删除特定URL记录\n6. 显示历史记录\n7. 清屏\n0. 退出\n选择: "); if (scanf("%d", &choice) != 1) { while (getchar() != '\n'); // 清除输入缓冲区 printf("无效输入，请输入数字选项\n"); continue; } clear_screen(); switch(choice) { case 1: { // 访问新网页 printf("输入URL: "); scanf("%99s", input_url); // 如果当前不是最后一条记录，截断后面的历史 if (current != tail) { DuLNode *temp = current->next; while (temp != NULL) { DuLNode *next = temp->next; free(temp); temp = next; } tail = current; tail->next = NULL; } HistoryEntry new_entry; strncpy(new_entry.url, input_url, MAX_URL_LENGTH); new_entry.timestamp = time++; if (tail_insert(history, &tail, new_entry)) { current = tail; printf("已访问: %s\n", input_url); } else { printf("访问失败\n"); } break; } case 2: { // 后退 if (current != NULL && current->pre != history) { current = current->pre; printf("已后退到: [%d] %s\n", current->data.timestamp, current->data.url); } else { printf("无法后退\n"); } break; } case 3: { // 前进 if (current != NULL && current->next != NULL) { current = current->next; printf("已前进到: [%d] %s\n", current->data.timestamp, current->data.url); } else { printf("无法前进\n"); } break; } case 4: { // 删除当前记录 if (current != NULL) { char current_url[MAX_URL_LENGTH]; strcpy(current_url, current->data.url); if (delete_current_history(history, &tail, ¤t)) { printf("已删除当前记录: %s\n", current_url); } else { printf("删除失败\n"); } } else { printf("无当前记录可删除\n"); } break; } case 5: { // 删除特定URL记录 printf("输入要删除的URL: "); scanf("%99s", input_url); to_lower_case(input_url); if (delete_history_by_url(history, &tail, input_url)) { printf("已删除所有匹配的URL记录: %s\n", input_url); // 如果当前页面被删除，调整current指针 if (current != NULL && strcmp(current->data.url, input_url) == 0) { if (current->next != NULL) { current = current->next; } else if (current->pre != history) { current = current->pre; } else { current = NULL; } } } else { printf("未找到匹配的URL记录: %s\n", input_url); } break; } case 6: { // 显示历史记录 print_history_forward(history); print_history_backward(tail); break; } case 7: { // 清屏 clear_screen(); break; } case 0: { // 退出 printf("退出浏览器...\n"); break; } default: printf("无效选择，请重新输入\n"); } } while (choice != 0); // 清理资源 list_destroy(history, &tail);}
int main() { browser_simulation(); return 0;}
复制代码
1.3 功能演示
程序启动：双向链表初始化，此时链表中包含四条数据，默认显示最后插入的www.social.com。
访问新网页：控制台输入 1，回车，进入 URL 输入界面，编写输入www.baidu.com回车，当前页面变成刚才输入的 URL 地址。
后退：控制台输入 2，回车，界面自动切换为上一个浏览记录www.social.com。
前进：控制台输入 3，回车，界面自动切换为上一个浏览记录www.baidu.com。
删除当前记录：控制台输入 4，回车，删除当前的页面www.baidu.com，并且将当前页面变更为www.social.com。
删除特定 URL 记录：控制台输入 5，回车，如果输入的 URL 在链表中不存在则提示“未找到匹配的 URL 记录”。如果输入的 URL 存在则显示删除成功。
显示历史记录：控制台输入 6，回车，控制台分别正反向打印历史记录。
清屏：控制台输入 7，回车，控制台清屏。
退出：控制台输入 0，回车，退出浏览器。
2. 总结
双向链表的特性总结：
双向链表的基本特点
双向链表是一种链式存储结构，每个节点包含数据域和两个指针域（前驱指针和后继指针），可以从任意节点向前或向后遍历整个链表。
双向链表的优点
双向链表的缺点
适用场景
最适合使用双向链表的场景：
需要频繁在任意位置插入/删除数据；需要双向遍历数据集合；数据规模经常变化且难以预测；实现撤销/重做、浏览器历史记录等需要双向导航的功能。
不适合使用双向链表的场景：
数据量固定且需要频繁随机访问；内存资源极其有限的嵌入式系统；对缓存性能要求极高的应用；只需要单向遍历的简单场景。
案例总结：
本案例主要包含三部分内容，开发者空间与 VS Code 开发环境配置、双向链表的基本操作以及最后的综合实验浏览器历史记录导航。
双向链表的基本操作，系统的学习了双向链表的初始化、销毁、插入、输出、删除等操作逻辑和代码实现。最后我们通过一个浏览器历史记录导航系统，展示了双向链表在实际应用中的灵活性和实用性。
双向链表通过牺牲部分空间效率换取了更高的操作灵活性，在特定场景下能提供单链表和数组无法比拟的操作优势。选择是否使用双向链表应当基于具体的应用需求和对各项性能指标的权衡。适用于如：浏览器历史记录管理（如本程序实现）、文本编辑器中的撤销/重做功能、音乐播放器的播放列表、操作系统中的进程调度等场景。
评论