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

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

一、双向链表概念与结构

双向链表是一种链式存储的数据结构，每个节点包含两个指针：一个指向前驱节点（prev），一个指向后继节点（next），同时包含数据域（data）存储数据。这种结构允许双向遍历（从头到尾或从尾到头），并支持更灵活的插入、删除操作，但相比单链表会增加一定的空间开销。

我们这里采用的是带头双向循环链表。它兼具'头节点''双向指针''循环结构'三大特性，是应用最广泛的双向链表类型。其结构稳定、边界处理简单，支持高效的插入、删除和双向遍历操作。

带头双向循环链表说明

带头链中的头节点，是不存储任何有效数据的，只用来站岗放哨，可称之为"哨兵位"。按照定义来说，严谨的定义：头节点是链表中第一个节点，但不存储有效数据（部分场景可存储链表长度等元信息），其核心价值是简化边界操作（如插入/删除首节点时无需特殊判断）。

双向链表结构定义

typedef int type;

typedef struct ListNode {
    type data;              // 数据域
    struct ListNode* prev;  // 前驱指针
    struct ListNode* next;  // 后继指针
} ListNode;

二、实现双向链表

1. 初始化

我们在双向链表中头节点是需要初始化的，数据域可以存任意的数据，前驱指针和后继指针都指向自己即可。

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;      // 指向自己
}

2. 创建节点辅助函数

为了实现尾插等操作，我们需要一个创建新节点的辅助函数。该函数不仅用于普通节点，也可用于初始化哨兵位。

ListNode* LTcreat(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;
}

3. 尾插操作

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

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

逻辑解析：

1. 创建新节点 p，此时 p 自指。
2. p->next = h：新节点的后继指向头节点。
3. p->prev = h->prev：新节点的前驱指向原尾节点。
4. h->prev->next = p：原尾节点的后继指向新节点。
5. h->prev = p：头节点的前驱更新为新节点（新尾节点）。

4. 头插操作

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

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

注意：在空链表状态下，h->next 和 h->prev 均指向 h，上述逻辑依然成立，无需特殊判断。

5. 判空与尾删

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

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;              // 头节点 prev 指向倒数第二个节点
    p->prev->next = h;              // 倒数第二个节点 next 指向头节点
    free(p);                        // 释放尾节点内存
}

关键点：双向循环链表尾删的核心是修复指针关系。若仅修改 h->prev 而不修改 p->prev->next，会导致链表出现断裂或错误的循环子链。

6. 头删操作

删除链表的第一个有效节点（即头节点后的第一个节点）。

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);                        // 释放内存
}

7. 销毁操作

销毁需遍历所有节点并逐个释放内存，顺序为先销毁除了头结点之外的所有节点，最后释放头结点空间。

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;                       // 置空指针，防止悬垂
}

8. 查找与插入

查找

利用临时指针遍历链表，找到目标值返回节点地址，否则返回 NULL。

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 之后插入新节点。

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

指定位置前插入

在指定节点 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;
    }
    ListNode* newnode = LTcreat(x);
    ListNode* pr = p->next;
    newnode->next = pr;
    newnode->prev = p;
    p->next = newnode;
    pr->prev = newnode;
}

指定位置删除

删除节点需修改前驱节点的 next 和后继节点的 prev，并释放被删节点内存。

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

9. 完整代码展示

为了方便测试，我们将接口整合到一个文件中。

list.h

#ifndef __LIST_H__
#define __LIST_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* LTcreat(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);

#endif

list.c

#include"list.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* LTcreat(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 = LTcreat(x);
    p->next = h;
    p->prev = h->prev;
    h->prev->next = p;
    h->prev = p;
}

void LTPushFront(ListNode* h, type x) {
    ListNode* p = LTcreat(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 = LTcreat(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 = LTcreat(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;
}

test.c

#include"list.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);
    print(h);

    LTInsert(p, 200);
    print(h);

    LTErase(p);
    print(h);

    LTDestroy(h);
}

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

三、顺序表与链表的分析

相同点

• 逻辑结构一致：均为线性表，数据元素之间呈一对一的顺序关系。
• 核心操作相同：都支持插入、删除、查找、遍历等基本线性表操作。
• 存储数据类型：均可存储相同类型的数据元素。

不同点（核心差异）

• 存储方式：顺序表是连续内存空间，链表是离散内存空间通过指针连接。
• 访问效率：顺序表支持随机访问（O(1)），链表只能顺序访问（O(n)）。
• 增删效率：顺序表中间插入删除需要移动大量元素（O(n)），链表只需修改指针（O(1)，已知位置）。
• 空间管理：顺序表需预先分配大小，可能浪费或不足；链表动态分配，按需使用。

关键结论

• 顺序表：适合频繁随机访问、数据量固定的场景（如存储学生信息表）。
• 链表：适合频繁插入删除、数据量动态变化的场景（如实现队列、栈）。

四、链表算法题

1. 移除链表元素

题目要求移除值为 val 的节点，并返回新的头结点。

思路：创建一个新链表，存储符合要求的节点（值不等于 val）。虽然未释放原链表空间，但在 OJ 解题中该方法较为简单直观。

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

解析：

1. 维护新链表的头节点 h 和尾节点 pr。
2. 遍历原链表，若当前节点值不等于 val，则将其拼接到新链表尾部。
3. 遍历结束后，将新链表尾节点的 next 置为 NULL，避免野指针风险。

2. 反转链表

题目要求反转单链表。

思路：迭代法。通过三个指针遍历链表，逐次反转节点指向。

• s1：指向已反转部分的头节点（初始为 NULL）。
• s2：指向当前待反转节点（初始为 head）。
• s3：临时保存 s2 的下一个节点（避免反转后断链）。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *s1 = NULL, *s2 = head, *s3 = NULL;
    if (s2) s3 = s2->next;
    while (s2) {
        s2->next = s1;
        s1 = s2;
        s2 = s3;
        if (s3) s3 = s3->next;
    }
    return s1;
}

解析：

1. 每次循环将 s2 的 next 指向 s1，完成局部反转。
2. 更新 s1 为 s2，s2 为 s3，继续向后处理。
3. 循环结束后，s1 指向原链表的尾节点，即新链表的头节点。

---

以上就是关于带头双向循环链表的详细讲解，涵盖了原理、实现细节、对比分析及经典算法题解法。希望这些内容能帮助你夯实底层数据结构基础。