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

代码实现细节

申请新节点

创建节点时，除了分配内存，还要检查是否成功。对于循环双向链表，新节点初始状态应指向自身。

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() {
    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);
    
    // 1. 新节点连向尾部
    newnode->prev = phead->prev;
    newnode->next = phead;
    
    // 2. 原尾部连向新节点
    phead->prev->next = newnode;
    
    // 3. 更新头结点的 prev 指针
    phead->prev = newnode;
}

// 头插
void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    
    // 1. 新节点连向头部
    newnode->next = phead->next;
    newnode->prev = phead;
    
    // 2. 原头部连向新节点
    phead->next->prev = newnode;
    
    // 3. 更新头结点的 next 指针
    phead->next = newnode;
}

删除操作（尾删与头删）

删除时同样要注意指针的重新连接。由于是循环链表，判空条件为 phead->next == phead。

// 尾删
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;
}

通用查找与定位操作

查找元素返回节点指针，若未找到则返回 NULL。插入和删除基于指定位置 pos 进行操作。

// 查找元素
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;
}

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

// 删除 pos 位置的节点
void LTErase(LTNode* pos) {
    assert(pos);
    
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    
    free(pos);
    pos = NULL;
}

辅助功能

打印链表用于调试，判空用于逻辑控制。

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

// 链表判空
bool LTEmpty(LTNode* phead) {
    assert(phead);
    return phead->next == phead;
}

顺序表与链表的对比分析

理解不同数据结构的特性有助于在实际开发中做出选择。下表总结了顺序表与链表的主要区别：

在实际项目中，如果涉及大量中间节点的插入删除，双向链表往往比顺序表更合适；但如果主要是查询操作，顺序表则是更好的选择。