一、顺序表的“阿喀琉斯之踵”上一篇我们学习了顺序表它像一排紧挨着的座位随机访问极快实现也简单。但我们也发现了它的两大痛点插入/删除效率低想在中间插入一个元素必须把后面的所有人往后挪一位时间复杂度为 O(n)。扩容麻烦静态顺序表容量固定满了就没法继续存数据。如果数据元素不必“挤”在连续的内存里而是通过某种方式“手拉手”连接起来是不是就能避免频繁搬移数据这就是单链表Singly Linked List的核心思想。二、单链表长什么样单链表不再要求数据在物理内存中连续存放。每个元素除了保存自己的数据外还保存着下一个元素在哪里的信息。我们把这样的元素称为节点Node每个节点包含两部分数据域存放实际的数据。指针域存放下一个节点的地址。内存中的实际分布离散0x2000 0x1000 0x3000 ┌─────┐ ┌─────┐ ┌─────┐ │ 10 │ │ 20 │ │ 30 │ │0x1000│──→│0x3000│──→│ NULL│ └─────┘ └─────┘ └─────┘逻辑上看10 → 20 → 30 → NULL关键区别顺序表靠“物理相邻”表示逻辑关系单链表靠“指针”表示逻辑关系。三、初识指针单链表的“胶水”要实现单链表我们需要先了解 C 语言中的指针Pointer。别担心这里只用到最基础的用法。指针就是一个存储内存地址的变量int a 10; int *p a; // p 是一个指针存储了变量 a 的地址 printf(%d, *p); // 通过 *p 可以访问 a 的值输出 10在单链表中每个节点的“指针域”就是一个指针指向下一个节点。四、单链表的 C 语言实现4.1 定义节点结构体#include stdio.h #include stdlib.h // 用于 malloc 和 free // 定义链表节点 typedef struct Node { int data; // 数据域 struct Node *next; // 指针域指向下一个节点 } Node;4.2 创建新节点// 创建一个值为 value 的新节点 Node* createNode(int value) { Node *newNode (Node*)malloc(sizeof(Node)); // 申请内存 newNode-data value; newNode-next NULL; // 新节点默认指向空 return newNode; }malloc的作用是在内存中“挖”一块空间给新节点这样节点就不需要连续排列了。4.3 初始化链表带头节点我们创建一个头节点它不存储实际数据只作为链表的入口这样操作更方便。// 初始化空链表返回头节点 Node* initList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; // 空链表头节点后面什么都没有 return head; }4.4 在尾部添加元素尾插法// 在链表末尾添加元素 void append(Node *head, int value) { Node *newNode createNode(value); // 找到最后一个节点 Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode; // 让最后一个节点指向新节点 }4.5 在头部添加元素头插法// 在链表头部添加元素插入到头节点之后 void insertHead(Node *head, int value) { Node *newNode createNode(value); newNode-next head-next; // 新节点指向原来的第一个节点 head-next newNode; // 头节点指向新节点 }思考一下为什么头插法不需要遍历它的时间复杂度是多少4.6 在指定位置插入元素// 在位置 pos从 0 开始插入元素 int insert(Node *head, int pos, int value) { Node *p head; int i 0; // 找到第 pos 个节点的前一个位置 while (p ! NULL i pos) { p p-next; i; } if (p NULL) { printf(插入位置不合法\n); return 0; } Node *newNode createNode(value); newNode-next p-next; // 新节点指向原 pos 位置的节点 p-next newNode; // 前一个节点指向新节点 return 1; }4.7 删除指定位置的元素// 删除位置 pos 的元素 int delete(Node *head, int pos) { Node *p head; int i 0; // 找到要删除节点的前一个节点 while (p-next ! NULL i pos) { p p-next; i; } if (p-next NULL) { printf(删除位置不合法\n); return 0; } Node *temp p-next; // temp 是要删除的节点 p-next temp-next; // 让前一个节点指向要删除节点的后一个 free(temp); // 释放被删除节点的内存 return 1; }4.8 查找元素// 按值查找返回节点地址找不到返回 NULL Node* find(Node *head, int value) { Node *p head-next; // 从第一个实际节点开始 while (p ! NULL) { if (p-data value) { return p; } p p-next; } return NULL; }4.9 遍历输出链表// 打印链表 void printList(Node *head) { Node *p head-next; printf(链表); while (p ! NULL) { printf(%d, p-data); if (p-next ! NULL) printf( - ); p p-next; } printf( - NULL\n); }4.10 释放整个链表// 销毁链表释放所有节点内存 void destroyList(Node *head) { Node *p head; while (p ! NULL) { Node *temp p; p p-next; free(temp); } }五、完整测试代码#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* createNode(int value) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data value; newNode-next NULL; return newNode; } Node* initList() { Node *head (Node*)malloc(sizeof(Node)); head-next NULL; return head; } void append(Node *head, int value) { Node *newNode createNode(value); Node *p head; while (p-next ! NULL) p p-next; p-next newNode; } void insertHead(Node *head, int value) { Node *newNode createNode(value); newNode-next head-next; head-next newNode; } void printList(Node *head) { Node *p head-next; printf(链表); while (p ! NULL) { printf(%d, p-data); if (p-next ! NULL) printf( - ); p p-next; } printf( - NULL\n); } void destroyList(Node *head) { Node *p head; while (p ! NULL) { Node *temp p; p p-next; free(temp); } } int main() { Node *list initList(); // 尾插法10 - 20 - 30 append(list, 10); append(list, 20); append(list, 30); printList(list); // 头插法在头部插入 5 insertHead(list, 5); printList(list); // 5 - 10 - 20 - 30 destroyList(list); return 0; }六、顺序表 vs 单链表终极对比对比维度顺序表单链表存储结构连续内存物理相邻离散内存指针连接随机访问O(1)直接通过下标访问O(n)必须从头遍历插入/删除O(n)需要移动大量元素O(n) 查找 O(1) 修改指针扩容需重新分配更大数组拷贝数据动态申请节点无需扩容空间开销可能预分配过多造成浪费每个节点额外消耗一个指针的空间适用场景查询多、增删少增删频繁、数据量不确定七、小结要点内容核心思想用指针将离散的节点串联起来逻辑上保持线性关系关键操作插入和删除只需修改指针无需移动元素代价失去了随机访问能力需要额外空间存储指针与顺序表的关系两者都是线性表只是存储方式不同互为补充一句话记忆顺序表是“数组思维”靠位置找数据单链表是“接力思维”靠指针找下一个。希望这篇博客能帮你理解单链表的本质如果有疑问欢迎随时交流。