数据结构实战：C 语言循环双向链表实现详解

核心实现细节

1. 申请新节点

这是最基础的单元。注意，新节点创建时，其 next 和 prev 先指向自己，形成一个独立的微型环，后续再将其接入主链表。

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

2. 初始化与销毁

初始化只需调用买节点函数创建一个哨兵位。销毁时需要遍历链表，逐个释放非头结点，最后释放头结点本身。

// 初始化
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;
}

3. 插入操作（头插与尾插）

双向链表的插入涉及四个指针的修改。顺序至关重要，一旦断链就无法找回丢失的节点。

尾插逻辑： 新节点夹在 tail 和 head 之间。先连新节点的后继（head），再连前驱（tail），最后更新 head 和 tail 的指针。

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;
    phead->prev = newnode;
}

头插逻辑： 类似尾插，只是位置在 head 和 head->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;
}

4. 删除操作（头删与尾删）

删除相对简单，但要注意释放内存后不要立即使用指针，防止野指针。

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

5. 通用插入与删除

在指定位置 pos 之后插入，或删除 pos 节点。这里假设 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;
}

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

6. 辅助功能

判空通过检查头结点的 next 是否指向自己来判断。打印则从 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;
}

顺序表与链表对比

掌握指针操作的先后顺序是双向链表的核心难点。在实际开发中，务必确保在断开旧连接前，先保存好必要的指针引用，否则会导致内存泄漏或程序崩溃。