数据结构 | 单链表

一、为什么要学习单链表在学习顺序表时我们发现它存在一些难以避免的缺陷必须占用一整块连续的内存空间头部、中间插入或删除需要大量移动元素效率很低动态扩容需要开辟新空间并复制数据代价较高为了解决这些问题我们引入了链表而单链表是最基础、最核心的链表结构。二、单链表的特点逻辑相邻物理不一定相邻不要求连续的内存空间内存利用率更高完美避开顺序表插入删除效率低的问题但失去了随机存取的能力不能直接按下标访问元素【顺序表 物理存储图】【单链表 物理存储图】三、单链表的结构单链表由一个个节点组成每个节点包含两部分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. 所有位置逻辑完全一样无特殊处理// pos0 头插 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. 所有位置逻辑完全统一// pos0 头删 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; // 找前驱 pp-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. 查找元素思路从第一个有效节点开始遍历找到返回节点地址找不到返回NULLNode* 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; }