跳到主要内容数据结构实战：带头双向循环链表的实现与解析 | 极客日志C算法
数据结构实战：带头双向循环链表的实现与解析
详细讲解带头双向循环链表的数据结构原理与 C 语言实现。涵盖初始化、头尾插删、查找、销毁等核心接口代码，分析顺序表与链表差异，并包含移除元素、反转链表等经典算法题解法。重点阐述指针操作细节与边界处理，适合希望夯实底层数据结构基础的学习者参考。
游戏玩家1 浏览 数据结构实战：带头双向循环链表的实现与解析
一、双向链表概念与结构
双向链表是一种链式存储的数据结构，每个节点包含两个指针：一个指向前驱节点（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;
}
- 创建新节点
p，此时 p 自指。
p->next = h：新节点的后继指向头节点。p->prev = h->prev：新节点的前驱指向原尾节点。h->prev->next = p：原尾节点的后继指向新节点。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;
p->prev->next = h;
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;
p->next->prev = h;
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;
}
指定位置后插入
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;
}
指定位置删除
删除节点需修改前驱节点的 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. 完整代码展示
#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
#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;
}
#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;
}
- 维护新链表的头节点
h 和尾节点 pr。
- 遍历原链表，若当前节点值不等于
val，则将其拼接到新链表尾部。
- 遍历结束后，将新链表尾节点的
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;
}
- 每次循环将
s2 的 next 指向 s1，完成局部反转。
- 更新
s1 为 s2，s2 为 s3，继续向后处理。
- 循环结束后，
s1 指向原链表的尾节点，即新链表的头节点。
以上就是关于带头双向循环链表的详细讲解，涵盖了原理、实现细节、对比分析及经典算法题解法。希望这些内容能帮助你夯实底层数据结构基础。
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Gemini 图片去水印
基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
