数据结构 | 单链表
一、为什么要学习单链表？
在学习顺序表时，我们发现它存在一些难以避免的缺陷：
- 必须占用一整块连续的内存空间
- 头部、中间插入或删除需要大量移动元素，效率很低
- 动态扩容需要开辟新空间并复制数据，代价较高
为了解决这些问题，我们引入了链表，而单链表是最基础、最核心的链表结构。
二、单链表的特点
- 逻辑相邻，物理不一定相邻
- 不要求连续的内存空间，内存利用率更高
- 完美避开顺序表插入删除效率低的问题
- 但失去了随机存取的能力，不能直接按下标访问元素
【顺序表 物理存储图】
【单链表 物理存储图】
三、单链表的结构
单链表由一个个节点组成，每个节点包含两部分：
1.数据域：存放当前节点的有效数据
2.指针域：存放下一个节点的地址，用来串联整个链表
// 节点结构体 struct Node { int data; // 数据域 Node* next; // 指针域 }; // 带头结点的单链表，头结点不存数据，只做辅助四、带头结点 vs 不带头结点
本篇博客所有代码全部使用带头结点的单链表实现，头结点也叫哨兵节点、辅助节点，不存储有效数据。
1. 带头结点（哨兵/辅助节点）
- 存在一个不存储数据的辅助节点
- 作用：统一边界条件，简化头插、头删、判空操作
- 判空条件：head->next == NULL
- 头插、头删时不需要修改头指针
2. 不带头结点
- 头指针直接指向第一个数据节点
- 空表条件：head == NULL
- 头插、头删都需要修改头指针，逻辑复杂，容易出错
辅助节点（哨兵）：帮助我们在空表判断、第一个元素插入、删除时，统一处理边界条件，不用写特殊逻辑。
【带头结点的 单链表】
【不带头结点的 单链表】
五、两个常用技巧
技巧1：需要找前驱 → 从辅助节点开始遍历
适用场景：插入、删除（必须找到前驱节点才能修改指针）
// 需要前驱：插入、删除 for (Node* p = head; p->next != nullptr; p = p->next);技巧2：不需要前驱 → 从第一个有效节点开始遍历
适用场景：打印、查找、求长度（只访问数据，不修改结构）
// 不需要前驱：打印、查找 for (Node* p = head->next; p != nullptr; p = p->next);六、重点函数讲解
1. 初始化函数
思路：带头结点链表，只需要将头结点的 next 置空即可，表示空链表。
// 初始化带头结点的链表 void InitList(Node*& head) { head = new Node; head->next = nullptr; }2. 按位置插入（头插、尾插、中间插）
思路：
1. 检查位置合法性
2. 从头结点出发，找到待插入位置的前驱节点
3. 新建节点，执行插入
4. 所有位置逻辑完全一样，无特殊处理
// pos=0 头插 pos=长度 尾插 中间位置通用 bool InsertPos(Node* head, int pos, int val) { int len = GetLength(head); if (pos < 0 || pos > len) return false; // 位置非法 // 1. 找前驱节点（从头结点开始） Node* p = head; for (int i = 0; i < pos; i++) { p = p->next; } // 2. 新建节点 Node* newNode = new Node; newNode->data = val; // 3. 插入（核心步骤） newNode->next = p->next; p->next = newNode; return true; }3. 按位置删除（头删、尾删、中间删）
思路
1. 判空 + 检查位置
2. 从头结点找前驱节点
3. 跨越指向 + 释放节点
4. 所有位置逻辑完全统一
// pos=0 头删 pos=长度-1 尾删 通用 bool DeletePos(Node* head, int pos) { if (head->next == nullptr) return false; // 空表 int len = GetLength(head); if (pos < 0 || pos >= len) return false; // 1. 找前驱（从头结点开始） Node* p = head; for (int i = 0; i < pos; i++) { p = p->next; } // 2. 待删除节点 Node* q = p->next; // 3. 跨越删除 p->next = q->next; delete q; return true; }4. 按值删除
思路：
1. 查找值是否存在
2. 找到其前驱
3. 跨越删除
bool DeleteVal(Node* head, int val) { if (head->next == nullptr) return false; // 找前驱 p（p->next 是目标节点） Node* p = head; while (p->next != nullptr && p->next->data != val) { p = p->next; } // 没找到 if (p->next == nullptr) return false; // 删除 Node* q = p->next; p->next = q->next; delete q; return true; }5. 查找元素
思路：从第一个有效节点开始遍历，找到返回节点地址，找不到返回NULL
Node* Search(Node* head, int val) { for (Node* p = head->next; p != nullptr; p = p->next) { if (p->data == val) { return p; } } return nullptr; }6. 判空
思路：带头结点，判断头结点next是否为空
bool Is_Empty(Node* plist) { return plist->next == nullptr; }7. 销毁
思路：销毁就是不断头删
void Destroy(Node*& head) { Node* p = head->next; Node* q = nullptr; while (p != nullptr) { q = p->next; delete p; p = q; } delete head; // 释放头结点 head = nullptr; }8. 打印链表
思路：从第一个有效节点开始遍历打印
void Show(Node* head) { for (Node* p = head->next; p != nullptr; p = p->next) { cout << p->data << " "; } cout << endl; }9. 获取有效长度
思路：遍历有效节点，计数
int GetLength(Node* head) { int cnt = 0; for (Node* p = head->next; p != nullptr; p = p->next) { cnt++; } return cnt; }