带头双向循环链表的 C 语言实现详解

关键实现细节

1. 初始化与辅助函数

初始化时创建一个哨兵位头结点，它的 next 和 prev 都指向自己。这样无论链表是否为空，phead 始终有效。

LTNode* ListInit() {
    // 哨兵位头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    if (phead == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

// 创建新节点的辅助函数
LTNode* BuyListNode(LDataType x) {
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->val = x;
    newnode->prev = newnode->next = NULL;
    return newnode;
}

2. 插入操作

尾插时，先找到当前尾节点（即 phead->prev）。新节点要插在尾节点和头节点之间。连接顺序要注意：先连前驱，再连后继，最后更新头结点的 prev。

void ListPushBack(LTNode* phead, LDataType x) {
    assert(phead);
    LTNode* tail = phead->prev;
    LTNode* newnode = BuyListNode(x);
    
    newnode->next = phead;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;
}

头插逻辑类似，只是插在头结点和原第一个数据节点之间。同样需要先保存原后继节点地址，防止断链。

void ListPushFront(LTNode* phead, LDataType x) {
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* pheadNext = phead->next;
    
    phead->next = newnode;
    newnode->prev = phead;
    pheadNext->prev = newnode;
    newnode->next = pheadNext;
}

3. 删除操作

尾删时，通过 phead->prev 定位尾节点，再通过尾节点的 prev 找到它的前驱。断开链接后释放尾节点内存。

void ListPopBack(LTNode* phead) {
    assert(phead);
    assert(phead->next != phead); // 非空检查
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    
    tailPrev->next = phead;
    phead->prev = tailPrev;
    free(tail);
}

头删同理，直接操作 phead->next。注意如果链表只有一个数据节点，删除后应恢复为空表状态（即 next 和 prev 均指向 phead）。

void ListPopFront(LTNode* phead) {
    assert(phead);
    assert(phead->next != phead);
    LTNode* head = phead->next;
    LTNode* next = head->next;
    
    next->prev = phead;
    phead->next = next;
    free(head);
}

指定位置插入/删除是双向链表的精髓。插入时，利用 pos->prev 找到前驱，修改四个指针即可。删除时，直接修改前后节点的指针，跳过待删节点。

void ListInsert(LTNode* pos, LDataType x) {
    assert(pos != NULL);
    LTNode* newnode = BuyListNode(x);
    LTNode* posPrev = pos->prev;
    
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
}

void ListErase(LTNode* pos) {
    assert(pos != NULL);
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

4. 查找、打印与销毁

查找从头结点的后继开始遍历，直到回到头结点为止。打印时同样遵循此循环条件。销毁时需要逐个释放节点，并保留下一个节点的地址以防野指针。

LTNode* ListFind(LTNode* phead, LDataType x) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        if (cur->val == x) {
            return cur;
        } else {
            cur = cur->next;
        }
    }
    return NULL;
}

void ListPrint(LTNode* phead) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

void ListDestroy(LTNode* phead) {
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead) {
        LTNode* tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    cur = NULL;
    phead = NULL;
}

使用示例

在实际测试中，我们通常会组合调用上述接口来验证功能。以下是一个简单的测试流程，涵盖了增删查改的基本场景。

#define _CRT_SECURE_NO_WARNINGS
#include "List.h"

void ListTest1() {
    LTNode* plist = ListInit();
    
    // 尾插测试
    ListPushBack(plist, 1);
    ListPushBack(plist, 2);
    ListPushBack(plist, 3);
    ListPrint(plist);
    
    // 尾删测试
    ListPopBack(plist);
    ListPopBack(plist);
    ListPrint(plist);
    
    // 头插测试
    ListPushFront(plist, 6);
    ListPushFront(plist, 7);
    ListPrint(plist);
    
    // 查找与插入
    LTNode* pos = ListFind(plist, 2);
    if (NULL != pos) {
        printf("找到了\n");
        ListInsert(pos, 10);
        ListPrint(plist);
    }
    
    // 删除
    pos = ListFind(plist, 1);
    ListErase(pos);
    ListPrint(plist);
    
    ListDestroy(plist);
    plist = NULL;
}

int main() {
    ListTest1();
    return 0;
}

总结

带头双向循环链表通过哨兵位简化了边界处理，相比单链表支持双向遍历，灵活性更高。代码实现中需注意指针修改的顺序，避免断链。最后对比顺序表，链表在插入删除上效率更高，但随机访问性能较差，实际开发中需根据场景选择。