list

container/list 是 Go 标准库中实现双向链表的包，它提供了高效的插入和删除操作，特别适合需要频繁在首尾修改元素的场景。

container/list 作为 Go 标准库中的重要数据结构，为开发者提供了简洁高效的非线程安全双向链表实现。虽然在随机访问方面不如 slice，但在处理需要频繁插入、删除的队列式数据时，其 O(1) 的操作复杂度使其成为无可替代的选择。

特性

list

slice

map

首部插入

O(1)

O(n)

不支持

中间插入

O(1)

O(n)

不支持

随机访问

O(n)

O(1)

内存占用

中等 (每个元素额外16字节)

低

高

元素有序性

保持插入顺序

保持索引顺序

无序

1 Element

// Element 表示双向链表中的一个节点
type Element struct {
    next, prev *Element // 前后节点指针
    list       *List    // 所属链表
    Value      any      // 存储的实际值
}

1.1 func (e Element) Next() Element

功能说明

返回当前元素的下一个元素
如果当前元素是尾元素或者不属于任何链表，则返回 nil

返回值

*Element: 下一个链表节点指针
无错误返回

使用注意事项

空链表调用：当元素不属于任何链表时返回 nil
尾元素处理：尾元素的 Next() 必然返回 nil
并发安全：遍历时可能被其他协程修改，需加锁

package main

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

func main() {
    l := list.New()
    l.PushBack("A")
    l.PushBack("B")
    l.PushBack("C")

    // 获取第一个元素
    first := l.Front()
    
    // 案例1：正常遍历
    fmt.Print("正向遍历: ")
    for e := first; e != nil; e = e.Next() {
        fmt.Printf("%s → ", e.Value)
    }
    // 输出: A → B → C → 
    
    // 案例2：尾元素测试
    last := l.Back()
    if last.Next() == nil {
        fmt.Println("\n尾元素的Next()返回nil") 
    }
    
    // 案例3：孤儿元素测试
    orphan := &list.Element{Value: "Orphan"}
    if orphan.Next() == nil {
        fmt.Println("孤儿元素的Next()返回nil")
    }
    
    // 案例4：并发安全处理
    var wg sync.WaitGroup
    var mu sync.Mutex
    
    wg.Add(1)
    go func() {
        defer wg.Done()
        
        mu.Lock()
        defer mu.Unlock()
        
        // 安全遍历
        for e := l.Front(); e != nil; e = e.Next() {
            fmt.Printf("%s ", e.Value)
        }
    }()
    wg.Wait()
    // 输出: A B C
}

1.2 func (e Element) Prev() Element

功能说明

返回当前元素的前一个元素
如果当前元素是首元素或者不属于任何链表，则返回 nil

返回值

*Element: 前一个链表节点指针
无错误返回

使用注意事项

空链表调用：当元素不属于任何链表时返回 nil
首元素处理：首元素的 Prev() 必然返回 nil
环形链表模拟：当用于环形结构时需手动连接首尾

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack("X")
    l.PushBack("Y")
    l.PushBack("Z")
    
    // 获取最后一个元素
    last := l.Back()
    
    // 案例1：反向遍历
    fmt.Print("反向遍历: ")
    for e := last; e != nil; e = e.Prev() {
        fmt.Printf("%s → ", e.Value)
    }
    // 输出: Z → Y → X → 
    
    // 案例2：首元素测试
    first := l.Front()
    if first.Prev() == nil {
        fmt.Println("\n首元素的Prev()返回nil")
    }
    
    // 案例3：孤儿元素测试
    isolated := &list.Element{Value: "Isolated"}
    if isolated.Prev() == nil {
        fmt.Println("孤儿元素的Prev()返回nil")
    }
    
    // 案例4：手动创建环形链表
    fmt.Println("\n手动环形结构:")
    ringStart := &list.Element{Value: "LoopStart"}
    ringEnd := &list.Element{Value: "LoopEnd"}
    
    // 手动链接节点
    ringStart.next = ringEnd
    ringEnd.prev = ringStart
    ringEnd.next = ringStart // 关键：形成环
    ringStart.prev = ringEnd // 关键：形成环
    
    // 模拟环形遍历
    fmt.Print("环形遍历: ")
    current := ringStart
    for i := 0; i < 4; i++ {
        fmt.Printf("%s → ", current.Value)
        current = current.Prev() // 注意：使用Prev模拟逆时针
    }
    // 输出: LoopStart → LoopEnd → LoopStart → LoopEnd → 
}

2 List

// List 表示一个双向链表
type List struct {
    root Element // 哨兵节点（不存储实际值）
    len  int     // 当前链表长度
}

作用：提供双向链表数据结构实现，支持高效的头尾操作和任意位置插入删除。

2.1 func New() *List

功能：创建并初始化一个新的空链表 返回值：新链表指针

// 创建空链表
emptyList := list.New()
fmt.Println("长度:", emptyList.Len()) // 输出: 0

// 创建带元素的链表
filledList := list.New()
filledList.PushBack("A")
filledList.PushBack("B")
fmt.Printf("首元素: %v, 尾元素: %v\n", 
    filledList.Front().Value, 
    filledList.Back().Value) // 输出: 首元素: A, 尾元素: B

2.2 func (l List) Back() Element

功能：返回链表最后一个元素 返回值：尾元素指针（链表为空时返回 nil） 注意事项：

空链表调用返回 nil
修改尾元素需使用链表方法（如 MoveToBack）

l := list.New()
l.PushBack(10)
l.PushBack(20)

last := l.Back()
fmt.Println("尾元素值:", last.Value) // 输出: 20

// 危险：直接修改可能导致数据不一致
last.Value = 30 // ⚠️ 可直接修改值但不改变链表结构

// 安全移动尾元素
l.MoveToFront(last) // ✅ 使用链表方法操作元素位置
fmt.Println("新尾元素:", l.Back().Value) // 输出: 10

2.3 func (l List) Front() Element

功能：返回链表第一个元素 返回值：首元素指针（链表为空时返回 nil）

l := list.New()
l.PushFront("First")
l.PushFront("NewFirst")

first := l.Front()
fmt.Println("首元素:", first.Value) // 输出: NewFirst

// 当链表为空时
emptyList := list.New()
if emptyList.Front() == nil {
    fmt.Println("空链表没有首元素") // ✅ 正确检测
}

2.4 func (l List) Init() List

功能：重置链表为空状态（O(1)时间） 返回值：当前链表指针（便于链式调用） 注意事项：

不会回收元素内存（可能需手动清空引用）
被移除的元素仍可能被外部引用

l := list.New()
l.PushBack("A")
l.PushBack("B")

// 记录元素用于后续检查
elem := l.Front()

// 清空链表
l.Init() 
fmt.Println("长度:", l.Len()) // 输出: 0

// 危险：外部引用元素已被移出链表
fmt.Println("孤立元素值:", elem.Value) // 输出: A（还能访问值）
elem.Value = nil // ✅ 手动解引用防内存泄漏

2.5 func (l List) InsertAfter(v any, mark Element) *Element

参数：

v：插入的值
mark：参照元素（新元素插入在其后）

返回值：新元素指针（无效操作时返回 nil） 注意事项：

mark 必须属于当前链表
插入位置必须在链表内

l := list.New()
a := l.PushBack("A")
b := l.PushBack("B")

// 正确插入
newElem := l.InsertAfter("C", a)
fmt.Println(a.Next().Value) // 输出: C

// 错误示例1：使用不属于链表的元素
foreignElem := &list.Element{Value: "Foreign"}
if l.InsertAfter("X", foreignElem) == nil {
    fmt.Println("插入失败：无效参照元素") // ✅ 正确处理
}

// 错误示例2：使用已删除的元素
removed := l.Remove(b)
if l.InsertAfter("Y", removed) == nil {
    fmt.Println("插入失败：元素已被移除") // ✅
}

2.6 func (l List) InsertBefore(v any, mark Element) *Element

类似 InsertAfter，但插入在 mark 元素之前

2.7 func (l *List) Len() int

功能：返回链表长度 返回值：当前元素数量（≥0） 特性：复杂度 O(1)

2.8 func (l List) MoveAfter(e, mark Element)

功能：将元素 e 移动到 mark 之后 参数：

e：要移动的元素
mark：目标位置元素

注意事项：

两元素必须属于同一链表
e 和 mark 不能为同一元素
操作后原位置元素自动连接

l := list.New()
elems := []*Element{
    l.PushBack(1),
    l.PushBack(2),
    l.PushBack(3),
}

// 移动元素3到元素1之后
l.MoveAfter(elems[2], elems[0])

// 验证结果
fmt.Println("链表顺序:")
current := l.Front()
for current != nil {
    fmt.Print(current.Value, " ")
    current = current.Next()
}
// 输出: 1 3 2

2.9 func (l List) MoveBefore(e, mark Element)

类似 MoveAfter，但移动到 mark 元素之前

2.10 func (l List) MoveToBack(e Element)

功能：移动元素到链表尾部 注意事项：

元素必须属于当前链表
移动尾元素无实际效果但允许操作

l := list.New()
a := l.PushBack("A")
b := l.PushBack("B")

// 移动首元素到尾部
l.MoveToBack(a)

// 危险：移动不属于链表的元素
foreign := &list.Element{Value: "X"}
l.MoveToBack(foreign) // ⚠️ 会导致panic崩溃！

// 安全检测（推荐实践）
if e.list == l {
    l.MoveToBack(e)
} else {
    fmt.Println("非法元素操作")
}

2.11 func (l List) MoveToFront(e Element)

类似 MoveToBack，但移动到头部

2.12 func (l List) PushBack(v any) Element

功能：尾部添加元素（O(1)） 返回值：新元素指针

l := list.New()

// 连续添加
e1 := l.PushBack("First")
e2 := l.PushBack("Second")

// 结果验证
fmt.Printf("尾元素: %v\n", l.Back().Value)  // Second
fmt.Printf("首元素: %v\n", l.Front().Value) // First

2.13 func (l List) PushBackList(other List)

功能：将另一链表所有元素添加到当前链表尾部 注意事项：

other 链表会被清空（元素移动）
添加后两个链表互不影响

listA := list.New()
listA.PushBack("A1")
listA.PushBack("A2")

listB := list.New()
listB.PushBack("B1")
listB.PushBack("B2")

// 合并链表
listA.PushBackList(listB)

fmt.Println("合并后长度:", listA.Len()) // 4
fmt.Println("listB长度:", listB.Len())    // 0 (已清空)

2.14 func (l List) PushFront(v any) Element

类似 PushBack，但在头部添加

2.15 func (l List) PushFrontList(other List)

类似 PushBackList，但添加到头部

2.16 func (l List) Remove(e Element) any

功能：移除链表中的元素 参数：要移除的元素指针 返回值：被移除元素的值 错误情况：

如果 e 为 nil：panic("list: Remove called on nil Element")
如果 e 不属于当前链表：panic("list: Remove called on element not in list")

注意事项：

移除后该元素不再属于链表
仍可访问该元素的值，但不应再用于链表操作

l := list.New()
elem := l.PushBack("ToRemove")

// 正确移除
removedValue := l.Remove(elem)
fmt.Println("被移除的值:", removedValue)

// 致命错误1：移除空元素
// l.Remove(nil) // 触发panic

// 致命错误2：重复移除相同元素
// l.Remove(elem) // 触发panic (元素已不属于链表)

// 安全移除模式
if elem.list == l {
    value := l.Remove(elem)
    // 安全清理
    elem.Value = nil // 帮助GC
}

操作

时间复杂度

解释

PushFront/PushBack

O(1)

常数时间完成

InsertBefore/After

O(1)

修改指针即可

MoveToFront/Back

O(1)

直接调整指针

Remove

O(1)

解除节点链接

按索引访问

O(n)

需要顺序遍历

查找元素

O(n)

需要顺序遍历

最后更新于22天前

1 Element

1.1 func (e *Element) Next() *Element

1.2 func (e *Element) Prev() *Element

2 List

2.1 func New() *List

2.2 func (l *List) Back() *Element

2.3 func (l *List) Front() *Element

2.4 func (l *List) Init() *List

2.5 func (l *List) InsertAfter(v any, mark *Element) *Element

2.6 func (l *List) InsertBefore(v any, mark *Element) *Element

2.7 func (l *List) Len() int

2.8 func (l *List) MoveAfter(e, mark *Element)

2.9 func (l *List) MoveBefore(e, mark *Element)

2.10 func (l *List) MoveToBack(e *Element)

2.11 func (l *List) MoveToFront(e *Element)

2.12 func (l *List) PushBack(v any) *Element

2.13 func (l *List) PushBackList(other *List)

2.14 func (l *List) PushFront(v any) *Element

2.15 func (l *List) PushFrontList(other *List)

2.16 func (l *List) Remove(e *Element) any

1.1 func (e Element) Next() Element

1.2 func (e Element) Prev() Element

2.2 func (l List) Back() Element

2.3 func (l List) Front() Element

2.4 func (l List) Init() List

2.5 func (l List) InsertAfter(v any, mark Element) *Element

2.6 func (l List) InsertBefore(v any, mark Element) *Element

2.8 func (l List) MoveAfter(e, mark Element)

2.9 func (l List) MoveBefore(e, mark Element)

2.10 func (l List) MoveToBack(e Element)

2.11 func (l List) MoveToFront(e Element)

2.12 func (l List) PushBack(v any) Element

2.13 func (l List) PushBackList(other List)

2.14 func (l List) PushFront(v any) Element

2.15 func (l List) PushFrontList(other List)

2.16 func (l List) Remove(e Element) any