数据结构：双向链表

一、什么是双向链表？

双向链表是一种链式存储结构，每个节点除了存储数据外，还包含两个指针，分别指向前一个节点（prev）和后一个节点（next）。这与单向链表不同，双向链表允许我们在链表中向前或向后遍历，非常灵活。

二、程序的作用和意义

通过实现双向链表，我们可以更灵活地管理数据。相比数组，链表在插入和删除时更加高效，特别是当操作发生在链表中间位置时，不需要移动其他元素。双向链表在实际开发中有广泛的应用，比如在缓存、操作系统中的任务管理、文本编辑器等地方，都可以看到双向链表的身影。

三、双向链表结构图解

假设我们有以下的双向链表：

[head] <--> [1] <--> [2] <--> [3] <--> [4] <--> [head]

1. head 是哨兵节点（不存储实际数据，仅作链表的头和尾）。
2. 每个节点都可以通过 next 指针访问下一个节点，通过 prev 指针访问上一个节点。
3. 双向链表具有环形结构，最后一个节点的 next 指针指向 head，第一个节点的 prev 指针也指向 head。

四、 双向链表的基本结构

我们先看一下在C语言中如何定义双向链表节点的结构体：

typedef int LTDataType; // 链表中的数据类型
typedef struct ListNode {
    LTDataType data; // 节点数据
    struct ListNode* next; // 指向下一个节点
    struct ListNode* prev; // 指向上一个节点
} LTNode;

每个节点存储一个data，以及两个指针next和prev，用来分别指向下一个和上一个节点。

五、 双向链表的基本操作

接下来我们讨论双向链表的几种常见操作，包括初始化、插入、删除、查找、打印等。我们将逐步介绍这些操作的实现原理和注意事项。

5.1 初始化链表

初始化时，我们通常创建一个“哨兵节点”，这个节点不存储实际的数据，只是为了方便后续操作。哨兵节点的next指针指向链表的第一个节点，prev指针指向链表的最后一个节点。以下是链表初始化的代码：

LTNode* LTInit() {
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode)); // 创建哨兵节点
    phead->data = -1; // 哨兵节点通常存放无意义的数据
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

5.2 尾插法（在链表末尾插入节点）

尾插法是向链表的末尾添加新节点的一种方式。具体操作如下：

• 新节点的prev指向当前链表的最后一个节点。
• 新节点的next指向哨兵节点。
• 调整哨兵节点和原最后一个节点的指针，指向新节点。

代码如下：

// 尾插法
void LTPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);

    // 插入新节点到尾部
    newnode->next = phead;           // 新节点next指向哨兵
    newnode->prev = phead->prev;     // 新节点prev指向原最后节点

    phead->prev->next = newnode;     // 原最后节点的next指向新节点
    phead->prev = newnode;           // 哨兵的prev指向新节点
}

5.3 头插法（在链表头部插入节点）

头插法与尾插法类似，只是新节点被插入到哨兵节点之后，第一个有效节点之前。注意指针的调整顺序：

// 头插法
void LTPushFront(LTNode* phead, LTDataType x)
{
    assert(phead);
    LTNode* newnode = LTBuyNode(x);

    // 插入新节点到头部
    newnode->next = phead->next;    // 新节点的next指向原第一节点
    newnode->prev = phead;          // 新节点的prev指向哨兵

    phead->next->prev = newnode;    // 原第一节点的prev指向新节点
    phead->next = newnode;          // 哨兵的next指向新节点
}

5.4 删除链表尾部节点

删除尾部节点需要修改链表末尾节点的前一个节点和哨兵节点的prev指针，断开它们与被删除节点的连接：

// 尾部删除
void LTPopBack(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));  // 确保链表不为空

    LTNode* del = phead->prev;  // 找到最后一个节点
    del->prev->next = phead;    // 修改倒数第二个节点的next指向哨兵
    phead->prev = del->prev;    // 修改哨兵的prev指向倒数第二个节点

    free(del);  // 释放被删除的节点内存
}

5.5 删除链表头部节点

删除头部节点类似尾部删除，只是需要调整的是哨兵节点和第二个节点的指针：

// 头部删除
void LTPopFront(LTNode* phead)
{
    assert(phead);
    assert(!LTEmpty(phead));  // 确保链表不为空

    LTNode* del = phead->next;  // 找到第一个有效节点
    phead->next = del->next;    // 哨兵的next指向第二个节点
    del->next->prev = phead;    // 第二个节点的prev指向哨兵

    free(del);  // 释放被删除的节点内存
}

5.6 查找节点

我们可以通过遍历链表来查找某个特定值的节点：

LTNode* LTFind(LTNode* phead, LTDataType x) {
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur; // 找到节点
        }
        pcur = pcur->next;
    }
    return NULL; // 没有找到
}

5.7 插入节点（在指定节点后插入）

当我们需要在某个节点pos之后插入节点时，可以这样做：

void LTInsert(LTNode* pos, LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 创建新节点
    newnode->data = x;
    newnode->next = pos->next;
    newnode->prev = pos;

    pos->next->prev = newnode;
    pos->next = newnode;
}

5.8 删除指定节点

删除指定节点时，需要将节点前后的节点指针重新连接：

// 删除指定位置的节点
void LTErase(LTNode* pos)
{
    assert(pos);
    pos->prev->next = pos->next;  // 修改前后节点的链接
    pos->next->prev = pos->prev;

    free(pos);  // 释放节点内存
}

5.9 打印链表

为了查看链表的内容，可以遍历链表并输出每个节点的数据：

void LTPrint(LTNode* phead) {
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

5.10打印链表中的数据

// 打印链表中的数据
void LTPrint(LTNode* phead)
{
    LTNode* pcur = phead->next;  // 从第一个有效节点开始遍历
    while (pcur != phead)
    {
        printf("%d -> ", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

5.11判断链表是否为空 

//c
bool LTEmpty(LTNode* phead)
{
    assert(phead);
    return phead->next == phead;
}

5.12销毁链表

// 销毁链表
void LTDesTroy(LTNode** pphead)
{
    assert(pphead && *pphead);
    LTNode* pcur = (*pphead)->next;

    while (pcur != *pphead)
    {
        LTNode* next = pcur->next;
        free(pcur);  // 逐个释放节点
        pcur = next;
    }
    free(*pphead);  // 释放哨兵节点
    *pphead = NULL;
}

六、双向链表的实现

在下面的代码中，我们将实现一个基本的双向链表，包含初始化、插入、删除、查找等基本操作。

List.h
#pragma once

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

// 双向链表节点定义
typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;          // 节点存储的数据
    struct ListNode* next;    // 指向下一个节点的指针
    struct ListNode* prev;    // 指向前一个节点的指针
} LTNode;

// 函数声明
LTNode* LTInit();  // 初始化双向链表
void LTDesTroy(LTNode** pphead);  // 销毁双向链表
void LTDesTroy2(LTNode* phead);   // 销毁链表 (传一级指针)

void LTPrint(LTNode* phead);      // 打印链表
void LTPushBack(LTNode* phead, LTDataType x);   // 末尾插入
void LTPushFront(LTNode* phead, LTDataType x);  // 头部插入
void LTPopBack(LTNode* phead);    // 末尾删除
void LTPopFront(LTNode* phead);   // 头部删除
bool LTEmpty(LTNode* phead);      // 判断链表是否为空
LTNode* LTFind(LTNode* phead, LTDataType x);    // 查找元素
void LTInsert(LTNode* pos, LTDataType x);       // 在指定位置插入
void LTErase(LTNode* pos);        // 删除指定节点

七、易错点和细节

1. 指针的正确使用：链表中的每个操作都涉及大量的指针操作。插入、删除节点时需要特别注意节点指针的调整顺序，否则可能导致链表断裂或出现悬空指针。
2. 内存管理：在删除节点时，一定要记得free掉节点占用的内存，避免内存泄漏。
3. 哨兵节点的使用：哨兵节点的引入可以简化代码，使得处理空链表或只有一个节点的特殊情况更加方便。但是要注意，哨兵节点本身不存储有效数据。

八、总结

双向链表是链表的一种扩展形式，允许我们双向遍历数据。在C语言中，链表通过指针来实现，操作灵活，但需要小心指针操作和内存管理。通过本文介绍的代码和细节，大家可以掌握双向链表的基本实现方式，同时避免常见的错误。