企业官网建设流程全解析

这次我们直接看单链表。

很多同学刚接触“单链表”时，第一反应是：数组用着挺方便，为什么还要单链表？这个问题如果没想明白，后面写插入、删除、逆序、合并的代码就会一直别扭。先把结论放在前面：单链表是理解指针操作、内存管理和后续算法题的地基，大部分数据结构实验、考研算法题和面试手撕代码都从单链表开始。

这篇文章会覆盖单链表定义、结点结构设计、带头结点与不带头结点的区别、头插法、尾插法、按值删除、按位序插入、遍历查找、单链表逆序、合并两个升序单链表、判断链表是否有环，并给出 C、Python、Java 三套可运行示例。代码全部可以直接复制编译运行，适合正在上数据结构课、准备考研复试或刷 LeetCode 链表专题的读者。

1. 单链表核心知识速览

单链表和数组的核心区别是：数组在内存中占用连续存储空间，支持 O(1) 随机访问；单链表不要求内存连续，每个结点按需分配，插入和删除操作只需要修改指针，但是随机访问只能从头开始遍历，时间复杂度是 O(n)。

2. 单链表适用场景与使用边界

先判断一下：你什么时候该用单链表？什么时候不该用？

适合使用单链表的场景：

• 频繁在头部或中间插入、删除元素，且不便搬移大量数据。
• 无法预估数据总量，需要动态增长，数组扩容成本高。
• 需要实现诸如 LRU 缓存、任务队列、待办列表这类“逐步串联”的数据结构。
• 学习指针、引用和内存管理。

不适合使用单链表的场景：

• 需要频繁按下标随机访问元素。链表要遍历，数组更合适。
• 数据量小且长度固定。直接用数组更简单，没必要引入结点分配开销。
• 对缓存命中率要求高的高性能计算场景。链表结点在内存中可能分散，CPU 缓存不友好。
• 需要双向遍历的场景。单链表只有 next 指针，回退需要重新从头遍历，这种情况应使用双向链表。

使用边界要说清楚：单链表不是“更快的数组”，而是“存储方式不同的线性表”。它牺牲了随机访问能力，换来插入删除的灵活性和按需分配的内存使用方式。学习时不要只会背定义，要通过代码实验去观察指针变化过程。

3. 环境准备与前置条件

单链表不需要 GPU、不需要 CUDA、不需要下载模型文件。准备一个能运行 C、Python 或 Java 的环境即可。

推荐环境如下：

C 语言示例编译命令：

gcc -g -o list list.c ./list

Python 示例运行命令：

python3 list.py

Java 示例编译运行命令：

javac ListNode.java SingleLinkedList.java java SingleLinkedList

如果本机没有安装编译器，也可以使用在线 IDE。学习阶段建议优先在本地环境运行，因为本地调试器能直接看到指针指向的地址，这对理解单链表“串联”关系帮助很大。

4. 单链表的定义与结点结构设计

4.1 单链表是什么

单链表是线性表的链式存储结构。它由一组结点组成，每个结点存储一个数据元素和一个指向下一个结点的指针。最后一个结点的 next 指向空，标记链表结束。

单链表和数组一样描述的是“线性关系”，但存储方式完全不同。数组是静态分配的连续空间，链表是动态分配的离散空间，依靠指针把结点串联起来。

4.2 C 语言中的结构体定义

在 C 语言中，结点就是结构体变量。定义一个链表结点，需要同时定义数据域和指针域。以数据域为 int 为例：

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef struct LNode { int data; struct LNode* next; } LNode;

这里的关键点：struct LNode* next是结点的指针域，它指向下一个结点。如果链表到此结束，则 next 为 NULL。很多初学者会把next理解成“另一个结点”，更准确的说法是：next保存的是下一个结点的地址。

再看结构体变量的定义。上面代码中的这一句：

typedef struct LNode { int data; struct LNode* next; } LNode;

等价于：

struct LNode { int data; struct LNode* next; }; typedef struct LNode LNode;

定义完成后，LNode node;表示定义一个结构体变量变量，LNode* p;表示定义一个指向该结构体的指针变量。

4.3 Python 中的类定义

Python 没有指针，但引用本身就具备指针语义。定义结点如下：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

Python 中self.next保存的就是下一个 ListNode 对象的引用，和 C 语言中的指针思路一致，只是不需要手动管理内存。

4.4 Java 中的结点定义

Java 方式和 Python 类似：

public class ListNode { int val; ListNode next; public ListNode() {} public ListNode(int val) { this.val = val; } }

4.5 带头结点还是不带头结点

这是一个很容易绕晕的问题。单链表有两种组织方式：

• 不带头结点：链表第一个结点直接存储数据，head 指向第一个数据结点。
• 带头结点：链表有一个额外的头结点，它的 data 域不存储有效数据，next 指向第一个数据结点。

带头结点的好处很多：插入第一个数据结点和插入其他位置的操作逻辑可以统一，删除第一个数据结点时也不需要特殊处理头指针。单链表实验和大部分教材示例都建议使用带头结点。

头结点的存在意义是“占位”，它让空链表也有一个可管理的对象，初始状态为只有一个头结点，next 为 NULL。

4.6 单链表定义小结

定义一个单链表，核心要素有三个：

• 数据域：存储当前结点的值。
• 指针域：存储下一个结点的地址。
• 头指针：指向链表第一个结点，是访问整个链表的入口。

5. 单链表基本操作实现

单链表的基本操作实验，通常包括初始化、头插法创建、尾插法创建、按值删除、按位序插入、按值查找、遍历输出。下面给出一套完整可运行的 C 语言实现。

5.1 初始化带头结点的单链表

LNode* initList() { LNode* head = (LNode*)malloc(sizeof(LNode)); head->data = 0; head->next = NULL; return head; }

5.2 头插法创建单链表

头插法每次把新结点插到头结点后面。特点是最后插入的结点会出现在链表最前面，相当于逆序建表。

void createByHead(LNode* head, int arr[], int n) { for (int i = 0; i < n; i++) { LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = arr[i]; s->next = head->next; head->next = s; } }

执行顺序可以这样理解：先让新结点指向原来的第一个数据结点，再让头结点的 next 指向新结点。顺序不能反过来。如果先执行head->next = s，原来的链表就会丢失。

5.3 尾插法创建单链表

尾插法每次把新结点放到链表尾部。为了不每次遍历到尾结点，需要用一个 tail 指针记录当前尾部结点。

void createByTail(LNode* head, int arr[], int n) { LNode* tail = head; for (int i = 0; i < n; i++) { LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = arr[i]; s->next = NULL; tail->next = s; tail = s; } }

尾插法保持了原始数据的相对顺序，是实验中更常用的建表方式。

5.4 遍历输出

void printList(LNode* head) { LNode* p = head->next; while (p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); }

5.5 按值查找

LNode* findByValue(LNode* head, int value) { LNode* p = head->next; while (p != NULL) { if (p->data == value) { return p; } p = p->next; } return NULL; }

5.6 按位序插入

在第 position 个位置插入结点，position 从 1 开始计数。需要先找到第 position-1 个结点。

bool insertByPosition(LNode* head, int position, int value) { LNode* p = head; int i = 0; while (p != NULL && i < position - 1) { p = p->next; i++; } if (p == NULL) { return false; } LNode* s = (LNode*)malloc(sizeof(LNode)); s->data = value; s->next = p->next; p->next = s; return true; }

5.7 按值删除

删除第一个值为 value 的结点。因为要修改前驱结点的 next，所以需要找到待删除结点的前驱。

bool deleteByValue(LNode* head, int value) { LNode* p = head; while (p->next != NULL) { if (p->next->data == value) { LNode* q = p->next; p->next = q->next; free(q); return true; } p = p->next; } return false; }

5.8 释放整个链表

手动管理内存的 C 代码，在程序结束前要释放所有结点，包括头结点。

void freeList(LNode* head) { LNode* p = head; while (p != NULL) { LNode* next = p->next; free(p); p = next; } }

5.9 主函数测试

int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); LNode* head = initList(); createByTail(head, arr, n); printf("尾插法结果：\n"); printList(head); LNode* found = findByValue(head, 3); printf("查找值为3的结点：%s\n", found != NULL ? "找到" : "未找到"); insertByPosition(head, 2, 99); printf("插入99到第2位后：\n"); printList(head); deleteByValue(head, 4); printf("删除值为4的结点后：\n"); printList(head); freeList(head); return 0; }

运行结果：

尾插法结果： 1 -> 2 -> 3 -> 4 -> 5 -> NULL 查找值为3的结点：找到 插入99到第2位后： 1 -> 99 -> 2 -> 3 -> 4 -> 5 -> NULL 删除值为4的结点后： 1 -> 99 -> 2 -> 3 -> 5 -> NULL

6. 单链表功能测试与效果验证

基本操作写完以后，建议按照下面这套顺序验证，不要只看代码逻辑。

6.1 测试目的

验证单链表的创建、插入、删除和查找功能是否符合预期，同时观察边界条件是否处理正确。

6.2 测试用例建议

6.3 判断是否成功

判定的标准是：遍历结果和预期一致，且没有丢结点、没有内存泄漏。C 语言环境下可以使用 Valgrind 检查内存泄漏：

valgrind --leak-check=full ./list

如果显示no leaks are possible，说明所有结点都被正确释放。

6.4 常见失败原因

• 插入时先改 head->next，导致原链表断开。
• 删除时没有保存待删除结点的 next，free 之后丢失后续链表。
• 遍历时循环条件写错，多走一步访问 NULL 导致段错误。
• malloc 后忘记判断是否为空。
• 忘记释放不再使用的结点。

7. 单链表进阶操作：逆序、合并、判环

基础操作跑通后，可以做三件事：单链表逆序、合并两个升序单链表、判断链表是否有环。这三个操作是单链表实验中出镜率最高的题目，也是 LeetCode 上的经典原题。

7.1 单链表逆序

Python 版本的迭代式逆序实现如下：

def reverse_list(head): prev = None cur = head while cur is not None: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

这里的核心思想是：用 cur 指向当前要处理的结点；用 prev 记录已经处理好的链表头；用 nxt 保存 cur 原来的下一个结点，否则修改 next 之后就会丢失后续链表。

C 语言版本：

void reverseList(LNode* head) { LNode* prev = NULL; LNode* cur = head->next; while (cur != NULL) { LNode* nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } head->next = prev; }

Java 版本：

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; } return prev; }

逆序测试用例：链表 1 -> 2 -> 3 -> 4 -> 5，逆序后为 5 -> 4 -> 3 -> 2 -> 1。递归方法也能实现逆序，但迭代方法空间复杂度只有 O(1)，更推荐先掌握。

7.2 合并两个升序单链表

已知两个长度为 m 和 n 的升序单链表，将它们合并为一个有序链表，是单链表考研题和面试题中的高频题目。要求是两个链表依然升序。

Python 实现：

def merge_two_lists(a, b): dummy = ListNode(0) tail = dummy while a is not None and b is not None: if a.val <= b.val: tail.next = a a = a.next else: tail.next = b b = b.next tail = tail.next if a is not None: tail.next = a if b is not None: tail.next = b return dummy.next

Java 实现：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode tail = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; } else { tail.next = l2; l2 = l2.next; } tail = tail.next; } tail.next = (l1 != null) ? l1 : l2; return dummy.next; }

合并操作的解题要点有两个。第一，使用 dummy 结点避免处理“链表头最终是 a 还是 b”的分支判断。第二，循环结束后，最多还剩一条链表未遍历完，直接把尾指针接到剩余链表头部即可。

测试用例：

7.3 判断单链表是否有环

使用快慢指针：慢指针每次走一步，快指针每次走两步。如果链表有环，快指针最终会追上慢指针；如果无环，快指针会先走到 NULL。

def has_cycle(head): slow = head fast = head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next if slow == fast: return True return False

这个操作不修改链表结构，只做检测，在面试中经常作为附加题出现。

8. 单链表复杂度分析与性能观察

时间复杂度汇总：

空间复杂度方面，基本操作额外空间为 O(1)，合并和逆序的迭代实现额外空间也是 O(1)。递归实现逆序或合并时，递归栈深度为 O(n)，需要注意。

观察性能时，比较典型的现象是：当链表规模增大时，按值查找和尾插法（不维护尾指针）会明显变慢，因为每次都要从头遍历。这就是为什么在实验中使用尾插法时一定要维护 tail 指针。

单链表在性能上还有一个特点：内存碎片化。C 语言中每次 malloc 一个结点，结点在堆中的地址不一定连续，遍历链表时 CPU 缓存命中率不如数组。数据量很大时，即使时间复杂度和数组操作同为 O(n)，链表可能仍然更慢。这是链表的固有特性，不是代码问题。

9. 单链表常见问题与排查方法

遇到链表问题，第一件事不是改代码，而是画出当前链表和指针变化图。把 head、p、s、prev、cur、nxt 这些指针用箭头表示，每一步修改都对应一条赋值语句，只要箭头画正确，代码自然写正确。

10. 单链表最佳实践与使用建议

结合实验和刷题经验，给出一套可以直接沿用的实践建议。

10.1 统一使用带头结点

除非题目明确要求不带头结点，否则建议统一带头结点。带头结点可以消除空链表和非空链表操作的差异，删除首元结点时不需要修改头指针，代码逻辑更简洁。

10.2 建表优先使用尾插法

如果数据顺序有意义，优先使用尾插法。头插法虽然代码看着简单，但会让数据逆序，容易造成误解。在单链表基本操作实验中，尾插法配合 tail 指针是更稳妥的方案。

10.3 善用 dummy 结点

在合并有序链表、删除倒数第 N 个结点等场景中，使用 dummy 结点可以减少边界判断。它的核心价值是提供一个虚拟的前驱，避免单独处理头结点被修改的情况。

10.4 双指针技巧值得重点掌握

链表中大量算法题的优化思路都来自双指针。快慢指针可以判环、找中点、找倒数第 K 个结点；前后指针可以在一次遍历内完成逆序；临时指针可以在交换结点时不丢失链表引用。

10.5 分离逻辑测试和效果复核

写链表代码时，先跑小规模用例，比如 3 个结点以内的插入删除，打印每一步结果。确认无误后再跑大规模数据。实验报告中应当包含测试输入、实际输出和结果分析，而不只是贴一段代码。

10.6 注意代码规范与算法复用

deleteNode、isEmpty、getSize这类工具函数可以单独封装。C 语言中封装成函数指针结构体，Java 中使用LinkedList类，Python 中定义LinkedList类统一管理。这和实际工程中把链表封装成可复用组件的思路一致。

10.7 应用场景落地

• 实现 LRU 缓存时，哈希表负责 O(1) 查找，单链表或双向链表负责记录访问顺序。
• 实现任务队列时，单链表天然支持头部出队、尾部入队，比数组扩容方案更灵活。
• 实现多项式加法时，单链表结点可以存储系数和指数，便于动态维护多项式项数。

11. 总结

单链表定义和实现的核心并不复杂：一个数据域、一个指针域，加上对指针的插入、删除和遍历操作。真正难的是理解指针在内存中如何串联结点，以及如何通过前驱结点完成插入和删除。

建议先跑通这篇里的 C 语言完整示例，再用 Python 实现逆序和合并两个升序链表，最后用 Java 手写一遍判环。三个语言各写一遍，单链表的基本操作实验基本就掌握了。最先要验证的功能是头插法和尾插法创建链表，最容易踩的坑是插入时指针修改顺序和删除时丢失后继结点。

后续可以从单链表扩展到双向链表、循环链表、静态链表，再进阶到 LRU 缓存、链表排序、相交链表、回文链表等综合题。数据结构这一块，单链表的实现会了，后面很多链式结构都顺理成章。建议收藏备用，写实验报告或刷题前拿出来过一遍。