链表
链表用独立节点保存数据，每个节点包含值和指向后继的 next。头插只需改写指针，时间为 O(1)；访问索引、搜索或定位任意插入位置，则要从 head 沿链前进，最坏为 O(n)。
每个节点像一条线索：保存当前值，也告诉你下一站。不能直接跳到第五个节点，必须先经过前四个；找到插入位置后，只需接好两条指针。
链表如何工作
本课是单链表。Node 包含 value、next；LinkedList 只保存入口 head，没有 tail。因此 insert_tail 每次都遍历到末尾。
insert_head(v) 先让新节点的 next 指向旧头，再把 head 改为新节点，两次写入，不遍历。insert_at(k, v) 先到索引 k − 1，再依次执行 newNode.next = curr.next、curr.next = newNode。顺序不能颠倒，动画将两次写入分开显示。
delete(v) 先检查头节点。头没有前驱，单独处理只需 O(1)。否则让 curr 前进，但检查的是 curr.next.value。找到目标时，curr 已位于前驱，可执行 curr.next = curr.next.next 跳过目标。search(v) 则逐个比较，返回索引，找不到返回 -1。
容量滑块为 4–10，默认 7，这是画布限制，代码用 max 对应限制。链表结构本身没有固定容量，可按可用内存增长。
逐步演示
从空链表开始，在输入面板运行：
- 头插 5：新节点的
next指向∅，再让head指向它。得到5 → ∅。 - 头插 8：
8.next指向旧头 5，head改为 8。得到8 → 5 → ∅。 - 尾插 3：
curr从索引 0 的 8 走到索引 1 的 5。看到5.next = ∅后停止，将3.next = ∅，再让5.next指向 3。得到8 → 5 → 3 → ∅。 - 索引 1 插入 7：前驱位于索引 0。先
7.next = 8.next，指向 5，再8.next = 7。得到8 → 7 → 5 → 3 → ∅。 - 搜索 5：索引 0 比较
8 ≠ 5，索引 1 比较7 ≠ 5，索引 2 比较5 = 5，返回 2。 - 删除 5：头检查
8 ≠ 5。curr在索引 0 看后继 7，在索引 1 看后继 5。命中后让7.next跳过 5 指向 3，得到8 → 7 → 3 → ∅。
画布的 curr 标出比较位置。新节点先悬在插入位置上方，两条指针接好后入列；删除时节点移出，旁路箭头越过它。这些动作对应指针改写的顺序。
时间与空间复杂度
| 操作 | 成本 | 原因 |
|---|---|---|
| 按索引访问 | O(n) | 从 head 沿链前进 |
| 头插 | O(1) | 两次指针写入 |
| 尾插 | O(n) | 本课没有 tail 指针 |
| 索引 k 插入 | O(k) | 找前驱，再用 O(1) 接入 |
| 按值删除 | O(n) | 找目标前驱 |
| 搜索 | O(n) | 逐节点比较 |
| 空间 | O(n) | 每个值一个节点及后继指针 |
维护 tail 可把尾插降为 O(1)。本课保留遍历过程。已知前驱后的接入本身是 O(1)，主要成本在定位。
边界情况
- 空链表插入：头插和尾插都把
head从∅改为唯一节点。 - 空链表删除或搜索：
delete由if not self.head分支返回False；search的while curr一次也不进入循环，返回-1。不抛异常。 - 删除头节点：执行
head = head.next，不遍历。 - 删除不存在的值：
curr.next到达∅后返回False。 - 索引越过末尾：展示的
insert_at(k, v)没有完整越界检查，会沿链走到空引用并出错。可视化会停止并说明原因。k = 0则调用insert_head。
常见错误
- 接入顺序颠倒。 先写
newNode.next = curr.next，再写curr.next = newNode。反过来会覆盖通向后半链的引用，并可能让新节点指向自己。 - 只找目标，不找前驱。 单链表删除需要改前驱的
next，所以循环查看curr.next。 - 循环条件差一位。
while curr.next停在尾节点，适合尾插；搜索用while curr才能检查最后一个节点。混用会漏查或解引用∅。 - 忽略定位与缓存成本。 节点可能散布在内存中，追踪指针不利于缓存。已有位置、经常接入节点时链表才可能有优势；频繁索引访问通常更适合连续数组。