跳到主要内容数据结构实战:带头双向循环链表的实现与解析 | 极客日志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