C 语言链表 · 学习笔记
从节点结构到指针操作，从单向到双向循环——一份随手可查的链表参考
节点结构 —— 自引用结构体
链表的核心是一个包含指向自身类型指针的结构体。只要有 struct Xxx* next 这个字段，它就是链表节点——叫 Node、Student、Task 都一样。
节点定义
typedef struct Node { int data; /* 数据域 */ struct Node* next; /* 指针域 —— 串起节点的"链条" */ } Node;
三个角色要分清：
内存布局 —— 散落在堆上的珍珠
数组元素连续排列在一整块内存中；链表节点散布在堆的各处，全靠 next 指针串联。这就是为什么链表插入删除 O(1) 但随机访问 O(n)。
↖ 节点随意散落，靠指针串联
head = head→next —— 指针前移一位
这是链表最核心的操作：把 head 指针移向下一个节点。每执行一次，head 就往前跨一步。
典型用法：while 循环遍历链表。注意用临时指针 cur 而不是直接用 head——否则遍历完 head 指向 NULL，链表开头就找不到了。
遍历链表
void printList(Node* head) { Node* cur = head; while (cur != NULL) { printf("%d → ", cur->data); cur = cur->next; /* 指针前移 */ } printf("NULL\n"); }
指针基础 —— 链表为什么离不开指针
内存的本质
计算机内存由连续存储单元组成，8 bit = 1 byte，每个 byte 有唯一地址编号——就像小区里每户有门牌号。32 位机器最多寻址 2³² = 4GB。
以 int a = 999 为例，int 占 4 字节，999 的补码是 0000 0011 1110 0111：
链表节点的字段完全一样：data 和 next 按结构体成员顺序依次排列在内存中，next 里存的就是下一个节点的首地址——一个 4 或 8 字节的整数编号。
指针 = 存地址的变量
指针本质
int a = 42; int* pa = &a; /* pa 存的是 a 在内存中的首地址 */ printf("%p", pa); /* → 0x7ffcad3b8f3c */ printf("%d", *pa); /* → 42 解引用：按 int 类型读出值 */
解引用靠指针类型：
类型决定"取多少字节"
int* pi = &a; /* *pi 取 4 字节，按 int 解释 */ char* pc = &a; /* *pc 只取 1 字节（最低字节） */ float* pf = &a; /* *pf 取 4 字节，但按 IEEE 754 浮点数解释 */
链表的 struct Node* next 就是利用这个机制——编译器知道 next 指向的内容按 struct Node 布局解读：前几个字节是 data，后几个字节是 next。
核心关系：每个节点有两个域 —— data（数据） + next（地址编号）。next 存的值恰好是下一个 Node 结构体在内存中的起始位置。指针就这样把散落的节点"串"成了一条链。
基本操作 —— 增 · 删 · 查 · 改
创建节点（malloc）
在堆上申请一个节点
Node* createNode(int value) { Node* n = (Node*)malloc(sizeof(Node)); n->data = value; n->next = NULL; return n; }
头插法 —— 新节点成为新的头
头插（两行搞定）
Node* insertHead(Node* head, int v) { Node* n = createNode(v); n->next = head; /* 新节点指向原头 */ return n; /* 返回新头 */ }
中间插入 —— 顺序千万不能反
⚠ 关键：① 先让新节点接上后方 → ② 再让前方接上新节点。顺序反了后半段链表就丢了。
在 prev 之后插入
void insertAfter(Node* prev, int v) { Node* n = createNode(v); n->next = prev->next; /* ① 先接后方 */ prev->next = n; /* ② 再接前方 */ }
删除节点 —— 别忘了 free！
按值删除（需二级指针）
void deleteByValue(Node** headRef, int key) { Node* cur = *headRef, *prev = NULL; if (cur && cur->data == key) { /* 删的是头 */ *headRef = cur->next; free(cur); return; } while (cur && cur->data != key) { /* 查找 */ prev = cur; cur = cur->next; } if (!cur) return; /* 没找到 */ prev->next = cur->next; /* 跳过被删节点 */ free(cur); /* 释放内存 */ }
尾插法
追加到链表末尾
Node* insertTail(Node* head, int v) { Node* n = createNode(v); if (!head) return n; /* 空表 */ Node* cur = head; while (cur->next) cur = cur->next; /* 找到尾 */ cur->next = n; /* 挂上去 */ return head; }
链表反转 —— 三指针迭代法
用 pre、cur、next 三个指针协作，逐个把每个节点的 next 箭头掰向它的前驱。
↖ 所有箭头方向反转，pre 成为新头
三指针反转
Node* reverse(Node* head) { Node* pre = NULL; Node* cur = head; while (cur) { Node* nxt = cur->next; /* ① 保存下一个 */ cur->next = pre; /* ② 反转箭头 */ pre = cur; /* ③ pre 前移 */ cur = nxt; /* ④ cur 前移 */ } return pre; /* 新头 */ }
链表分类 —— 三个维度，八种组合
单向/双向 × 带头/不带头 × 循环/非循环 = 2 × 2 × 2 = 8 种。
→单向 · 不带头 · 非循环面试高频，最基础的结构
→○单向 · 不带头 · 循环尾节点指回头
H→单向 · 带头 · 非循环头结点统一操作逻辑
H→○单向 · 带头 · 循环
⇄双向 · 不带头 · 非循环可前后遍历
⇄○双向 · 不带头 · 循环
H⇄双向 · 带头 · 非循环
H⇄○双向 · 带头 · 循环最复杂但最好用
双向链表节点
doubly-linked
typedef struct DNode { int data; struct DNode* prev; /* 前驱 */ struct DNode* next; /* 后继 */ } DNode;
删除时不用遍历找前驱，效率更高。
快慢指针判环
detect-cycle
bool hasCycle(Node* head) { Node* s = head, *f = head; while (f && f->next) { s = s->next; /* 慢: 1步 */ f = f->next->next; /* 快: 2步 */ if (s == f) return true; } return false; }
相遇则有环，找入环点：一个指针回头，同速走，再次相遇处即入口。
链表 vs 数组
| 对比维度 | 链表 | 数组 |
|---|---|---|
| 内存分布 | 不连续，堆上逐个分配 | 连续，一整块 |
| 随机访问 | O(n) 只能顺序遍历 | O(1) a[i] |
| 头部插入/删除 | O(1) | O(n) 移动所有元素 |
| 中间插入/删除 | O(1)（已知位置时） | O(n) 移动后续元素 |
| 扩容 | 随时 malloc，无拷贝 | realloc + 拷贝 |
| 额外内存 | 每节点多存 1~2 个指针 | 无 |
| 缓存友好 | 差（cache miss 多） | 好（连续存储） |
多级指针 & void 指针在链表中的角色
改 head 必须用二级指针（Node**）
C 语言函数传参是值传递。传一级指针只能改指针指向的内容，不能改指针本身。要改 head 本身，必须传 head 的地址——二级指针。
✗ 错误
void delHead(Node* head) { head = head->next; /* 改的是局部变量！main 里的 head 不变 */ }
✓ 正确
void delHead(Node** hr) { *hr = (*hr)->next; /* 改的是 main 里的 head */ } /* 调用: delHead(&head); */
多级指针：快递柜模型
根本没有"多级指针"这种东西——指针就是指针。同一块内存，存实际内容就叫变量，存别人地址就叫指针。
二级指针代码
int a = 42; /* 变量 */ int* pa = &a; /* 一级指针：存 a 的地址 */ int** ppa = &pa; /* 二级指针：存 pa 的地址 */ /* 关系：ppa → pa → a(42) */
void 指针 —— 泛型链表的基石
通用节点
typedef struct GNode { void* data; /* 可指向 int / float / 任何类型 */ struct GNode* next; } GNode; int x = 42; float y = 3.14; GNode* n1 = makeNode(&x); /* data → int */ GNode* n2 = makeNode(&y); /* data → float */
不能直接解引用 void*：编译器不知道它指向什么类型。使用前必须转回来：
*(int*)node->data。
数组名 ≠ 指针（虽然长得像）
关键区别
int arr[10]; int* p = arr; printf("%zu", sizeof(arr)); /* 40 —— 整个数组 */ printf("%zu", sizeof(p)); /* 4 或 8 —— 指针本身 */
数组名在 sizeof 下表现的是整个数组的长度，编译器在编译期就知道。链表只有一个 head 指针，编译器无从得知链表有多长。
typedef · typeof · 结构体内存布局
typedef —— 起别名
给结构体起短名
typedef struct Student { char name[20]; int score; struct Student* next; /* 自引用 → 链表标志 */ } Student; Student* head = NULL; /* 不用写 struct */
有自引用指针就是链表节点，叫什么名字无关紧要。
typeof —— 取类型
GCC 扩展，泛型宏
#define SWAP(a, b) do { \ typeof(a) t = a; \ a = b; b = t; \ } while(0) int x=1,y=2; double p=1.5,q=2.5; SWAP(x,y); /* typeof(a)→int */ SWAP(p,q); /* typeof(a)→double */
非标准 C，编译器扩展。与链表本身无关。
结构体指针的本质：基地址 + 偏移量
链表节点的 cur→data 和 cur→next 底层都是这样工作的：
链表的根本：next 只是结构体尾部的一个字段，存的是下一个同类结构体的首地址——仅此而已。
常见错误 & 注意事项
- 插入顺序不能颠倒：先接后方，再接前方。反了会丢后半段。
- 删除后要 free：只改指针不释放 = 内存泄漏。
- 改头指针用二级指针：要在函数内改 head，参数必须是 Node**。
- 遍历用临时指针：别直接用 head 遍历——走完 head 指向 NULL，链表开头就没了。
- 带头结点统一操作：有了头结点，首元结点的插入删除不再需要特殊处理。
- 画图：链表操作最直观的理解方式——纸笔画出每个指针的指向变化。
- 避免指针越界访问：对 short* 解引用成 float 会读到脏数据；写入则可能 coredump。类型必须匹配。
- void* 不能直接解引用：必须先强转回原类型。
- 数组名 ≠ 指针：sizeof(arr) 是整个数组大小，sizeof(ptr) 永远只是指针本身大小。
- NULL 是链表的终点：while (cur != NULL) 就是在防止越界——NULL 标志链表的边界。