Go 语言标准库 —— container/list 包（双向链表）

🔹 概述

container/list 包实现了双向链表的数据结构。

主要功能：

• 双向链表操作
• O(1) 时间复杂度的插入和删除
• 支持在任意位置插入/删除元素
• 可以存储任意类型的元素

重要说明：

• list 是一个通用的双向链表实现
• 不是并发安全的
• 元素类型为 interface{}（可以存储任意类型）
• 每个元素包含指向前后元素的指针
• 链表本身包含指向头尾的指针

链表的特性：

• 双向链表（每个节点有 prev 和 next 指针）
• 环形结构（尾节点的 next 指向头，头节点的 prev 指向尾）
• 支持 O(1) 时间复杂度的头尾操作
• 支持 O(1) 时间复杂度的任意位置插入/删除（已知位置）
• 不支持随机访问（需要遍历）

应用场景：

• LRU 缓存
• 浏览器历史记录
• 撤销/重做功能
• 任务队列
• 需要频繁插入删除的场景

🔹 核心类型

Element 元素类型

list.Element struct

• 说明：

  • 链表中的节点元素
  • 包含数据、前驱节点、后继节点的引用
  • 属于某个 List

• 字段：

  type Element struct {
      Value interface{} // 元素存储的值
      // 以下是内部字段，不应直接访问
      next *Element
      prev *Element
      list *List
  }
  

• 常用方法：

  • Next 方法

    • 说明：返回下一个元素
    • 方法：Next() *Element
    • 返回值：
      • 如果当前是尾元素，返回 nil
    • 示例：

      e := list.Front()
      for e != nil {
          fmt.Println(e.Value)
          e = e.Next()
      }
      

  • Prev 方法

    • 说明：返回前一个元素
    • 方法：Prev() *Element
    • 返回值：
      • 如果当前是头元素，返回 nil
    • 示例：

      e := list.Back()
      for e != nil {
          fmt.Println(e.Value)
          e = e.Prev()
      }
      

List 链表类型

list.List struct

• 说明：

  • 双向链表结构
  • 包含指向头尾元素的指针
  • 记录链表长度

• 字段：

  type List struct {
      root Element // 哨兵节点
      len  int      // 链表长度
  }
  

• 常用方法详解

  • Len 方法

    • 说明：返回链表的长度（元素个数）
    • 方法：Len() int
    • 时间复杂度：O(1)
    • 示例：

      list := list.New()
      fmt.Println(list.Len()) // 0
      
      list.PushBack(1)
      list.PushBack(2)
      fmt.Println(list.Len()) // 2
      

  • Front 方法

    • 说明：返回链表的头元素
    • 方法：Front() *Element
    • 返回值：
      • 如果链表为空，返回 nil
    • 时间复杂度：O(1)
    • 示例：

      list := list.New()
      list.PushBack(1)
      list.PushBack(2)
      
      front := list.Front()
      fmt.Println(front.Value) // 1
      

  • Back 方法

    • 说明：返回链表的尾元素
    • 方法：Back() *Element
    • 返回值：
      • 如果链表为空，返回 nil
    • 时间复杂度：O(1)
    • 示例：

      list := list.New()
      list.PushBack(1)
      list.PushBack(2)
      
      back := list.Back()
      fmt.Println(back.Value) // 2
      

  • Init 方法

    • 说明：初始化或清空链表
    • 方法：Init() *List
    • 返回值：返回链表本身（支持链式调用）
    • 示例：

      list := list.New()
      list.PushBack(1)
      list.PushBack(2)
      
      list.Init() // 清空链表
      fmt.Println(list.Len()) // 0
      

  • NewList 函数

    • 说明：创建并初始化新的链表
    • 函数：NewList() *List
    • 示例：

      list := list.NewList()
      

🔹 元素操作

在头部插入

list.PushFront(v interface{}) *Element

• 说明：

  • 在链表头部插入新元素
  • 返回新插入的元素

• 参数：

  • v interface{} - 要插入的值

• 返回值：

  • *Element - 新插入的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  e1 := list.PushFront(1)
  e2 := list.PushFront(2)
  e3 := list.PushFront(3)
  
  // 链表：3 -> 2 -> 1
  fmt.Println(list.Front().Value) // 3
  

在尾部插入

list.PushBack(v interface{}) *Element

• 说明：

  • 在链表尾部插入新元素
  • 返回新插入的元素

• 参数：

  • v interface{} - 要插入的值

• 返回值：

  • *Element - 新插入的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  list.PushBack(1)
  list.PushBack(2)
  list.PushBack(3)
  
  // 链表：1 -> 2 -> 3
  fmt.Println(list.Back().Value) // 3
  

在元素前插入

list.InsertBefore(v interface{}, mark *Element) *Element

• 说明：

  • 在指定元素 mark 之前插入新元素
  • 如果 mark 不在链表中，行为未定义

• 参数：

  • v interface{} - 要插入的值
  • mark *Element - 参考元素

• 返回值：

  • *Element - 新插入的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  e1 := list.PushBack(1)
  e2 := list.PushBack(3)
  
  // 在 e2 之前插入 2
  list.InsertBefore(2, e2)
  
  // 链表：1 -> 2 -> 3
  

在元素后插入

list.InsertAfter(v interface{}, mark *Element) *Element

• 说明：

  • 在指定元素 mark 之后插入新元素
  • 如果 mark 不在链表中，行为未定义

• 参数：

  • v interface{} - 要插入的值
  • mark *Element - 参考元素

• 返回值：

  • *Element - 新插入的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  e1 := list.PushBack(1)
  e2 := list.PushBack(3)
  
  // 在 e1 之后插入 2
  list.InsertAfter(2, e1)
  
  // 链表：1 -> 2 -> 3
  

移动元素到头部

list.MoveToFront(e *Element)

• 说明：

  • 将元素 e 移动到链表头部
  • 如果 e 不在链表中，行为未定义

• 参数：

  • e *Element - 要移动的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  list.PushBack(1)
  e := list.PushBack(2)
  list.PushBack(3)
  
  // 移动 2 到头部
  list.MoveToFront(e)
  
  // 链表：2 -> 1 -> 3
  

移动元素到尾部

list.MoveToBack(e *Element)

• 说明：

  • 将元素 e 移动到链表尾部
  • 如果 e 不在链表中，行为未定义

• 参数：

  • e *Element - 要移动的元素

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  e := list.PushBack(1)
  list.PushBack(2)
  list.PushBack(3)
  
  // 移动 1 到尾部
  list.MoveToBack(e)
  
  // 链表：2 -> 3 -> 1
  

删除元素

list.Remove(e *Element) interface{}

• 说明：

  • 删除元素 e 并返回其值
  • 如果 e 不在链表中，行为未定义

• 参数：

  • e *Element - 要删除的元素

• 返回值：

  • interface{} - 被删除元素的值

• 时间复杂度：O(1)

• 示例：

  list := list.New()
  e := list.PushBack(1)
  list.PushBack(2)
  list.PushBack(3)
  
  // 删除元素 e
  value := list.Remove(e)
  fmt.Println(value) // 1
  
  // 链表：2 -> 3
  

🔹 遍历操作

从头到尾遍历

package main

import (
	"container/list"
	"fmt"
)

func main() {
	list := list.New()
	list.PushBack(1)
	list.PushBack(2)
	list.PushBack(3)

	// 从头到尾遍历
	for e := list.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
	// 输出：1 2 3
}

从尾到头遍历

package main

import (
	"container/list"
	"fmt"
)

func main() {
	list := list.New()
	list.PushBack(1)
	list.PushBack(2)
	list.PushBack(3)

	// 从尾到头遍历
	for e := list.Back(); e != nil; e = e.Prev() {
		fmt.Println(e.Value)
	}
	// 输出：3 2 1
}

使用 range 遍历（Go 1.23+）

package main

import (
	"container/list"
	"fmt"
)

func main() {
	list := list.New()
	list.PushBack(1)
	list.PushBack(2)
	list.PushBack(3)

	// 注意：list 不支持 range 遍历
	// 需要使用 for 循环遍历
	for e := list.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

🔹 使用场景

1. LRU 缓存

package main

import (
	"container/list"
	"fmt"
)

// LRUCache 实现简单的 LRU 缓存
type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type entry struct {
	key   int
	value int
}

func NewLRUCache(capacity int) *LRUCache {
	return &LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

func (c *LRUCache) Get(key int) int {
	if elem, ok := c.cache[key]; ok {
		// 移动到头部（最近使用）
		c.list.MoveToFront(elem)
		return elem.Value.(*entry).value
	}
	return -1
}

func (c *LRUCache) Put(key int, value int) {
	if elem, ok := c.cache[key]; ok {
		// 更新值并移动到头部
		c.list.MoveToFront(elem)
		elem.Value.(*entry).value = value
		return
	}

	// 插入新元素到头部
	elem := c.list.PushFront(&entry{key, value})
	c.cache[key] = elem

	// 如果超出容量，删除尾部的元素
	if c.list.Len() > c.capacity {
		last := c.list.Back()
		c.list.Remove(last)
		delete(c.cache, last.Value.(*entry).key)
	}
}

func main() {
	cache := NewLRUCache(2)

	cache.Put(1, 10)
	cache.Put(2, 20)
	fmt.Println(cache.Get(1)) // 10

	cache.Put(3, 30) // 淘汰 key=2
	fmt.Println(cache.Get(2)) // -1（不存在）
	fmt.Println(cache.Get(3)) // 30
}

2. 浏览器历史记录

package main

import (
	"container/list"
	"fmt"
)

// BrowserHistory 实现浏览器历史记录
type BrowserHistory struct {
	history *list.List
	current *list.Element
}

func NewBrowserHistory() *BrowserHistory {
	return &BrowserHistory{
		history: list.New(),
	}
}

func (b *BrowserHistory) Visit(url string) {
	// 删除当前页面之后的所有历史记录
	for b.current != nil && b.current.Next() != nil {
		b.history.Remove(b.current.Next())
	}

	// 添加新页面
	b.current = b.history.PushBack(url)
}

func (b *BrowserHistory) Back(steps int) string {
	for i := 0; i < steps && b.current != nil && b.current.Prev() != nil; i++ {
		b.current = b.current.Prev()
	}

	if b.current == nil {
		return ""
	}
	return b.current.Value.(string)
}

func (b *BrowserHistory) Forward(steps int) string {
	for i := 0; i < steps && b.current != nil && b.current.Next() != nil; i++ {
		b.current = b.current.Next()
	}

	if b.current == nil {
		return ""
	}
	return b.current.Value.(string)
}

func main() {
	browser := NewBrowserHistory()

	browser.Visit("https://google.com")
	browser.Visit("https://github.com")
	browser.Visit("https://stackoverflow.com")

	fmt.Println(browser.Back(1))      // https://github.com
	fmt.Println(browser.Back(1))      // https://google.com
	fmt.Println(browser.Forward(1))   // https://github.com
}

3. 撤销/重做功能

package main

import (
	"container/list"
	"fmt"
)

// Editor 实现编辑器的撤销/重做功能
type Editor struct {
	undoStack *list.List
	redoStack *list.List
	content   string
}

func NewEditor() *Editor {
	return &Editor{
		undoStack: list.New(),
		redoStack: list.New(),
		content:   "",
	}
}

func (e *Editor) Type(text string) {
	// 保存当前状态到撤销栈
	e.undoStack.PushBack(e.content)
	// 清空重做栈
	e.redoStack.Init()
	// 更新内容
	e.content += text
}

func (e *Editor) Undo() string {
	if e.undoStack.Len() == 0 {
		return e.content
	}

	// 保存当前状态到重做栈
	e.redoStack.PushBack(e.content)
	// 恢复到上一个状态
	last := e.undoStack.Back()
	e.content = last.Value.(string)
	e.undoStack.Remove(last)

	return e.content
}

func (e *Editor) Redo() string {
	if e.redoStack.Len() == 0 {
		return e.content
	}

	// 保存当前状态到撤销栈
	e.undoStack.PushBack(e.content)
	// 恢复到下一个状态
	last := e.redoStack.Back()
	e.content = last.Value.(string)
	e.redoStack.Remove(last)

	return e.content
}

func main() {
	editor := NewEditor()

	editor.Type("Hello")
	editor.Type(" World")
	fmt.Println(editor.content) // Hello World

	fmt.Println(editor.Undo())  // Hello
	fmt.Println(editor.Undo())  // ""

	fmt.Println(editor.Redo()) // Hello
	fmt.Println(editor.Redo()) // Hello World
}

4. 任务队列

package main

import (
	"container/list"
	"fmt"
	"sync"
)

// TaskQueue 实现任务队列
type TaskQueue struct {
	mu    sync.Mutex
	queue *list.List
}

type Task struct {
	ID   int
	Name string
}

func NewTaskQueue() *TaskQueue {
	return &TaskQueue{
		queue: list.New(),
	}
}

func (q *TaskQueue) Enqueue(task Task) {
	q.mu.Lock()
	defer q.mu.Unlock()
	q.queue.PushBack(task)
}

func (q *TaskQueue) Dequeue() *Task {
	q.mu.Lock()
	defer q.mu.Unlock()

	if q.queue.Len() == 0 {
		return nil
	}

	elem := q.queue.Front()
	task := elem.Value.(Task)
	q.queue.Remove(elem)
	return &task
}

func (q *TaskQueue) Len() int {
	q.mu.Lock()
	defer q.mu.Unlock()
	return q.queue.Len()
}

func main() {
	queue := NewTaskQueue()

	// 添加任务
	queue.Enqueue(Task{ID: 1, Name: "任务 1"})
	queue.Enqueue(Task{ID: 2, Name: "任务 2"})
	queue.Enqueue(Task{ID: 3, Name: "任务 3"})

	// 处理任务
	for queue.Len() > 0 {
		task := queue.Dequeue()
		fmt.Printf("处理：%s\n", task.Name)
	}
}

5. 滑动窗口

package main

import (
	"container/list"
	"fmt"
)

// SlidingWindow 实现滑动窗口
type SlidingWindow struct {
	window   *list.List
	maxSize  int
}

func NewSlidingWindow(size int) *SlidingWindow {
	return &SlidingWindow{
		window:  list.New(),
		maxSize: size,
	}
}

func (w *SlidingWindow) Add(value int) {
	// 如果窗口已满，移除最旧的元素
	if w.window.Len() >= w.maxSize {
		w.window.Remove(w.window.Front())
	}
	w.window.PushBack(value)
}

func (w *SlidingWindow) GetValues() []int {
	values := make([]int, 0, w.window.Len())
	for e := w.window.Front(); e != nil; e = e.Next() {
		values = append(values, e.Value.(int))
	}
	return values
}

func (w *SlidingWindow) Average() float64 {
	if w.window.Len() == 0 {
		return 0
	}

	sum := 0
	for e := w.window.Front(); e != nil; e = e.Next() {
		sum += e.Value.(int)
	}
	return float64(sum) / float64(w.window.Len())
}

func main() {
	window := NewSlidingWindow(3)

	window.Add(1)
	window.Add(2)
	window.Add(3)
	fmt.Printf("窗口：%v, 平均：%.2f\n", window.GetValues(), window.Average())

	window.Add(4) // 移除 1
	fmt.Printf("窗口：%v, 平均：%.2f\n", window.GetValues(), window.Average())

	window.Add(5) // 移除 2
	fmt.Printf("窗口：%v, 平均：%.2f\n", window.GetValues(), window.Average())
}

🔹 注意事项和最佳实践

1. 类型断言

• ⚠️ list 存储的是 interface{} 类型
• ✅ 取出元素时必须进行类型断言
• ⚠️ 类型断言可能 panic，建议使用 comma-ok 形式

// 不安全
value := element.Value.(int)

// 安全
if value, ok := element.Value.(int); ok {
	fmt.Println(value)
}

2. 并发安全

• ⚠️ list 不是并发安全的
• ✅ 多线程环境需要加锁

type SafeList struct {
	mu   sync.RWMutex
	list *list.List
}

func (sl *SafeList) PushBack(v interface{}) {
	sl.mu.Lock()
	defer sl.mu.Unlock()
	sl.list.PushBack(v)
}

func (sl *SafeList) Front() *list.Element {
	sl.mu.RLock()
	defer sl.mu.RUnlock()
	return sl.list.Front()
}

3. 内存管理

• ✅ 及时删除不需要的元素
• ✅ 清空链表使用 Init()

list.Init() // 清空链表

4. 性能考虑

• ✅ 头尾操作：O(1)
• ✅ 已知位置的插入/删除：O(1)
• ⚠️ 查找元素：O(n)
• ⚠️ 随机访问：不支持

🔹 与其他数据结构的对比

List vs Slice

选择指南

使用 List：

• ✅ 需要频繁在头尾插入/删除
• ✅ 需要 O(1) 时间复杂度的插入/删除
• ✅ 实现 LRU 缓存、队列等

使用 Slice：

• ✅ 需要随机访问
• ✅ 需要类型安全（使用泛型）
• ✅ 内存敏感
• ✅ 需要缓存友好

🔥 总结

核心类型

核心方法

主要特点

• 双向链表 👉 每个节点有 prev 和 next 指针
• 环形结构 👉 尾节点的 next 指向头
• O(1) 操作 👉 头尾插入/删除
• 任意类型 👉 存储 interface{}

使用场景

• LRU 缓存 👉 最近最少使用淘汰
• 浏览器历史 👉 前进/后退功能
• 撤销/重做 👉 编辑器功能
• 任务队列 👉 FIFO 队列
• 滑动窗口 👉 固定大小窗口

最佳实践

• ✅ 使用类型断言时检查类型
• ✅ 并发环境加锁保护
• ✅ 及时清理不需要的元素
• ✅ 根据场景选择合适的数据结构
• ⚠️ 注意：不支持随机访问

性能提示

• 头尾操作 👉 O(1)
• 已知位置插入/删除 👉 O(1)
• 查找元素 👉 O(n)
• 随机访问 👉 不支持

container/list 包提供了高效的双向链表实现，适合需要频繁插入删除的场景！