企业官网建设流程全解析

单链表是数据结构课程里接触到的第一类真正意义上的动态存储结构。很多初学者会有这样的疑问：数组用起来也挺方便，为什么要费力维护一堆指针指向的结点？等真正写完建表、插入、删除、逆序这些基础操作之后就会明白，链表的优势恰恰在于动态分配和指针操作——在已知前驱结点的情况下，插入和删除只需要修改指针指向，不需要像数组那样移动大量元素。

这篇文章围绕单链表代码演示展开，用纯 C 语言实现一套完整的、可以直接复制运行的示例程序，内容包括结点结构体定义、头插法与尾插法建表、遍历打印、求链表长度、按值查找、指定位置插入、按值删除、链表逆序以及内存释放。不管是正在上数据结构课的学生，还是准备期末上机考试、考研机试的读者，都可以把这篇文章当作一份随时能查阅的代码手册。

考虑到很多读者还会搜索 Python 版本的链表操作，我在文章最后补充了 Python 的实现思路，并整理了“两个升序链表合并”和“链表逆序”两个高频扩展练习，方便有刷题需求的同学对照学习。

1. 单链表是什么，为什么一定要亲手写一遍

1.1 单链表解决什么问题

通俗地理解，数组在内存里是一段连续的地址空间，定义完长度就基本固定了。单链表则不同，它的每个结点可以存放在内存中的任意位置，通过指针把前后结点“串”起来。就像一根线穿珠子，每颗珠子都知道下一颗珠子在哪里，整条链的结构是由指针关系决定的，而不是由物理地址决定的。

用专业一点的语言来描述：单链表是一种链式存储的线性表，每个结点由数据域和指针域两部分组成。数据域存放元素信息，指针域存放直接后继结点的地址，最后一个结点的指针域指向 NULL，表示链表结束。访问元素时需要从头开始沿着指针依次寻找，因此它是一种顺序访问、随机访问能力较弱的存储结构。

把单链表和数组放在一起对比，各自的优缺点就非常清晰了。数组在中间位置插入或删除一个元素时，需要把后续所有元素整体移动，时间复杂度是 O(n)；单链表只要已经找到待插入位置的前驱结点，插入新结点只需要两次指针赋值，时间复杂度是 O(1)。同理，删除操作在已知前驱的情况下也是 O(1)。反过来，数组可以通过下标 O(1) 随机访问任意元素，单链表访问第 k 个元素则必须从头遍历，时间复杂度 O(n)。

单链表的应用场景非常广泛：操作系统中的空闲内存块管理、文件系统的目录结构、图的邻接表存储、LRU 缓存淘汰策略，以及各种需要频繁插入删除但不需要随机访问的场景，都会用到链表的思想。所以，无论是否从事底层开发，掌握单链表的建立、遍历、插入、删除、逆序等基本操作，都是数据结构学习中的必经之路。

1.2 头结点与头指针的区别

这是初学者最容易混淆的一对概念。头指针是指向链表第一个结点的指针变量，它代表整条链表的入口；如果没有头指针，链表中的所有结点都无法被访问，链表本身也就“不存在”了。

头结点则是在第一个数据结点之前额外分配的一个结点，它的数据域一般不存放有效数据，指针域指向第一个真正存储数据的结点。引入头结点的主要目的是统一处理边界情况：在头部插入和删除结点时，不需要单独判断目标位置是不是第一个结点，所有操作都变成“在某个结点的后面进行操作”，代码逻辑更加统一。习惯上，我们还会让头结点的数据域闲置或用来记录链表长度等信息。

在本文的代码中，统一使用带头结点的写法。head是头结点本身，head->next才是第一个数据结点。后面的插入、删除、逆序等函数都依赖这个约定，理解这一点是读懂后续代码的前提。

2. 环境准备与代码文件组织

2.1 编译环境

本文示例使用 C 语言编写，不依赖任何第三方库，只需要一个支持 C99 标准的编译器即可正常运行。

• Windows：可以使用 Dev-C++、Visual Studio，也可以用 CLion。
• Linux / macOS：直接使用 gcc 编译。

Linux 或 macOS 下编译运行的命令如下：

gcc -o linkedlist linkedlist.c ./linkedlist

Windows 下如果在命令行使用 gcc，编译后生成的是linkedlist.exe，直接运行即可；如果使用 Dev-C++ 或 Visual Studio，新建源文件后把代码粘贴进去，点击编译运行就能看到输出结果。

需要说明的是，示例代码中的for (int i = 0; ...)写法依赖 C99 支持。如果你的编译器默认使用更老的标准，把循环变量提前到函数开头声明即可。版本需要根据实际环境调整，本文重点演示的是单链表的代码组织思路和操作实现。

2.2 代码文件结构

本文使用单文件组织，方便初学者直接复制编译：

linkedlist.c // 单链表全部代码，包含 main 函数

不需要额外的头文件和工程配置文件。所有功能都封装成独立函数，main函数中依次调用，便于观察每一步操作的输出结果。读者也可以把各个函数按功能拆到.h和.c文件中，这是工程化的问题，初学阶段在一个文件里写好并跑通即可。

3. 单链表核心结点结构与基础操作拆解

3.1 结点结构体定义

链表的基石是结点结构体。每个结点至少包含两部分：一个用于存放数据的成员，一个用于指向下一个结点的指针成员。

typedef struct Node { int data; // 数据域，这里以 int 为例 struct Node *next; // 指针域，指向下一个结点 } Node;

这里有两个细节值得说明。第一，结构体内部的next必须写成struct Node *，因为此时类型别名Node还没有定义完成，不能直接使用Node *next。第二，typedef的作用是给结构体起一个更短的名字，定义完成后，函数签名里就可以直接写Node *，而不需要每次都写struct Node *，代码看起来更简洁。

在实际项目中，数据域不一定只是一个int。如果链表要存储学生信息，可以把数据域扩展成一个结构体，包含学号、姓名、成绩等字段。指针域的操作逻辑是完全一样的，理解了基本模型之后，换一种数据域并不会增加学习成本。

3.2 创建链表：头插法与尾插法

创建链表有两种经典方式，它们非常直观地体现了链表操作的基本逻辑。

头插法：每次把新结点插入到头结点之后，使它成为新的第一个数据结点。

Node* createByHead(int arr[], int n) { Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; for (int i = 0; i < n; i++) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = head->next; head->next = newNode; } return head; }

newNode->next = head->next先把新结点指向当前第一个数据结点，head->next = newNode再把头结点指向新结点。这两句的顺序不能颠倒，否则当前链表的后半段会丢失。由于每次新结点都插入在最前面，头插法创建的链表顺序和原数组顺序相反。

尾插法：用一个tail指针始终指向当前链表的最后一个结点，新结点追加到tail之后，然后更新tail。

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

尾插法能保持数据的原始顺序，实际项目中使用频率更高。如果只用头插法又想得到和输入一致的顺序，需要先把数据逆序，反而多一步操作。在实验报告中，老师通常要求两种方法都写一遍，目的就是让同学们体会它们的区别。

3.3 遍历打印与求链表长度

遍历是链表最基本的能力。从head->next开始，当前结点不为 NULL 时就输出数据，然后让指针向后移动。

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

求链表长度的逻辑和遍历几乎一样，区别只是统计结点个数而不打印。

int getLength(Node *head) { int count = 0; Node *p = head->next; while (p != NULL) { count++; p = p->next; } return count; }

这里有一个容易忽略的边界条件：空链表时head->next == NULL，while 循环一次都不会执行，返回长度为 0。在编写依赖链表长度的代码时，必须先考虑空表情况，避免出现长度为 0 时继续访问结点的逻辑错误。

3.4 按值查找与指定位置插入

按值查找比较简单，遍历链表，遇到数据域等于目标值的结点就返回该结点的指针，找不到返回 NULL。

Node* findNode(Node *head, int target) { Node *p = head->next; while (p != NULL) { if (p->data == target) { return p; } p = p->next; } return NULL; }

插入是单链表里最容易写错的操作。下面实现的是“在第 pos 个位置（从 1 开始计数）插入值为 value 的新结点”。

int insertNode(Node *head, int pos, int value) { Node *p = head; int i = 0; while (p != NULL && i < pos - 1) { p = p->next; i++; } if (p == NULL) { return 0; } Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = value; newNode->next = p->next; p->next = newNode; return 1; }

这段代码最关键的是两步指针操作：

newNode->next = p->next; // 新结点先连接后驱 p->next = newNode; // 前驱再连接新结点

顺序必须如此。如果先写p->next = newNode，原来的p->next所指向的后半段链表就找不到了，链表会发生断链。很多新手写完代码后，发现链表输出到插入位置就结束了，多半就是这个原因。

p从头结点开始移动还有一个额外好处：插入位置为 1 时，走完循环后p就是头结点，逻辑和其他位置完全一致，不需要为“插入头部”单独写特判。函数返回 0 表示插入失败，返回 1 表示插入成功，调用方可以据此处理异常。

3.5 按值删除结点

删除操作的关键是要找到目标结点的前驱结点，而不是目标结点本身。因为单链表只能从前往后走，如果只拿到目标结点，是无法访问它前驱的。

int deleteNode(Node *head, int target) { Node *p = head; while (p->next != NULL && p->next->data != target) { p = p->next; } if (p->next == NULL) { return 0; } Node *temp = p->next; p->next = temp->next; free(temp); return 1; }

删除操作分三步：第一步，从 head 开始找前驱 p，循环条件是p->next不为空且后继结点的数据不等于目标值；第二步，把 p 的 next 指向目标结点的后继，相当于把目标结点从链表中“摘”下来；第三步，free 目标结点所占用的内存。

p->next = temp->next; free(temp);

先改指针，再释放内存，这个顺序也不能反。如果先free(temp)，temp 指向的内存已经归还系统，再访问temp->next就是未定义行为，程序可能随时崩溃。循环条件写成p->next->data != target而不是p->data != target，就是为了让 p 始终停在目标结点的前驱位置。

3.6 单链表逆序

单链表逆序是面试和上机考试的高频题。思路是准备三个指针：prev记录已经逆序完成部分的前一个结点，cur记录当前待处理结点，next记录cur的后继，防止断链。

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

循环内部做的事情是重复三步：先把next保存下来，再把cur的next指向前一个结点prev，最后把三个指针整体向后移动。循环结束后，原链表的最后一个结点成为新的第一个数据结点，把它挂到头结点后面即完成逆序。

整个过程是原地完成，没有申请新的结点，空间复杂度是 O(1)。初学阶段建议在纸上画一条包含三四个结点的链表，按照循环步骤逐行推演指针的变化，这一步理解到位之后，后面再学习双向链表、循环链表的反转都会顺很多。

4. 完整代码演示

4.1 完整可运行代码

把前面所有操作整合到一个linkedlist.c文件中：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } Node; // 头插法创建链表 Node* createByHead(int arr[], int n) { Node *head = (Node *)malloc(sizeof(Node)); head->next = NULL; for (int i = 0; i < n; i++) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = head->next; head->next = newNode; } return head; } // 尾插法创建链表 Node* createByTail(int arr[], int n) { Node *head = (Node *)malloc(sizeof(Node)); Node *tail = head; head->next = NULL; for (int i = 0; i < n; i++) { Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return head; } // 遍历打印链表 void printList(Node *head) { Node *p = head->next; while (p != NULL) { printf("%d", p->data); if (p->next != NULL) { printf(" -> "); } p = p->next; } printf("\n"); } // 求链表长度 int getLength(Node *head) { int count = 0; Node *p = head->next; while (p != NULL) { count++; p = p->next; } return count; } // 按值查找 Node* findNode(Node *head, int target) { Node *p = head->next; while (p != NULL) { if (p->data == target) { return p; } p = p->next; } return NULL; } // 指定位置插入 int insertNode(Node *head, int pos, int value) { Node *p = head; int i = 0; while (p != NULL && i < pos - 1) { p = p->next; i++; } if (p == NULL) { return 0; } Node *newNode = (Node *)malloc(sizeof(Node)); newNode->data = value; newNode->next = p->next; p->next = newNode; return 1; } // 按值删除 int deleteNode(Node *head, int target) { Node *p = head; while (p->next != NULL && p->next->data != target) { p = p->next; } if (p->next == NULL) { return 0; } Node *temp = p->next; p->next = temp->next; free(temp); return 1; } // 链表逆序 void reverseList(Node *head) { Node *prev = NULL; Node *cur = head->next; while (cur != NULL) { Node *next = cur->next; cur->next = prev; prev = cur; cur = next; } head->next = prev; } // 释放整个链表 void freeList(Node *head) { Node *p = head; while (p != NULL) { Node *temp = p; p = p->next; free(temp); } } int main() { int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("=== 尾插法创建链表 ===\n"); Node *list1 = createByTail(arr, n); printf("链表内容："); printList(list1); printf("链表长度：%d\n", getLength(list1)); printf("\n=== 头插法创建链表 ===\n"); Node *list2 = createByHead(arr, n); printf("链表内容："); printList(list2); printf("\n=== 按值查找 ===\n"); Node *found = findNode(list1, 3); if (found != NULL) { printf("找到了结点：%d\n", found->data); } else { printf("未找到该结点\n"); } printf("\n=== 指定位置插入 ===\n"); if (insertNode(list1, 3, 99)) { printf("插入成功，插入后链表："); printList(list1); } else { printf("插入失败，位置不合法\n"); } printf("\n=== 按值删除 ===\n"); if (deleteNode(list1, 99)) { printf("删除成功，删除后链表："); printList(list1); } else { printf("删除失败，链表中不存在该值\n"); } printf("\n=== 链表逆序 ===\n"); reverseList(list1); printf("逆序后链表："); printList(list1); freeList(list1); freeList(list2); return 0; }

4.2 预期运行结果

编译运行后，输出如下：

=== 尾插法创建链表 === 链表内容：1 -> 2 -> 3 -> 4 -> 5 链表长度：5 === 头插法创建链表 === 链表内容：5 -> 4 -> 3 -> 2 -> 1 === 按值查找 === 找到了结点：3 === 指定位置插入 === 插入成功，插入后链表：1 -> 2 -> 99 -> 3 -> 4 -> 5 === 按值删除 === 删除成功，删除后链表：1 -> 2 -> 3 -> 4 -> 5 === 链表逆序 === 逆序后链表：5 -> 4 -> 3 -> 2 -> 1

4.3 结果说明

从运行结果中可以验证几件事情。尾插法创建的链表保持了1 2 3 4 5的原始顺序，而头插法得到的是5 4 3 2 1，两者对比能很清楚地区分两种建表方式。在第 3 个位置插入 99 后，链表变成1 -> 2 -> 99 -> 3 -> 4 -> 5，说明插入逻辑正确处理了指定位置。删除 99 后链表恢复原样，说明按值删除只移除第一个匹配的结点，不影响其他元素。最后链表逆序成5 -> 4 -> 3 -> 2 -> 1，说明三指针逆序的写法达到了预期效果。

5. 常见错误与排查思路

5.1 空指针导致的段错误

新手最常见的报错是程序一运行就崩溃，或者出现 Segmentation Fault。根本原因通常是访问了空指针，例如遍历时没有判断 p 是否为 NULL 就直接取p->data，或者结点被 free 之后仍然继续使用。排查时可以在关键函数入口打印调试信息，再用小规模数据逐步缩小范围；养成每次循环先判断指针是否有效的习惯，这类问题会减少很多。

5.2 断链问题

插入或删除后链表内容残缺，通常是修改指针指向的顺序出了问题。插入时一定要先执行newNode->next = p->next，再执行p->next = newNode；删除时先让前驱绕过目标结点，再释放目标结点。凡是涉及两个结点之间的指针变化，都建议先用示意图画出前后状态，再动手写代码，这样基本可以避免断链。

5.3 内存泄漏

程序功能正常，但反复执行插入删除后内存占用不断上涨，多半是删除结点或清空链表时没有调用 free。链表由动态内存分配而来，C 语言不会自动回收。为此我在代码里单独设计了freeList函数，从头开始逐个释放所有结点，并在 main 结束前调用，确保程序退出时没有悬挂的内存。

5.4 边界位置判断失误

插入位置为 1、插入位置超过链表长度、删除不存在的值、对空链表调用操作，这些都属于边界情况。如果函数返回值设计成 0/1 状态码，调用方可以根据返回值决定继续处理还是输出错误提示。建议把上面几种边界场景整理成测试数据，逐一验证，防止到了考试或面试时因为边界条件丢分。

6. 最佳实践与工程建议

6.1 命名规范

链表指针的命名要能一眼看出含义。习惯上，头结点用 head，遍历指针用 p 或 cur，前驱用 prev，后继用 next，临时保存的结点用 temp 或 nextNode，尾结点用 tail。函数命名采用“动词 + 名词”的方式，例如createByTail、printList、deleteNode、reverseList，阅读代码时不用看实现也能推断出函数作用。

6.2 内存管理

每次 malloc 之后都要考虑对应的 free 时机。建议在代码里明确分配和释放的职责：例如createByTail负责申请内存，freeList负责释放内存，删除函数只释放被摘下来的那个结点。这样职责清晰后，内存泄漏的概率会大幅降低。在生产环境中，还应该判断 malloc 返回值是否为 NULL，避免内存分配失败后继续使用空指针。

6.3 防御式编程

不要把输入数据都假设成合法值。插入位置可能为负数或超出链表长度，删除目标可能不存在，这些情况都应该通过返回值或错误信息反馈给调用方。本文的insertNode和deleteNode都返回状态码，就是典型的防御式写法。函数只做一件事，并且明确告诉调用方执行结果，是工程上比较推崇的风格。

6.4 测试思路

链表代码非常适合按动作维度测试：建表后立刻打印，插入后立刻打印，删除后立刻打印，每一步都验证中间状态。这样可以在出问题时快速定位是哪一步操作引起的。调试链表问题时，画图比看日志更高效，建议把当前所有结点的指针指向画出来，再对照代码逐行走一遍。练习时也可以自己设计一组更长的测试数据，覆盖空表、单结点、满表等情况。

7. 进阶练习与扩展

7.1 合并两个升序链表

“已知两个长度为 m 和 n 的升序单链表，将它们合并为一个升序链表”是笔试和面试中的经典题。思路是用pa、pb两个指针分别遍历两条链表，每次取较小值的结点接到结果链表尾部。

Node* mergeTwoLists(Node *la, Node *lb) { Node *head = (Node *)malloc(sizeof(Node)); Node *tail = head; Node *pa = la->next; Node *pb = lb->next; while (pa != NULL && pb != NULL) { if (pa->data <= pb->data) { tail->next = pa; pa = pa->next; } else { tail->next = pb; pb = pb->next; } tail = tail->next; } tail->next = (pa != NULL) ? pa : pb; return head; }

需要注意，这个做法直接复用了原链表的结点，新链表并没有额外申请结点，合并结束后原两条链表的 next 结构已经改变。如果题目要求不修改原链表，就需要复制结点后再合并。做题前看清题目约束，避免实现和需求错位。

7.2 Python 版本实现

不少同学刷题时会用到 Python。Python 版链表用类定义结点，指针的概念变成了对象引用，写起来更简洁：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverse_list(head: ListNode) -> ListNode: prev = None cur = head while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev

这个逆序写法和上面的 C 版本是一一对应的。理解 C 版本的三个指针之后，Python 版本读起来会非常轻松。LeetCode 上默认使用的ListNode结构就和这个定义类似，刷链表题时可以直接复用。

7.3 下一步学什么

单链表掌握之后，可以按顺序继续学习双向链表、循环链表，然后练习约瑟夫环、链表排序、每 k 个结点一组反转等综合题目。建议把基础操作的复杂度一起整理记忆：查找 O(n)、已知前驱时插入 O(1)、删除 O(1)、遍历 O(n)。有了单链表的指针操作功底，后面学习二叉树、图的邻接表都会轻松很多。

如果只看不写，链表永远学不会。建议把本文的完整代码先在自己电脑上编译跑通，然后把插入和删除两个函数遮住，自己默写三遍，每一遍都画出对应的指针变化图。坚持这个习惯，数据结构的上机考试和面试手写题基本不会慌。后续遇到其他链表题目，也可以回到这套基础函数上来对照理解，祝你写出链表代码时一次通过。