当前位置：首页 > news >正文

单链表深度精讲，从零手写完整单链表、头插尾插、任意增删、链表反转、复杂度与面试考点全解

news 2026/6/12 10:19:52

0. 前言

我们学完了 C++ STL 去重、合并、集合算法，彻底掌握了有序数据预处理的最优写法。而昨天第五十四天的顺序表学习，让我们清楚看到了顺序表的致命短板：内存连续、固定排布，导致头部/中间插入删除必须大量移位，效率极低，且必须开辟连续内存，容易产生内存浪费与大块内存申请失败问题。

为了解决顺序表的缺陷，数据结构引入了链表结构。链表是线性表的第二种核心存储方式，彻底颠覆顺序表的内存模型：不连续内存、动态按需分配、无数据移位、插入删除高效。

链表分为单链表、双链表、循环链表，其中单链表是所有链表的基础，也是面试笔试最高频的数据结构手写代码题。链表题贯穿算法刷题基础、LeetCode 入门题库、面试手撕代码，是必须做到闭眼默写、零Bug、边界全覆盖的核心结构。

很多初学者学链表只会背代码，不懂指针指向逻辑、不懂断链风险、不懂边界判空、不懂头结点意义、分不清带头结点与不带头结点的区别，刷题时频繁出现死循环、内存泄漏、断链、空指针崩溃。

今天我们从零彻底吃透单链表全套体系，从理论模型、内存结构、优缺点对比、带头结点设计、全套增删查改、链表反转、边界处理、复杂度分析、手写工业级代码、高频坑点、面试问答一站式搞定，为后续双链表、栈队列、哈希表链式解决铺垫绝对扎实的底层功底。

1. 单链表核心理论（必背基础）

1.1 什么是单链表？

单链表是一种链式存储的线性表。它不再需要连续内存，而是将每一个数据单元独立封装为结点（Node），每个结点包含两部分：

1.数据域：存储当前结点有效数据；

2.指针域：存储下一个结点的地址指针。

结点之间通过指针串联，逻辑连续、物理内存不连续。

1.2 为什么要引入「头结点」？（面试高频）

单链表分为两种实现：不带头结点、带头结点。

工程与算法中统一使用带头结点单链表。

头结点是一个不存储有效数据的虚拟结点，永远指向链表头部，作用：

1. 统一空表、非空表操作逻辑，无需特殊处理头插、删头结点的边界；

2. 避免链表头指针频繁修改，减少指针逻辑复杂度；

3. 彻底规避空指针、断链问题，代码更稳健。

核心结论：带头结点是工业级标准，所有手写链表默认带头结点。

1.3 顺序表 VS 单链表终极对比

顺序表优势：支持随机访问 O(1)、缓存命中率高、访问速度快；

顺序表劣势：中间/头部增删 O(n)、需要连续内存、存在扩容开销与内存浪费；

单链表优势：按需动态开辟内存、无扩容浪费、任意位置插入删除仅 O(1)（找到位置后）、无需连续内存；

单链表劣势：不支持随机访问、只能从头遍历、查找访问 O(n)、存在指针存储开销。

2. 单链表结点结构设计

标准单链表结点结构体，C++ 通用定义：

// 单链表结点 struct ListNode { int val; // 数据域 ListNode* next; // 指针域：指向下一结点 // 构造初始化 ListNode(int v = 0) : val(v), next(nullptr) {} };

每一个结点独立开辟内存，next 为空代表链表终点。

3. 从零手写完整工业级单链表

本节实现带头结点、无内存泄漏、边界全覆盖、可直接面试默写的完整单链表，包含：初始化、尾插、头插、任意位置插入、按值删除、按位置删除、查找、链表反转、清空、析构释放。

#include <iostream> using namespace std; // 定义单链表结点 struct ListNode { int val; ListNode* next; ListNode(int v = 0) : val(v), next(nullptr) {} }; // 单链表类（带头结点） class SingleList { private: ListNode* head; // 头结点指针 public: // 构造：初始化头结点 SingleList() { head = new ListNode(); } // 1. 头插法 void pushFront(int val) { ListNode* newNode = new ListNode(val); newNode->next = head->next; head->next = newNode; } // 2. 尾插法 void pushBack(int val) { ListNode* cur = head; // 遍历到最后一个结点 while(cur->next != nullptr) { cur = cur->next; } cur->next = new ListNode(val); } // 3. 任意位置插入（pos从0开始，0为第一个有效结点） void insert(int pos, int val) { if(pos < 0) return; ListNode* cur = head; // 找到pos的前驱结点 for(int i = 0; i < pos; i++) { if(cur->next == nullptr) return; // 位置越界 cur = cur->next; } ListNode* newNode = new ListNode(val); newNode->next = cur->next; cur->next = newNode; } // 4. 按位置删除 void erasePos(int pos) { if(pos < 0) return; ListNode* cur = head; // 找到前驱 for(int i = 0; i < pos; i++) { if(cur->next == nullptr) return; cur = cur->next; } if(cur->next == nullptr) return; ListNode* delNode = cur->next; cur->next = delNode->next; delete delNode; // 防止内存泄漏 } // 5. 按值删除（删除第一个匹配值） void eraseVal(int val) { ListNode* cur = head; while(cur->next != nullptr) { if(cur->next->val == val) { ListNode* delNode = cur->next; cur->next = delNode->next; delete delNode; return; } cur = cur->next; } } // 6. 查找值是否存在 bool find(int val) { ListNode* cur = head->next; while(cur != nullptr) { if(cur->val == val) return true; cur = cur->next; } return false; } // 7. 链表反转（核心面试算法） void reverse() { ListNode* pre = nullptr; ListNode* cur = head->next; ListNode* nxt = nullptr; while(cur != nullptr) { nxt = cur->next; // 保存后继 cur->next = pre; // 反转指向 pre = cur; cur = nxt; } head->next = pre; // 头结点指向新链表首部 } // 8. 清空所有有效结点 void clear() { ListNode* cur = head->next; while(cur != nullptr) { ListNode* tmp = cur; cur = cur->next; delete tmp; } head->next = nullptr; } // 9. 打印链表 void print() { ListNode* cur = head->next; cout << "链表元素："; while(cur != nullptr) { cout << cur->val << " "; cur = cur->next; } cout << endl; } // 析构：释放全部内存 ~SingleList() { clear(); delete head; } }; // 测试主函数 int main() { SingleList lst; lst.pushBack(10); lst.pushBack(20); lst.pushFront(5); lst.insert(2, 15); lst.print(); lst.eraseVal(20); lst.print(); lst.reverse(); lst.print(); return 0; }