数据结构：双向链表原理与 C 语言实现

数据结构：双向链表

在数据结构中，双向链表是基础且重要的线性表结构。相比单链表，它在每个节点中增加了前驱指针，使得遍历更加灵活，支持双向查找。

概念与结构

核心概念

双向链表通常采用带头结点的循环结构。这里的'头结点'是一个哨兵位，不存储有效数据，仅用于简化边界条件的处理（如空表判断、首尾插入）。

节点定义

// 定义数据类型
typedef int LTDataType;

// 定义双向链表节点结构
typedef struct ListNode {
    LTDataType data;
    struct ListNode* next; // 指向下一个节点
    struct ListNode* prev; // 指向前一个节点
} LTNode;

接口设计

为了保持接口的统一性和易用性，我们约定所有操作函数都接收头指针 LTNode* phead。初始化函数直接返回头指针，销毁函数也返回 NULL 以便接收者重置指针。

// 初始化
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 节点

核心操作实现

1. 节点申请与初始化

申请新节点时，需要分配内存并检查是否成功。对于带头结点的循环链表，新节点初始化时可以先自环，或者在插入时再调整。

LTNode* LTBuyNode(LTDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = newnode->prev = newnode;
    return newnode;
}

LTNode* LTInit() {
    // 创建一个哨兵节点，数据可以是任意值，这里用 -1 示意
    LTNode* phead = LTBuyNode(-1);
    return phead;
}

2. 销毁链表

销毁时需要遍历所有有效节点释放内存，最后释放头结点。注意使用二级指针或返回值来更新外部指针，防止野指针。

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

3. 插入操作

尾插

在尾部插入时，要注意修改指针的顺序。先连接新节点与旧尾节点，再连接新节点与头结点，最后更新头结点的前驱指针。

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

头插

逻辑与尾插类似，只是方向相反。先连接新节点与旧头节点，再连接新节点与头结点。

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

指定位置后插入

在 pos 节点之后插入，只需将 pos 的后继节点作为桥梁即可。

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

4. 删除操作

尾删与头删

删除时需确保链表非空。删除后记得将断开节点的指针置为 NULL，避免悬垂指针。

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 LTErase(LTNode* pos) {
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    free(pos);
    pos = NULL;
}

5. 辅助功能

判空

由于是循环链表，当 next 指向自己时，说明只有头结点，即为空。

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)
空间管理	动态扩容，可能有浪费	按需申请，无容量限制
适用场景	频繁读取，少增删	频繁增删，少随机访问

通过上述分析可以看出，双向链表在插入和删除操作上具有显著优势，适合对数据变动频繁的场景；而顺序表则在访问效率上更胜一筹。实际开发中，应根据具体需求选择合适的结构。