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

一、双向链表概念与结构

双向链表概念

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

图示：不带头双向循环链表

双向链表不仅能找到当前节点的下一个节点，还可以找到当前节点的上一个节点，使用起来是很方便的。

因为刚刚讲解过的单链表为单向不带头不循环链表，目前还没有讲过带头形式的，所以本双链表为带头双向循环链表。

带头双向循环链表

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

对于上面头结点讲解：

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

双向链表结构

根据前文知识讲解，以及前面单向不带头不循环链表的知识，我们来实现下双向链表结构：

typedef int type;
typedef struct ListNode {
    type data; // 数据域
    struct ListNode* prev; // 前驱指针，指向前一个节点
    struct ListNode* next; // 后继指针，指向后一个节点
} ListNode;

二、实现双向链表

1. 双向链表的初始化

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

函数形式：

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

细讲：代码逐行解析

初始图示：

void test() {
    ListNode* h;
    LTInit(&h);
}
int main() {
    test();
}

2. 双向链表的尾插

双向链表尾插是指在链表的尾部（最后一个有效节点之后）插入新节点。对于带头节点的双向循环链表，尾插可直接通过头节点的 prev 指针定位尾节点，无需遍历链表，时间复杂度为O(1)。

void LTPushBack(ListNode* h, type x)

不过，该函数为实现尾插入，需要插入一个新节点，但传入的参数为 type，需要先将 type 类型转化为 ListNode* 类型，所以，应有下面函数:

创建节点

ListNode* LTcreat(type x)

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

讲解：

LTcreat 函数：创建新节点（含哨兵位初始化） 功能：创建一个新节点，初始化 data 为 x，并让 next 和 prev 指针自指（形成循环）。 用途：可用于初始化链表的哨兵位头节点（此时 x 通常为无意义值，如 -1）；也可用于创建普通有效节点（此时 x 为实际数据）。

LTPushBack 函数：尾插操作 核心逻辑：通过 LTcreat(x) 创建新节点 p，并插入到链表尾部（头节点 h 的 prev 位置）。 步骤拆解：

1. ListNode* p = LTcreat(x); → 创建新节点 p（p->next 和 p->prev 初始指向自身）。
2. p->next = h; → 新节点 p 的 next 指向头节点 h（保持循环）。
3. p->prev = h->prev; → 新节点 p 的 prev 指向原尾节点（h->prev 是原尾节点）。
4. h->prev->next = p; → 原尾节点的 next 指向新节点 p。
5. h->prev = p; → 头节点 h 的 prev 指向新节点 p（更新尾节点为 p）。

newNode->prev = h->prev; // 新节点 prev 指向原尾节点
newNode->next = h;       // 新节点 next 指向头节点
h->prev->next = newNode; // 原尾节点 next 指向新节点
h->prev = newNode;       // 头节点 prev 更新为新节点（新尾节点）

图示：

3. 双向链表的头插

头插是双向链表中最常用的操作之一，指将新节点插入到头节点之后、第一个有效节点之前的位置。适用于需频繁在头部添加数据的场景。

根据上面所说，我们可以知晓一点：插入到头节点之后、第一个有效节点之前的位置，所以实现上要考虑考虑：

void LTPushFront(ListNode* h, type x)

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

细讲一下：

向带头节点的双向循环链表头部插入新节点（头插）。 前提：链表已初始化（头节点 h 存在，且 h->next 和 h->prev 初始指向自身，即空链表状态）。

完整头插流程（以空链表插入第一个节点为例）

假设头节点 h 已通过 LTcreat(-1) 创建（-1 为哨兵位无效数据），插入第一个有效节点 x=10：

1. 创建新节点：ListNode* p = LTcreat(10); LTcreat 分配内存并初始化 p->data=10，p->next=p，p->prev=p。
2. 结果：链表变为 h <-> p（双向循环，p 为唯一有效节点）。

插入新节点：

p->next = h->next; // 步骤 1：p->next = h（因空链表 h->next = h）
p->prev = h;       // 步骤 2：p->prev = h（头节点为 p 的前驱）
h->next->prev = p; // 步骤 3：h->prev = p（原 h->next 是 h，故 h->prev 指向 p）
h->next = p;       // 步骤 4：h->next = p（头节点 next 指向 p，p 成为第一个有效节点）

图示：

4. 双向链表的尾删

双向链表的尾删（删除链表最后一个有效节点）是链表操作的高频场景，其核心是安全释放尾节点内存并修复前驱节点的指针关系。实现尾删之前，我们需要先实现一个判空的函数，如果链表为空则不能继续删除了：

尾删函数形式：

void LTPopBack(ListNode* h)

双向链表的判空

bool LTEmpty(ListNode* phead)

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

讲解: 空链表：头节点的 next 指针指向自身（phead->next == phead），此时链表无任何有效节点。非空链表：头节点的 next 指向第一个有效节点（phead->next != phead）。

接下来回归正题：

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

讲解： 步骤 1：判空——避免对空链表操作（核心安全检查！） LTEmpty 逻辑：return phead->next == phead（头节点的 next 指向自身，说明无有效节点）。作用：若链表为空（如 h <-> h），直接返回，避免后续 p->prev 访问空指针导致程序崩溃。

步骤 2：定位尾节点——无需遍历，O(1) 效率！ 双向循环链表特性：头节点的 prev 指针直接指向尾节点（无需从 h->next 开始遍历），时间复杂度O(1)（单向链表需 O(n)，这是双向链表的核心优势）。

步骤 3：修复指针——确保链表循环关系不中断 修复后链表结构：h <-> A <-> B <-> h（尾节点 C 已从逻辑上'脱离'链表）。关键对比：若仅修改 h->prev = p->prev 而不修改 p->prev->next，会导致B 的 next 仍指向 C，链表出现'断裂'（B <-> C <-> h <-> A <-> B），形成错误的循环子链。

步骤 4：释放内存——避免内存泄漏（必须！）

尾删图示：

5. 双向链表的头删

双向链表的头删指删除链表的第一个有效节点（即头节点后的第一个节点）。带头节点的链表可避免对空链表的特殊处理，实现更简洁。

根据前文所讲，我们可知其实现图示：

函数形式：

void LTPopFront(ListNode* h);

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

讲解： 核心代码逐行解析 1. 判空处理（避免操作无效链表） h == NULL：检查头节点指针是否为空（链表未初始化）。 h->next == h：检查链表是否为空（头节点的 next 指向自身，说明无有效节点）。处理逻辑：若满足任一条件，打印错误信息并退出函数，避免后续非法操作。

2. 记录待删除节点 头节点 h 的 next 指针指向链表的第一个有效节点，用 p 临时保存该节点地址，便于后续释放内存。

3. 更新链表指针关系（断链与重连） 步骤 1：头节点 h 不再指向 p，而是直接指向 p 的下一个节点（p->next），完成'前向断链'。 步骤 2：p 的下一个节点（p->next）的 prev 指针从指向 p 改为指向头节点 h，完成'反向断链'。 效果：通过双向指针的更新，p 节点从链表中完全脱离。

4. 释放内存（避免内存泄漏） 手动释放 p 指向的节点内存（C 语言需显式管理内存，否则会导致内存泄漏）。

6. 双向链表的销毁

双向链表的销毁需遍历所有节点并逐个释放内存，避免内存泄漏，顺序为：先销毁除了头结点（哨兵位）之外的所有节点，在最后释放头结点空间。

函数形式：

void LTDestroy(ListNode* h);

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

讲解：按道理来说是要传入二级指针的，但是前面其它接口都用的一级，这里和初始化部分统一比较好点，我们可以在测试文件中最后销毁完手动将头节点置为空。

7. 双向链表查找

双向链表的查找操作与单链表类似，但可利用创建一个暂时的指针实现遍历。

函数形式：

ListNode* LTFind(ListNode* h, type x);

实现：

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

细讲：通过遍历来实现，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空。

8. 双向链表在指定位置插入

双向链表在指定位置插入分为双向链表在指定位置之前插入与双向链表在指定位置之后插入：

双向链表在指定位置之后插入

函数形式：

void LTInsert(ListNode* pos, type x)

实现：

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 之后插入新节点，核心逻辑是通过调整指针关系实现无缝插入。 1. 参数与前置检查 作用：pos 是插入位置的基准节点（新节点将插入其后），x 是新节点的数据。风险控制：assert(pos) 防止用户传入 nullptr 导致后续操作崩溃。 2. 保存后继节点 必要性：插入新节点后，pos 的 next 指针会指向新节点，若不提前保存原后继 pos->next，将导致原链表后半部分丢失。 核心：调整指针关系（4 步插入法） 在指定位置之后的插入操作其实也没有很难，还是先断言，后续就是先申请一个新节点，跟头插尾插相似的方式。

双向链表在指定位置之前插入

函数形式：

void LTInsertfront(ListNode* pos, type x);

实现：

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

细讲：核心功能是在指定节点 pos 的前驱位置插入新节点（即'在 pos 前面插入'）。

9. 双向链表指定位置删除

删除节点需修改前驱节点的 next 和后继节点的 prev，并释放被删节点内存。关键是处理边界情况（如 pos 是头/尾节点）。

函数形式：

void LTErase(ListNode* pos)

实现：

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

细讲： 步骤：通过 pos->prev 获取前驱节点 p；调整指针：p->next = pos->next（切断 p 与 pos 的连接，指向 pos 的后继）；调整后继节点的前驱指针：pos->next->prev = p（切断后继与 pos 的连接，指向 p）；释放 pos 节点内存，并置空局部指针 pos。 前置断言 assert(pos) 作用：确保 pos 不为空指针，避免后续 pos->prev 等操作引发崩溃。

10. 总代码展示：(加入了测试代码)

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* 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);

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

main.cpp

#include "1.h"

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

int main() {
    test();
}

三、顺序表与链表的分析

本图列举了顺序表与链表之间的相同点与不同点：

一、相同点

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

二、不同点（核心差异）

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

四、链表算法题

一、移除链表元素

移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

由题意可知，本题要求移除值为 val 的节点，并要求返回新的头结点：

1. 链表的解法可以通过遍历整个链表，用一个节点存储前一个节点，在发现值为 val 时候改变 next 区域的指向解答。
2. 我们也可以选择创建一个新链表，存储符合要求的节点，虽然没有释放原链表空间，但做 OJ 题不释放也没什么问题的，该方法较为简单，本次解题选择此方法：

解题代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val) {
    Node *h = NULL, *pr = NULL;
    Node *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：新链表的头节点，初始为 NULL（表示新链表为空）。 pr：新链表的尾节点指针，用于拼接有效节点（值不等于 val 的节点）。 p：遍历指针，从原链表头节点 head 开始，依次访问每个节点。

2. 遍历原链表（while (p)） 循环条件 p 等价于 p != NULL，即遍历至原链表末尾时停止。 情况 1：当前节点 p 的值不等于 val（需保留） 首次保留节点（h == NULL）：新链表为空，因此 h（头节点）和 pr（尾节点）都指向当前节点 p。 非首次保留节点（h != NULL）：通过 pr->next = p 将当前节点 p 拼接到新链表尾部，然后 pr = p 更新尾节点指针。 情况 2：当前节点 p 的值等于 val（需删除） 不执行任何操作（不拼接至新链表），直接通过 p = p->next 跳过当前节点。

3. 处理新链表尾节点（if (pr) pr->next = NULL） 遍历结束后，pr 指向新链表的最后一个有效节点。若新链表非空（pr != NULL），需将其 next 置为 NULL，避免原链表中后续节点（已删除节点）的指针残留，导致野指针风险。

4. 返回新链表头节点 h 指向新链表的第一个有效节点，若原链表所有节点都被删除（如 head = [2,2,2], val=2），则 h 保持 NULL，返回空链表。

二、反转链表

反转链表

206. 反转链表 - 力扣（LeetCode）

解题思路：

反转题中给出的链表，如果简单来想，我们可以创建一个新链表一个一个节点的复制，但是题中的是单链表，不可找到前驱节点的，如果用上面思路，那会相当麻烦了。正确思路：通过三个指针来实现：迭代法（推荐：时间 O(n)，空间 O(1)）

核心思路：通过3 个指针遍历链表，逐次反转节点指向：

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

简单来做，我将其命名为 s1, s2, s3 了。

基本结构是这样的，接下来我将结合代码来讲解:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode node;
struct ListNode* reverseList(struct ListNode* head) {
    node *s1 = NULL;
    node *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;
}

讲解：

图示：

根据上图：我们可知代码 if (s3) { s3 = s3->next; } 的原因了：

while (s2) {  // 循环条件：当前待反转节点 s2 不为 NULL（遍历完所有节点后终止）
    // 步骤 1：反转当前节点 s2 的指向（指向已反转部分的头节点 s1）
    s2->next = s1;
    // 步骤 2：s1 后移到 s2（已反转部分的长度 +1，s1 成为新的'已反转头节点'）
    s1 = s2;
    // 步骤 3：s2 后移到 s3（继续处理下一个待反转节点）
    s2 = s3;
    // 步骤 4：若 s3 不为空，s3 后移到下一个节点（为下次循环做准备）
    if (s3) {
        s3 = s3->next;
    }
}
return s1;  // 循环结束后，s1 指向原链表的尾节点（即新链表的头节点）