【数据结构】链表详解：单链表、双向链表与循环链表

🚀 前言：链表是线性表的一种链式存储结构，逻辑上相邻的元素在物理内存上不必相邻。它通过指针域将各个节点连接起来，是数据结构中最基础也最核心的知识点。本文基于课堂笔记与代码实践，全面梳理单链表、双向链表以及循环链表的核心操作与算法实现。

一、 单链表 (Singly Linked List)

1. 概念与结构定义

单链表是链式存储的最基础形式，每个节点包含数据域（存放数据）和指针域（指向下一个节点）。通常我们会在链表的最前面附加一个头节点（不存放有效数据，便于统一操作）。

结构体定义：

typedef struct _LinkList {
int data; // 结点的数据域
struct _LinkList* next; // 结点的指针域
} LinkNode, LinkList;

2. 核心操作实现

🔹 初始化

生成一个新节点作为头结点，将其指针域置空。

bool InitList(LinkList*& L) {
L = new LinkNode;
if (!L) return false;
L->next = NULL;
L->data = -1; // 头结点数据域不作要求
return true;
}

 插入元素

前插法（头插法）：始终将新节点插入到头结点之后。特点：输入顺序与链表实际顺序相反。

bool ListInsert_front(LinkList*& L, LinkNode* node) {
if(!L || !node) return false;
node->next = L->next;
L->next = node;
return true;
}

尾插法（后插法）：遍历找到尾节点，将新节点接在其后。特点：保持输入顺序。

bool ListInsert_back(LinkList*& L, LinkNode* node) {
if(!L || !node) return false;
LinkNode* p = L;
while(p->next) p = p->next;
p->next = node;
node->next = NULL;
return true;
}

任意位置插入（在第 i 个位置插入 e）：

bool LinkInsert(LinkList*& L, int i, int& e) {
if (!L || i < 1) return false;
LinkNode *p = L, *s;
int j = 0;
// 找第 i-1 个节点
while (p && j < i – 1) {
p = p->next;
j++;
}
if (!p) return false; // 位置不合法
s = new LinkNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}

查找、删除与销毁

• 按位置查找：遍历到第 i 个节点并取值。

思路：从头结点的下一个节点（第1个数据节点）开始，利用计数器 index 顺链表向后扫描，直到 index == i。需要注意判断 i 是否合法以及链表是否为空。

// 按位置查找 单链表的取值
// L: 链表头指针，i: 要查找的位置，e: 用于返回查找到的数据
bool Link_GetElem(LinkList* &L, int i, int &e)
{
// 判断链表是否为空，或者 i 是否合法（i 从 1 开始）
if (!L || i < 1 || !L->next) return false;

int index = 1; // 计数器
LinkList* p = L->next; // p 指向第一个数据节点

// 顺链表向后扫描，直到找到第 i 个结点
while (p && index < i)
{
p = p->next; // 指针后移，访问下一个结点
index++; // 计数器加1
}

// 判断是否找到第 i 个结点（p为空说明i超出了表长）
if (!p || index > i) return false;

e = p->data; // 取出第 i 个结点的数据域
return true;
}

• 按值查找：遍历链表，比对数据域。

思路：从头遍历链表，逐个比对节点的数据域 data，找到则返回其位置（并打印），遍历完没找到则返回 false。

// 按值查找
// L: 链表头指针，e: 要查找的值，i: 用于返回查找到的位置索引
bool Link_LocateElem(LinkList* L, int e, int& i)
{
// 如果链表为空
if (!L || !L->next)
{
i = 0;
return false;
}

LinkNode* p = L->next;
i = 1; // 从第一个数据节点开始找

// 只要 p 不为空，且当前节点的数据不等于 e，就继续往后找
while (p && p->data != e)
{
p = p->next;
i++;
}

// 如果 p 为空，说明遍历完了都没找到
if (!p)
{
i = 0;
return false;
}

cout << "第" << i << "个结点的数据为：" << p->data << endl;
return true;
}

• 按位置删除：找到第 i-1 个节点，修改其 next 指针跳过目标节点，并 delete 释放内存。

思路：要删除第 i 个节点，需要先找到第 i-1 个节点（前驱节点），然后修改前驱节点的 next 指针跳过目标节点，最后 delete 目标节点。这里 p 初始指向头结点，是为了防止删除第一个节点时丢失头结点。

// 按位置删除
bool LinkDelete(LinkList*& L, int i)
{
if (!L || i < 1) return false; // 位置从 1 开始，i<1 不合法

LinkList* p = L; // p 指向头结点，防止删除第一个结点时头结点丢失
int index = 0; // 记录当前 p 是第几个节点（头结点为0）

// 查找第 i-1 个节点
while ((p->next) && (index < i – 1))
{
p = p->next;
index++;
}

// 当 i>n 或 i<1 时，删除失败，位置不合法
// 如果 p->next 为空，说明 i 超出了表长；如果 index < i-1，说明 i 小于 1
if (!p->next || (index < i – 1))
{
return false;
}

LinkList* q = p->next; // q 指向第 i 个节点（即要被删除的节点）
p->next = q->next; // 将 p 的 next 指针指向 q 的下一个节点，跳过 q
delete q; // 释放 q 的内存空间

return true;
}

• 销毁链表：从头节点开始，逐个释放所有节点空间，最后将头指针置为 NULL

思路：销毁链表需要将链表中所有节点（包括头结点）的内存都释放掉。使用临时指针 p 逐个遍历并 delete，最后将头指针置空，防止产生野指针。

bool DestroyList(LinkList*& L)
{
if (!L) return false;
LinkNode* p = L; // 定义临时节点 p 指向头结点
while (p)
{
L = L->next; // 头指针指向下一个节点（利用 L 保存下一个节点的位置）
delete p; // 释放当前节点内存空间
p = L; // p 指向下一个节点
}
// 此时 p 为 NULL，L 也为 NULL，函数结束
return true;
}

bool DestroyList(LinkList*& L)
{
if (!L) return false;

LinkNode* p = L;
while (p != NULL)
{
LinkNode* temp = p->next; // 先用 temp 保存下一个节点的地址
delete p; // 然后释放当前节点
p = temp; // p 走到下一个节点
}

L = NULL; // 全部释放完后，将头指针置空，防止野指针
return true;
}

二、 双向链表 (Doubly Linked List)

1. 概念与结构定义

双向链表的每个节点除了有指向后继的 next 指针，还多了一个指向前驱的 prev 指针。这使得双向链表可以“从前往后”或“从后往前”遍历，但也增加了在插入和删除时维护两个指针的复杂度。

结构体定义：

typedef struct _DoubleLinkList {
int data;
struct _DoubleLinkList* next;
struct _DoubleLinkList* prev;
} DbLinkNode, DbLinkList;

2. 核心操作实现

🔹 插入元素

• 双向链表的前插/后插：注意修改指针的顺序，一定要先连新节点的两头，再断开原链表，防止丢失后继节点。

1. 前插法（头插法）

逻辑：始终将新节点插入到头结点 L 之后。需要注意判断链表是否为空，如果为空，则只需处理头结点与新节点的关系。

// 前插法：将 node 插入到头结点 L 之后
bool ListInsert_front(DbLinkList *& L, DbLinkNode* node)
{
if (!L || !node) return false;

// 核心1：如果链表非空，原第一个节点（L->next）的 prev 必须指向新节点
if (L->next)
{
L->next->prev = node; // ① 原首节点的 prev 连向新节点
}

// 核心2：连接新节点的两头
node->next = L->next; // ② 新节点的 next 连向原首节点（或 NULL）
node->prev = L; // ③ 新节点的 prev 连向头节点

// 核心3：最后断开原头结点的连接，指向新节点
L->next = node; // ④ 头结点的 next 连向新节点
return true;
}

避坑：如果第 ④ 步先执行 L->next = node;，那么原来的第一个节点就找不到了，第 ① 步操作就会报错。所以必须先连新节点。

2. 后插法（尾插法）

逻辑：遍历找到链表的最后一个节点，然后将新节点接到它的后面。这是您文件中提供的实现。

// 后插法：将 node 插入到链表尾部
bool ListInsert_back(DbLinkList*& L, DbLinkNode* node)
{
if (!L || !node) return false;

DbLinkList* last = L;
// 1. 寻找尾结点（last->next == NULL）
while (last->next)
{
last = last->next;
}

// 2. 将新节点连接到尾节点之后
node->next = NULL; // ① 新节点作为新的尾部，next 置空
last->next = node; // ② 原尾节点的 next 连向新节点
node->prev = last; // ③ 新节点的 prev 连向原尾节点
return true;
}

• 双向链表任意位置插入：

bool DbLink_Insert(DbLinkList*& L, int i, int e) {
if (L == NULL || i < 1) return false;
DbLinkNode* p = L->next;
int j = 1;
while (p != NULL && j < i) { p = p->next; j++; }
if (p == NULL) return false; // i 超过表长

DbLinkNode* s = new DbLinkNode;
s->data = e;
s->prev = p->prev; // ① 新节点前驱指向原前驱
s->next = p; // ② 新节点后继指向当前节点
p->prev->next = s; // ③ 原前驱的后继指向新节点
p->prev = s; // ④ 当前节点的前驱指向新节点
return true;
}

打印与逆向打印

双向链表的一大特色是可以轻松实现逆向打印

void DbLink_Print(DbLinkList* L) {
// 正向打印到最后一个节点
DbLinkNode* P = L->next;
while (P != NULL) {
cout << P->data << "\\t";
if (P->next == NULL) break; // P 停在尾结点
P = P->next;
}
cout << endl << "逆向打印" << endl;

// 从尾节点倒推，碰到头结点停止
while (P != L) {
cout << P->data << "\\t";
P = P->prev;
}
}

 删除节点

删除第 i 个节点 q 时，一定不能忘记判断 q->next 是否为空。

DbLinkNode* q = p->next; // 第 i 个结点
p->next = q->next; // 前驱跨过 q
if (q->next != NULL) // 如果后面还有结点，才需要改它的 prev
q->next->prev = p;
delete q; // 释放内存

三、 循环链表 (Circular Linked List)

1. 概念

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个节点的指针域指向头结点，整个链表形成一个环。从任意一个节点出发，都能找到链表中的其他所有节点。

结构体定义与单链表一致，重点在于初始化：

bool InitList(LinkList*& L) {
L = new LinkNode;
if (!L) return false;
L->next = L; // 注意：指针域指向自身，形成空循环链表
L->data = -1;
return true;
}

2. 典型应用：约瑟夫环 (Josephus Problem)

问题描述：N个人围成一圈，从第一个人开始报数，报到 M 的人出列，下一个人继续从 1 开始报数，直到所有人出列。
算法实现（摘录核心逻辑）：

bool Joseph(LinkList*& L, int interval) {
if (L == NULL || L->next == NULL || L->next == L) return false; // 空表
if (interval < 1) return false;

LinkList* p = L; // p->next 是报数第1个人
int times = 0, num = 0;

while (L->next != L) { // 环里还有数据结点
// 前进 interval-1 步，中途需要跳过头结点（它不计入报数）
for (int k = 1; k < interval; k++) {
p = p->next;
if (p->next == L) p = p->next;
}
LinkList* q = p->next; // 出列者
num = q->data;
times++;
cout << "第" << times << "个出列的编号：" << num << endl;

p->next = q->next; // 摘链
delete q; // 释放
PrintList(L); // 打印当前剩余的人
}
cout << "最后一个编号" << num << endl;
return true;
}

总结与对比

💡 避坑指南：