go 链表 （标准库实现）

Go 链表简介Go 标准库里没有单链表只在 container/list 包里提供了双向循环链表。两个核心类型list.List 链表本身包含哨兵节点和长度list.Element 链表节点存数据 前后指针type Element struct { Value interface{} // 节点数据 (任意类型) // next, prev 是私有字段不能直接访问 }特点• 双向每个节点有 Next() 和 Prev()支持双向遍历• 循环内部用一个哨兵节点串成环首尾相连所以代码里没有 nil 判断的边界 case操作非常简洁• Value 是 interface{}可以存任意类型但取出来要类型断言e.Value.(int)• Len() 是 O(1)内部维护了计数不需要遍历常用方法速查遍历模板package main import ( container/list fmt ) func main() { // 创建一个新的链表 l : list.New() // 在链表的尾部添加元素 l.PushBack(Go) l.PushBack(is) l.PushBack(awesome) // 在链表的头部添加元素 l.PushFront(Programming) // 遍历链表并打印元素 for e : l.Front(); e ! nil; e e.Next() { fmt.Println(e.Value) } }几个坑1. Value 类型断言e.Value.(int)类型错了会 panic2. 查找是 O(n)链表没有按值查找的 API得自己写循环 → 这就是为什么 LRU 要配一个 map 做索引3. 节点必须先拿到 *list.Element 才能操作Remove / InsertBefore / MoveToFront 都接收节点指针不接收值4. 不要跨链表移动节点l1 的节点别拿去 l2.Remove()行为未定义什么时候用 container/list• ✅ 需要频繁在中间插入/删除且已经持有节点指针LRU 缓存、任务调度队列• ❌ 只是顺序存取 / 随机访问 → 直接用 slicecache 友好性吊打链表99% 的场景用 slice 就够了剩下 1% 才考虑 container/list。LRU 示例package main import ( container/list fmt ) // 实现一个LRU缓存策略缓存满了就淘汰最久没使用的那个 type LRUCache struct { capability int ll *list.List cache map[int]*list.Element } type entry struct { key, value int } func Constructor(capability int) LRUCache { return LRUCache{ capability: capability, ll: list.New(), cache: make(map[int]*list.Element), } } // 存元素如果元素已经存在则更新放到头部 // 如果元素不存在则加到头部然后判断是否溢出。 func(c *LRUCache) Put(key, value int) { if e,ok : c.cache[key]; ok{ e.Value.(*entry).value value c.ll.MoveToFront(e) return } e : c.ll.PushFront(entry{key: key, value: value}) c.cache[key] e if c.ll.Len() c.capability { e : c.ll.Back() delete(c.cache, e.Value.(*entry).key) c.ll.Remove(e) } } // 获取元素如果元素存在放回并放回头部如果不存在返回-1 func(c *LRUCache) Get(key int) int { if e, ok : c.cache[key]; ok { c.ll.MoveToFront(e) return e.Value.(*entry).value } return -1 } func main() { lrucache : Constructor(2) lrucache.Put(1,3) lrucache.Put(1,4) lrucache.Put(2,9) for e:lrucache.ll.Front(); e!nil;ee.Next() { fmt.Println(e.Value.(*entry).value) } }QA1:为什么用指针接收者 c *LRUCache因为方法里要修改 c 的内部状态链表、map用值接收者会改了个寂寞。对比// 值接收者c 是副本改了不影响原对象 func (c LRUCache) Put(...) { c.ll.PushFront(...) } // 看起来生效了 // 指针接收者c 指向原对象改的就是它本身 func (c *LRUCache) Put(...) { c.ll.PushFront(...) } // ✅ 真正生效⚠️ 有个细节ll 本身是 *list.List指针所以值接收者下 PushFront居然也看似能改链表——因为副本和原对象共享同一个底层链表。但 capacity 这种字段就改不动了而且 map 操作也会出问题。不要依赖这种巧合。Go 的两条经验法则1. 方法里要改字段 → 必须用指针接收者2. 结构体比较大、或包含 mutex/slice/map → 也建议用指针避免拷贝、避免锁失效3. 同一个类型的所有方法接收者类型要统一要么都是值要么都是指针否则方法集混乱、接口实现也容易踩坑LRU 三条全占要改状态、含 map 和 list、需要保持一致 → 必须是 *LRUCache。QA2: *list.List为什么是指针因为list.New()返回指针QA3: *list.Element 为什么这个也是指针呢因为 container/list 里所有方法本来就要求传 *list.Elementmap 存指针只是顺手保持一致避免来回取址。看 list 包的 API 签名func (l *List) PushFront(v any) *list.Element // 返回的就是指针 func (l *List) MoveToFront(e *list .Element) // 接收指针 func (l *List) Remove(e *list.Element) any // 接收指针 func (l *List) InsertBefore(v any, mark *list.Element) // 接收指针Go 标准库设计上链表节点天生就是用指针在传递的。所以elem : c.ll.PushFront(...) // elem 已经是 *list.Element c.cache[key] elem // 直接塞 map类型匹配如果存值类型每次用还得 v自找麻烦。QA4: *list.List不是一个双向链表吗一直next()为什么会出现nil呢container/list 的实现确实是循环双向链表内部有一个哨兵节点root最后一个节点的 next 指向 rootroot 的 next 又指向第一个节点。但是 Next() 和 Prev() 这两个公开方法被故意做了处理当下一个节点是 root 哨兵节点时返回 nil而不是把这个内部节点暴露出来。标准库源码src/container/list/list.gofunc (e *Element) Next() *Element { if p : e.next; e.list ! nil p ! e.list.root { return p } return nil } func (e *Element) Prev() *Element { if p : e.prev; e.list ! nil p ! e.list.root { return p } return nil }关键就是 p ! e.list.root 这个判断——一旦走到 root 哨兵就返回 nil。所以• 内部数据结构循环双向链表用 root 哨兵简化插入/删除的边界判断不需要处理 head/tail 为 nil 的特殊情况。• 对外暴露的迭代接口非循环到末尾返回 nil符合 Go 的习惯写法