数据结构实战：带头双向循环链表详解与实现

这里要注意，传入的是二级指针，因为我们需要修改外部传入的头节点指针本身。初始化后，链表状态就是 h <-> h。

辅助函数：创建节点

在插入操作中，我们需要频繁创建新节点。创建一个独立的辅助函数能让主逻辑更清晰。

ListNode* LTCreate(type x) {
    ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
    if (ph == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    ph->data = x;
    ph->next = ph;  // 初始自指
    ph->prev = ph;
    return ph;
}

尾插与头插

对于带头双向循环链表，尾插可以直接通过头节点的 prev 指针定位到尾部，无需遍历，时间复杂度为 O(1)。

尾插 (LTPushBack)

void LTPushBack(ListNode* h, type x) {
    ListNode* p = LTCreate(x);  // 创建新节点
    p->next = h;                // 新节点 next 指向头节点
    p->prev = h->prev;          // 新节点 prev 指向原尾节点
    h->prev->next = p;          // 原尾节点 next 指向新节点
    h->prev = p;                // 头节点 prev 更新为新节点
}

头插 (LTPushFront)

头插是在头节点之后、第一个有效节点之前插入。

void LTPushFront(ListNode* h, type x) {
    ListNode* p = LTCreate(x);
    p->next = h->next;  // 新节点 next 指向原第一个节点
    p->prev = h;        // 新节点 prev 指向头节点
    h->next->prev = p;  // 原第一个节点 prev 指向新节点
    h->next = p;        // 头节点 next 指向新节点
}

删除操作

删除前必须先判空，避免对空链表进行操作导致崩溃。

判空

bool LTEmpty(ListNode* phead) {
    assert(phead);
    return phead->next == phead; // 头节点 next 指向自身即为空
}

尾删 (LTPopBack)

由于是循环链表，尾节点即 h->prev。删除时需修复前驱节点的指针。

void LTPopBack(ListNode* h) {
    if (LTEmpty(h)) return;
    
    ListNode* p = h->prev;       // 待删除的尾节点
    h->prev = p->prev;           // 头节点 prev 指向新的尾节点
    p->prev->next = h;           // 新尾节点 next 指向头节点
    free(p);                     // 释放内存
}

头删 (LTPopFront)

删除头节点后的第一个有效节点。

void LTPopFront(ListNode* h) {
    if (LTEmpty(h)) {
        printf("链表为空，无法头删\n");
        return;
    }
    ListNode* p = h->next;       // 待删除的第一个节点
    h->next = p->next;           // 头节点 next 指向第二个节点
    p->next->prev = h;           // 第二个节点 prev 指向头节点
    free(p);                     // 释放内存
}

销毁

销毁需要遍历所有节点并逐个释放，最后释放头节点。

void LTDestroy(ListNode* h) {
    if (LTEmpty(h)) {
        free(h);
        return;
    }
    ListNode* p = h->next;
    while (p != h) {
        ListNode* pr = p;
        p = p->next;
        free(pr);
    }
    free(h);
    h = NULL; // 置空防止悬垂指针
}

3. 进阶操作

查找

利用遍历指针寻找目标值。

ListNode* LTFind(ListNode* h, type x) {
    if (LTEmpty(h)) return NULL;
    ListNode* p = h->next;
    while (p != h) {
        if (p->data == x) return p;
        p = p->next;
    }
    return NULL;
}

指定位置插入

分为在节点 pos 之后插入和在 pos 之前插入。

在 pos 之后插入

void LTInsert(ListNode* pos, type x) {
    assert(pos);
    ListNode* p = pos->next;
    ListNode* newnode = LTCreate(x);
    pos->next = newnode;
    newnode->prev = pos;
    newnode->next = p;
    p->prev = newnode;
}

在 pos 之前插入

需要先找到 pos 的前驱节点。

void LTInsertFront(ListNode* h, ListNode* pos, type x) {
    if (LTEmpty(h)) return;
    ListNode* p = h;
    while (p->next != h) {
        if (p->next == pos) break;
        p = p->next;
    }
    if (p->next == h) return; // 未找到 pos
    
    ListNode* newnode = LTCreate(x);
    ListNode* pr = p->next;
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

指定位置删除

直接断开前后连接并释放。

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

4. 顺序表与链表对比

结论：顺序表适合频繁随机访问、数据量固定的场景；链表适合频繁插入删除、数据量动态变化的场景。

5. 算法题实战

移除链表元素

题目：移除链表中值为 val 的所有节点。

思路：遍历链表，构建一个新链表只保留不等于 val 的节点，或者原地修改指针。这里演示构建新链表的方法，逻辑更直观。

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode *h = NULL, *pr = NULL;
    struct ListNode *p = head;
    while (p) {
        if (p->val != val) {
            if (h == NULL) {
                h = p;
                pr = p;
            } else {
                pr->next = p;
                pr = p;
            }
        }
        p = p->next;
    }
    if (pr) pr->next = NULL; // 断开旧链接
    return h;
}

反转链表

题目：反转单链表。

思路：迭代法，使用三个指针 prev, curr, next 逐次反转指向。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *s1 = NULL; // 已反转部分的头
    struct ListNode *s2 = head; // 当前节点
    struct ListNode *s3 = NULL; // 暂存下一个节点
    
    while (s2) {
        s3 = s2->next;   // 保存后续
        s2->next = s1;   // 反转指向
        s1 = s2;         // 移动已反转头
        s2 = s3;         // 移动当前指针
    }
    return s1;
}

6. 完整代码参考

为了方便测试，将上述功能整合到以下文件中。

1.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int type;
typedef struct ListNode {
    type data;
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

void LTInit(ListNode** h);
void LTPushBack(ListNode* h, type x);
ListNode* LTCreate(type x);
void LTPushFront(ListNode* h, type x);
void LTPopBack(ListNode* h);
void LTPopFront(ListNode* h);
void LTDestroy(ListNode* h);
void print(ListNode* h);
ListNode* LTFind(ListNode* h, type x);
void LTInsert(ListNode* pos, type x);
void LTInsertFront(ListNode* h, ListNode* pos, type x);
void LTErase(ListNode* pos);

1.cpp

#include"1.h"

void LTInit(ListNode** h) {
    ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
    if (ph == NULL) { perror("malloc fail!"); exit(1); }
    *h = ph;
    (*h)->data = -1;
    (*h)->next = *h;
    (*h)->prev = *h;
}

ListNode* LTCreate(type x) {
    ListNode* ph = (ListNode*)malloc(sizeof(ListNode));
    if (ph == NULL) { perror("malloc fail!"); exit(1); }
    ph->data = x;
    ph->next = ph;
    ph->prev = ph;
    return ph;
}

void LTPushBack(ListNode* h, type x) {
    ListNode* p = LTCreate(x);
    p->next = h;
    p->prev = h->prev;
    h->prev->next = p;
    h->prev = p;
}

void LTPushFront(ListNode* h, type x) {
    ListNode* p = LTCreate(x);
    p->next = h->next;
    p->prev = h;
    h->next->prev = p;
    h->next = p;
}

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

void LTPopBack(ListNode* h) {
    if (LTEmpty(h)) return;
    ListNode* p = h->prev;
    h->prev = p->prev;
    p->prev->next = h;
    free(p);
}

void LTPopFront(ListNode* h) {
    if (LTEmpty(h)) { printf("链表为空，无法头删\n"); return; }
    ListNode* p = h->next;
    h->next = p->next;
    p->next->prev = h;
    free(p);
}

void LTDestroy(ListNode* h) {
    if (LTEmpty(h)) { free(h); return; }
    ListNode* p = h->next;
    while (p != h) {
        ListNode* pr = p;
        p = p->next;
        free(pr);
    }
    free(h);
    h = NULL;
}

void print(ListNode* h) {
    if (LTEmpty(h)) return;
    ListNode* p = h->next;
    while (p != h) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

ListNode* LTFind(ListNode* h, type x) {
    if (LTEmpty(h)) return NULL;
    ListNode* p = h->next;
    while (p != h) {
        if (p->data == x) return p;
        p = p->next;
    }
    return NULL;
}

void LTInsert(ListNode* pos, type x) {
    assert(pos);
    ListNode* p = pos->next;
    ListNode* newnode = LTCreate(x);
    pos->next = newnode;
    newnode->prev = pos;
    newnode->next = p;
    p->prev = newnode;
}

void LTInsertFront(ListNode* h, ListNode* pos, type x) {
    if (LTEmpty(h)) return;
    ListNode* p = h;
    while (p->next != h) {
        if (p->next == pos) break;
        p = p->next;
    }
    if (p->next == h) return;
    ListNode* newnode = LTCreate(x);
    ListNode* pr = p->next;
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

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

main.cpp

#include"1.h"

void test() {
    ListNode* h;
    LTInit(&h);
    LTPushBack(h, 10);
    LTPushBack(h, 15);
    LTPushBack(h, 111);
    print(h);
    
    LTPushFront(h, 2);
    LTPushFront(h, 12);
    print(h);
    
    LTPopBack(h);
    print(h);
    LTPopFront(h);
    print(h);
    
    ListNode* p = LTFind(h, 10);
    LTInsert(p, 100);
    LTInsert(p, 200);
    LTErase(p);
    print(h);
    
    LTDestroy(h);
}

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

运行结果验证了各接口逻辑正确，指针关系维护无误。