数据结构：双向链表详解与实现

数据结构：双向链表

链表的分类

常见的链表分类主要包括单向、双向以及循环结构。理解这些分类有助于根据实际场景选择合适的存储方式。

链表分类示意图

循环链表示意图

概念与结构

概念

双向链表通常采用带头结点的设计，这里的'头结点'实际上是一个哨兵位。它不存储有效数据，仅作为链表的固定入口，简化了边界条件的处理（如头插、头删时无需特殊判断空指针）。

注意：哨兵位结点不存储任何有效元素，只是站在这里'放哨的'。

结构定义

在 C 语言中，我们需要定义节点结构和链表操作接口。

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

// 销毁
LTNode* LTDestroy(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);

// 打印
void LTPrint(LTNode* phead);

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x);

// 插入 / 删除
void LTInsert(LTNode* pos, LTDataType x); // 在 pos 之后插入
void LTErase(LTNode* pos);                // 删除 pos 位置节点

核心实现细节

申请新节点

分配内存时务必检查是否成功，并初始化指针指向自身以形成闭环。

LTNode* LTBuyNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc failed!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode; // 初始化为自环
    return newnode;
}

初始化与销毁

初始化直接返回哨兵节点，销毁时记得释放哨兵本身并将头指针置空。

LTNode* LTInit() {
    LTNode* phead = LTBuyNode(-1); // -1 仅为哨兵占位符
    return phead;
}

LTNode* LTDestroy(LTNode* phead) {
    assert(phead != NULL);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    free(phead); // 最后释放哨兵
    return NULL;
}

插入操作

插入是双向链表最容易出错的地方，指针修改顺序至关重要。如果先改了后继，再改前驱，可能会丢失原节点地址导致断链或内存泄漏。

尾插逻辑：

新节点的前驱指向当前尾节点（哨兵的前驱）。
新节点的后继指向哨兵。
原尾节点的后继指向新节点。
哨兵的前驱指向新节点。

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    // 关键顺序：先连后，再连前
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev->next = newnode;
    phead->prev = newnode;
}

头插逻辑： 同理，注意不要覆盖 phead->next 的地址。

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->next = phead->next;
    newnode->prev = phead;
    phead->next->prev = newnode;
    phead->next = newnode;
}

删除操作

删除时同样要注意顺序，先断开连接，再释放内存。

尾删： 直接操作哨兵的前驱节点即可。

void LTPopBack(LTNode* phead) {
    assert(!LTEmpty(phead));
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

头删：

void LTPopFront(LTNode* phead) {
    assert(!LTEmpty(phead));
    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

任意位置插入与删除：

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    newnode->prev = pos;
    newnode->next = pos->next;
    pos->next->prev = newnode;
    pos->next = newnode;
}

void LTErase(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

辅助功能

判空只需判断头节点的后继是否指向自己。打印则遍历一圈即可。

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

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

LTNode* LTFind(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    return NULL;
}

顺序表与链表分析

通过对比表格可以更直观地理解两者的差异：

不同点	顺序表	链表（双向）
存储空间	物理上连续	逻辑连续，物理不一定连续
随机访问	支持 O(1)	不支持，需遍历 O(N)
插入/删除	可能涉及大量搬移 O(N)	仅需修改指针，O(1)
空间管理	需扩容，存在浪费	按需申请，无容量限制
适用场景	频繁读取，尾部操作多	频繁增删，头部操作多

在实际开发中，若对查询效率要求高且数据量稳定，首选顺序表；若数据变动频繁且位置不确定，链表则是更好的选择。