线性表
线性表的两大经典实现：顺序表、链表
顺序表
（比如 C 里的数组
int arr[]
元素存在连续的内存中。
优点：随机访问快，arr[i] O(1)。
缺点：插入/删除慢（要挪动一堆数据），扩容麻烦。
链表
（比如单链表）
元素用节点存，每个节点带个 next 指针。
优点：插入/删除快（只改指针），灵活分配内存。
缺点：访问第 k 个元素必须从头数，O(n)。
📌 单链表操作总结（带头指针、可选尾指针）
| 操作 | 是否需要遍历？ | 说明 |
|---|---|---|
| 新增头结点 | ❌ O(1) | 新节点 next = head; head = 新节点 |
| 删除头结点 | ❌ O(1) | head = head->next |
| 新增尾结点（有尾指针） | ❌ O(1) | tail->next = 新节点; tail = 新节点 |
| 新增尾结点（无尾指针） | ✅ O(n) | 得从头走到尾再接上 |
| 删除尾结点（有尾指针） | ✅ O(n) | 要找到“倒数第二个节点”，才能改 tail(尾节点) |
| 删除尾结点（无尾指针） | ✅ O(n) | 同理，还得遍历 |
| 在中间插入节点（已知前驱） | ❌ O(1) | p->next = 新节点; 新节点->next = 原next |
| 在中间删除节点（已知前驱） | ❌ O(1) | p->next = p->next->next |
- 新增一个头结点通常只需要在链表的开始处插入一个新节点，并将它的next指针指向原链表的头结点。这个过程并不需要遍历整个链表。
- 新增一个尾结点通常意味着需要找到链表的最后一个节点，并将新节点的next指针设置为null（或对应语言中的空值），同时更新原链表的最后一个节点的next指针以指向新节点。但是，如果链表有一个指向尾部的指针（比如双向链表或某些特定设计的单链表），那么就不需要遍历整个链表来找到尾结点。
❓“有尾指针了，倒数第二个节点是不是也能直接找到？”
👉 答案是：不能。
为什么呢？
-
尾指针（tail）：只存了“最后一个节点”的地址。
head → [1] → [2] → [3] → [4] → NULL ↑ tail
📌 删除尾结点对比
| 链表类型 | 能不能直接删尾？ | 复杂度 | 原因 |
|---|---|---|---|
| 单链表 (Singly Linked List) | ❌ 不行 | O(n) | 有 tail 只能找到最后一个，但找不到倒数第二个（前驱节点），必须从头遍历 |
| 双向链表 (Doubly Linked List) | ✅ 可以 | O(1) | 有 tail，且每个节点有 prev 指针，能一步找到倒数第二个节点 |
| 循环链表 (Circular Linked List) | 取决于单/双 | 单向循环：O(n) 双向循环：O(1) | 循环只是头尾相连，不改变“是否能回退”的本质；单向还是要遍历，双向能一步删掉 |
📌 动态小图理解
单链表（单向 + 尾指针）：
head → [1] → [2] → [3] → [4] → NULL
↑
tail
要删 [4]，必须遍历找到 [3]。
痛点：不能倒着走。
双向链表（有 prev 指针）：
head ↔ [1] ↔ [2] ↔ [3] ↔ [4]
↑
tail
要删 [4]，直接 tail = tail.prev; tail.next = NULL;
一步到位，O(1)。
循环链表（头尾相连）：
- 单向循环：
head → [1] → [2] → [3] → [4] -
↑-----------------------|
要删 [4]，还是得找到 [3] → O(n)。
双向循环：
head ↔ [1] ↔ [2] ↔ [3] ↔ [4]
↑-------------------------↓
要删 [4]，tail = tail.prev; 就行 → O(1)。
🎯 总结口诀
👉 “单链表尾删必遍历，双向链表一箭毙，循环不改单双性。”