一、概述

1. 案例介绍

在现代软件开发中，数据结构的选择对程序的性能和可维护性有着至关重要的影响。数组和链表作为两种最基本的数据结构，分别适用于不同的场景。理解它们的特性和优劣，能够帮助开发者在实际项目中做出更合理的技术选型，从而优化系统性能。

双向链表通过在节点中添加一个指向前驱的指针 (prev)，克服了单向链表只能单向遍历和难以直接访问前驱节点的缺点。它以额外的内存开销为代价，换取了双向遍历能力和在任意已知节点位置进行高效插入、删除操作的能力。这种特性使得双向链表在需要频繁双向操作或在链表中间进行修改的场景中非常有用，是构建更高级数据结构（如双端队列、LRU缓存）的基础组件之一。

华为开发者空间，是为全球开发者打造的专属开发者空间，致力于为每位开发者提供一台云主机、一套开发工具和云上存储空间，汇聚昇腾、鸿蒙、鲲鹏、GaussDB、欧拉等华为各项根技术的开发工具资源，并提供配套案例指导开发者 从开发编码到应用调测，基于华为根技术生态高效便捷的知识学习、技术体验、应用创新。

2. 适用对象

• 个人开发者
• 高校学生

3. 案例时间

本案例总时长预计90分钟。

4. 案例流程

说明：

1. 开通开发者空间，搭建C/C++开发环境。
2. 打开VS Code，编写代码运行程序。

5. 资源总览

本案例预计花费0元。

资源名称	规格	单价（元）	时长（分钟）
开发者空间-云主机	4vCPUs | 8GB ARM Ubuntu Ubuntu 24.04 Server 定制版	免费	90
VS Code	1.97.2	免费	90

最新案例动态，请查阅 《双向链表的奥妙-浏览器航海家》。小伙伴快来领取华为开发者空间进行实操吧！

二、配置实验环境

1. 开发者空间配置

面向广大开发者群体，华为开发者空间提供一个随时访问的“开发桌面云主机”、丰富的“预配置工具集合”和灵活使用的“场景化资源池”，开发者开箱即用，快速体验华为根技术和资源。

如果还没有领取开发者空间云主机，可以参考免费领取云主机文档领取。

领取云主机后可以直接进入华为开发者空间工作台界面，点击打开云主机 > 进入桌面连接云主机。

2. 配置开发环境

参考案例中心《基于开发者空间，定制C&C++开发环境云主机镜像》“2. 实验环境搭建”、“3. VS Code安装部署”章节完成开发环境、VS code及插件安装。

三、双向链表的基本操作

1. 双向链表的初始化

1. 导入必要的头文件。

#include <stdio.h>
#include <stdlib.h>

2. 定义双向链表的节点。

typedef int ElemType;

typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *pre; //指向前驱结点的指针
    struct DuLNode *next; //指向后继结点的指针
}DuLNode, *DuLinkList;

3. 初始化双向链表。

如上图所示，链表的头节点的数据域不存储数据，指向前驱节点的指针域值为null，指向后继节点的指针域指向第一个真正存储数据的节点。因此双向链表初始化实现如下。

DuLinkList list_init()
{
    DuLinkList head;
    //创建一个头结点，使用head指针指向头结点（头指针）
    head = (DuLinkList)malloc(sizeof(DuLNode));
    head->next = NULL;
    head->pre = NULL;
    return head;
}

2. 销毁双向链表

1. 检查头节点指针head是否为NULL，是则打印错误并返回；
2. 遍历整个链表，直到最后一个节点前停止；
   • 头结点的next指向t的后继结点；（对应上图中的）
   • t的后继结点的pre指向头结点；（对应上图中的）
   • 释放当前节点t；
   • t指向头节点；
3. 断开head->next；
4. 释放尾节点t；
5. 释放头节点；
6. 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 双向链表头插法

1. 新建一个节点p将其前、后继指针域置空，数据域存储需要储存的数据；
2. 如果链表为空，则新插入的节点p为尾节点，此时将头节点的next 指针从原首节点改为指向新节点 p；
3. 如果链表不为空：

• 将新节点p的next指针指向原首节点，此时新节点p就“接管”了原首节点的位置，成为新的首节点，而 p->next 则链接着原来的链表（对应上图中的）；
• 头节点的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中导入代码。

1. 导入“双向链表初始化”章节代码；
2. 导入“销毁双向链表”章节list_destroy函数代码；
3. 导入“双向链表头插法”章节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 双向链表尾插法

1. 新建一个节点p将其前、后继指针域置空，数据域存储需要储存的数据；
2. 判断如果链表为空，则p节点的前驱指针指向head节点，head的后继指针指向p节点；
3. 如果链表不为空，则原尾节点的后继指针指向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中导入代码。

1. 导入“双向链表初始化”章节代码；
2. 导入“销毁双向链表”章节list_destroy函数代码；
3. 导入 “双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历”print_list_from_tail函数代码。
4. 导入“双向链表尾插法”章节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 双向链表指定位置插入节点

1. 新建一个节点p将其前、后继指针域置空，数据域存储需要储存的数据；
2. 将节点p的后继指针指向t节点（对应上图中的），将p节点的前驱指针指向修改为t节点的前驱指针指向（对应上图中的）；
3. 将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中导入代码。

1. 导入“双向链表初始化”章节代码；
2. 导入“销毁双向链表”章节list_destroy函数代码；
3. 导入 “双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历”print_list_from_tail函数代码。
4. 导入“双向链表指定位置插入节点”章节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）

1. 遍历双项链表，如果要删除的结点恰好是尾结点，则将*pTail修改为t节点的前驱；
2. 如果是中间节点：

• 则将t节点的前一个节点的后继指针指向t的后继指向的节点（对应上图中的）；
• 将t的后一个节点的前驱指针指向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中导入代码。

1. 导入“双向链表初始化”章节代码；
2. 导入“销毁双向链表”章节list_destroy函数代码；
3. 导入“双向链表头插法”章节head_insert函数代码，以及其子章节“双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历” print_list_from_tail函数代码；
4. 导入“删除指定的节点”章节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中导入代码。

1. 导入“双向链表初始化”章节代码；
2. 导入“销毁双向链表”章节list_destroy函数代码；
3. 导入“双向链表头插法”章节head_insert函数代码，以及其子章节“双向链表从头节点开始遍历”的print_list_from_head函数和“双向链表从尾节点开始遍历” print_list_from_tail函数代码；
4. 导入“删除指定的元素”章节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 功能需求

本程序模拟了现代浏览器中的历史记录导航系统，使用双向链表数据结构实现，主要功能包括：

1. 历史记录管理：记录用户访问的网页URL和时间戳。

• 使用双向链表存储历史记录，每个节点包含URL字符串和访问时间戳，维护头指针和尾指针实现高效操作，支持最多100个字符的URL长度。

2. 导航功能：支持前进、后退等基本导航操作。

• 前进操作：导航到当前页面的下一个访问记录，自动处理边界情况（如已在最新记录时提示无法前进）。
• 后退操作：导航到当前页面的上一个访问记录，自动处理边界情况（如已在最早记录时提示无法后退）。
• 智能截断：当从历史记录中间位置访问新页面时，自动删除当前位置之后的所有记录，确保历史记录的线性连续性。

3. 记录维护：提供多种方式管理历史记录

• 删除当前记录：删除当前正在浏览的页面记录，自动调整前后记录的链接关系，智能选择新的当前页面（优先后继，其次前驱）。
• 按URL删除记录：支持删除所有匹配特定URL的记录，URL比较不区分大小写，批量删除所有匹配项。
• 清空历史记录：程序退出时自动释放所有内存，确保无内存泄漏。

4. 可视化展示：以不同顺序展示历史记录

• 正向查看历史：按时间从早到晚顺序显示所有访问记录，格式化输出，包含时间戳和URL。
• 反向查看历史：按时间从晚到早顺序显示所有访问记录，便于查看最近的访问历史。
• 当前页面显示：实时显示当前浏览页面的信息，包括URL和访问时间戳。

5. 用户交互

• 菜单系统：清晰的数字选项菜单，包含7个主要功能和退出选项，输入错误处理和提示。
• 交互提示：每个操作都有明确的反馈，成功/失败都有相应提示，边界情况有友好提示。

1.2 编写实现

1. 添加必要的头文件和宏，定义结构体。

#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;

2. 添加浏览器历史记录导航双向链表的初始化函数；

// 初始化链表
DuLinkList list_init() {
    DuLinkList head = (DuLinkList)malloc(sizeof(DuLNode));
    if (head == NULL) {
        perror("内存分配失败");
        exit(EXIT_FAILURE);
    }
    head->next = NULL;
    head->pre = NULL;
    return head;
}

3. 添加浏览器历史记录导航双向链表的销毁函数；

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;
}

4. 添加浏览器历史记录导航双向链表的头部插入函数；

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;
}

5. 添加浏览器历史记录导航双向链表的尾部插入函数；

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;
}

6. 添加浏览器历史记录导航双向链表的遍历打印函数；

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");
}

7. 添加浏览器历史记录导航双向链表的删除特定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;
}

8. 添加浏览器历史记录导航双向链表的删除当前历史记录函数；

// 删除当前记录
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;
}

9. 添加浏览器历史记录导航双向链表的辅助函数清空控制台和转换大小写；

// 清除控制台
void clear_screen() {
    system("clear || cls");
}

// 转换为小写
void to_lower_case(char *str) {
    for (int i = 0; str[i]; i++) {
        str[i] = tolower(str[i]);
    }
}

10. 添加浏览器历史记录导航的浏览器模拟主函数；

// 浏览器模拟主函数
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, &current)) {
                        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 功能演示

1. 程序启动：双向链表初始化，此时链表中包含四条数据，默认显示最后插入的www.social.com。

2. 访问新网页：控制台输入1，回车，进入URL输入界面，编写输入www.baidu.com回车，当前页面变成刚才输入的URL地址。

3. 后退：控制台输入2，回车，界面自动切换为上一个浏览记录www.social.com。

4. 前进：控制台输入3，回车，界面自动切换为上一个浏览记录www.baidu.com。

5. 删除当前记录：控制台输入4，回车，删除当前的页面www.baidu.com，并且将当前页面变更为www.social.com。

6. 删除特定URL记录：控制台输入5，回车，如果输入的URL在链表中不存在则提示“未找到匹配的URL记录”。如果输入的URL存在则显示删除成功。

7. 显示历史记录：控制台输入6，回车，控制台分别正反向打印历史记录。

8. 清屏：控制台输入7，回车，控制台清屏。

9. 退出：控制台输入0，回车，退出浏览器。

2. 总结

双向链表的特性总结：

1. 双向链表的基本特点

双向链表是一种链式存储结构，每个节点包含数据域和两个指针域（前驱指针和后继指针），可以从任意节点向前或向后遍历整个链表。

2. 双向链表的优点

• 双向遍历能力
• 可以从头到尾或从尾到头遍历链表；
• 每个节点都能直接访问其前驱和后继节点；
• 特别适合需要双向查找的场景（如浏览器历史记录）。
• 高效的插入/删除操作
• 在已知节点位置时，插入和删除操作的时间复杂度为O(1)；
• 无需像单链表那样需要先找到前驱节点；
• 删除节点时更加高效（可直接通过前驱指针修改相邻节点）。
• 灵活的内存管理
• 动态内存分配，不需要预先知道数据规模；
• 可以高效地实现内存的利用和回收。

3. 双向链表的缺点

• 内存开销较大
• 每个节点需要存储两个指针（相比单链表多一个指针）；
• 对于小数据项，指针开销可能比实际数据还大。
• 实现复杂度较高
• 需要维护两个方向的指针，编程更复杂；
• 插入/删除操作需要考虑更多指针修改情况；
• 容易出现指针操作错误导致的内存问题。
• 缓存不友好
• 节点内存不连续，缓存命中率低于数组；
• 随机访问性能较差（相比数组）。
• 没有固定索引
• 不能像数组那样直接通过索引访问元素；
• 查找特定元素需要遍历（时间复杂度O(n)）。

4. 适用场景

最适合使用双向链表的场景：

需要频繁在任意位置插入/删除数据；需要双向遍历数据集合；数据规模经常变化且难以预测；实现撤销/重做、浏览器历史记录等需要双向导航的功能。

不适合使用双向链表的场景：

数据量固定且需要频繁随机访问；内存资源极其有限的嵌入式系统；对缓存性能要求极高的应用；只需要单向遍历的简单场景。

案例总结：

本案例主要包含三部分内容，开发者空间与VS Code开发环境配置、双向链表的基本操作以及最后的综合实验浏览器历史记录导航。

双向链表的基本操作，系统的学习了双向链表的初始化、销毁、插入、输出、删除等操作逻辑和代码实现。最后我们通过一个浏览器历史记录导航系统，展示了双向链表在实际应用中的灵活性和实用性。

双向链表通过牺牲部分空间效率换取了更高的操作灵活性，在特定场景下能提供单链表和数组无法比拟的操作优势。选择是否使用双向链表应当基于具体的应用需求和对各项性能指标的权衡。适用于如：浏览器历史记录管理（如本程序实现）、文本编辑器中的撤销/重做功能、音乐播放器的播放列表、操作系统中的进程调度等场景。