链表：绕过，而不是抹除.

上一篇的账单：连续内存给你 O(1) 随机访问和喂饱的 cache，代价是中间增删 O(n) 搬家。链表把这笔账整个反过来——格子不再连续，靠指针相认：增删变成几根指针的改写，搬家消失了；代价同样彻底，随机访问没了，cache 也冷了。这一篇把每个操作拆成节拍，逐根指针看它怎么改。

—节点与链：两格，加一个头.

节点你已经认识——指针篇的两格结构体。整条链表再配一个「头」，和切片头惊人地同构：

type Node struct {
    Val  int
    Next *Node
}
 
type LinkedList struct {
    head *Node
    tail *Node
    len  int
}

对照上一篇：切片头是 ptr/len/cap，链表头是 head/tail/len——都是「两个地址一个计数」。差别全在下面：切片的格子连续，第 i 格算得出来；链表的节点散在内存各处（看图里那三个地址），想到第 i 格，只能走。生产代码会用泛型 Node[T any]，本系列用 int 让图和码严格对齐。

—取数：没有算术，只有旅行.

数组 arr[i] 是一条地址算术；链表的 Get(i) 是一场旅行——从 head 出发跳 i 次：

func (l *LinkedList) Get(index int) *Node {
    if index < 0 || index >= l.len {
        return nil
    }
    cur := l.head
    for i := 0; i < index; i++ {
        cur = cur.Next // 每一步都是一次指针跳跃
    }
    return cur
}

O(n)，而且每一跳都可能落在冷内存上——上一篇实测过这笔账（乱序链表慢 25 倍）。顺带兑现那道对比题：二分在链表上失效，因为 mid 算得出下标、跳不过去。Set(i, v) 就是 Get(i) 加一次赋值，走位的钱一分不少。

—添加三式.

添加的全部秘密：新节点先造好，再改一两根指针。三种位置，三段分镜。

尾插 Append——O(1)，tail 的工资：

头插 Prepend——O(1)，顺序是命：

中插 Insert——走位 O(n)，手术 O(1)，先接后断：

三式合上账：尾插头插 O(1)，是数组给不起的（数组头插要全体搬家）；中插「已定位 O(1)、含定位 O(n)」——这个区分后面反复用。

—删除：绕过，而不是抹除.

删除是链表最出名的一课，也是这个系列图形语言的出生地：

func (l *LinkedList) Remove(index int) *Node {
    if index < 0 || index >= l.len {
        return nil
    }
    if index == 0 {
        return l.Unshift() // 删头 O(1)：head 挪一格
    }
    prev := l.Get(index - 1) // 走位 O(n)
    cur := prev.Next
    prev.Next = cur.Next     // 绕过：手术只有这一步
    cur.Next = nil           // 断开孤儿的引用，帮 GC 一把
    if index == l.len-1 {
        l.tail = prev        // 删的是末尾，tail 回撤
    }
    l.len--
    return cur
}

两个边界各有一句话的命运：删头（Unshift）O(1)——head = head.Next 完事；删尾（Pop）却是 O(n)——tail 能带你到末尾，但删末尾需要的是前驱，单向链里前驱只能从头走过去找。这是单链最著名的不对称，也是下一篇双向链表存在的理由。

哨兵再省一笔：上面每个操作都在特判空链和头部（len == 0、index == 0）。在 head 前面永久挂一个不存数据的哑节点，所有位置就都有了前驱，特判成批消失——空间花一格，if 少一半。标准库的 container/list 就是这么做的（用环形 + 哨兵）。

—反转：三指针体操.

高频题收尾。反转的本质：沿链走一遍，把每根 Next 掉头——难点是掉头的瞬间别把去路弄丢，所以要三个指针分工：

func (l *LinkedList) Reverse() {
    var prev *Node // 反转后的新链头，从 nil 长起
    cur := l.head
    l.head, l.tail = l.tail, l.head // 头尾先对调
    for cur != nil {
        next := cur.Next // ① 先记住去路
        cur.Next = prev  // ② 当前节点掉头
        prev = cur       // ③ prev 跟上
        cur = next       // ④ cur 沿旧路前进
    }
}

prev/cur/next 三个名字你现在都能一眼看穿——三个存着地址的变量而已。这套「先记住去路，再动手改写」的指针体操后面还会重演：平衡树的旋转就是它的树上版本，一样得先把要覆盖的那根指针存下来。

—账本：数组 vs 链表.

两篇的账合到一张表上（默认单链、带 tail）：

诚实的结论：链表赢的只有一件事——在你已经握着节点的地方，O(1) 摘挂。定位还是 O(n)，扫描还吃 cache 亏，所以现代工程默认切片。但「O(1) 摘挂」恰恰是某些场景的命门：LRU 缓存要把任意命中的条目瞬间挪到队首——哈希表负责「一步找到」，链表负责「一步摘挂」，两个结构各出所长（双向链表与哈希表篇会师）。

指针的第一场实战打完。下一篇给每个节点再加一根 Prev，看看多一格指针能买回什么——《双向与环形链表》，即将上线。