golang中container/list包

Go 标准包container中包含了常用的容器类型 包括
conatiner/list
container/heap
container/ring
本篇介绍 Go标准容器 conatiner/list
conatiner/list实现了一个双向链表 该结构具有链表的所有功能
type Element
type Element struct {
  Value interface{} //在元素中存储的值
}
func (e *Element) Next() *Element  //返回该元素的下一个元素 如果没有下一个元素则返回nil
func (e *Element) Prev() *Element//返回该元素的前一个元素 如果没有前一个元素则返回nil
type List
func New() *List //返回一个初始化的list
func (l *List) Back() *Element //获取list l的最后一个元素
func (l *List) Front() *Element //获取list l的第一个元素
func (l *List) Init() *List  //list l初始化或者清除list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  //在list l中元素mark之后插入一个值为v的元素 并返回该元素 如果mark不是list中元素 则list不改变
func (l *List) InsertBefore(v interface{}, mark *Element) *Element//在list l中元素mark之前插入一个值为v的元素 并返回该元素 如果mark不是list中元素 则list不改变
func (l *List) Len() int //获取list l的长度
func (l *List) MoveAfter(e, mark *Element)  //将元素e移动到元素mark之后 如果元素e或者mark不属于list l 或者e==mark 则list l不改变
func (l *List) MoveBefore(e, mark *Element)//将元素e移动到元素mark之前 如果元素e或者mark不属于list l 或者e==mark 则list l不改变
func (l *List) MoveToBack(e *Element)//将元素e移动到list l的末尾 如果e不属于list l 则list不改变
func (l *List) MoveToFront(e *Element)//将元素e移动到list l的首部 如果e不属于list l 则list不改变
func (l *List) PushBack(v interface{}) *Element//在list l的末尾插入值为v的元素 并返回该元素
func (l *List) PushBackList(other *List)//在list l的尾部插入另外一个list 其中l和other可以相等
func (l *List) PushFront(v interface{}) *Element//在list l的首部插入值为v的元素 并返回该元素
func (l *List) PushFrontList(other *List)//在list l的首部插入另外一个list 其中l和other可以相等
func (l *List) Remove(e *Element) interface{}//如果元素e属于list l 将其从list中删除 并返回元素e的值

conatiner/list用法举例

package main
import (
"container/list"
"fmt"
)
func main() {
    l := list.New() //创建一个新的list
    for i := 0; i < 5; i++ {
        l.PushBack(i)
    }
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出list的值,01234
    }
    fmt.Println("")
    fmt.Println(l.Front().Value) //输出首部元素的值,0
    fmt.Println(l.Back().Value)  //输出尾部元素的值,4
    l.InsertAfter(6, l.Front())  //首部元素之后插入一个值为10的元素
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出list的值,061234
    }
    fmt.Println("")
    l.MoveBefore(l.Front().Next(), l.Front()) //首部两个元素位置互换
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出list的值,601234
    }
    fmt.Println("")
    l.MoveToFront(l.Back()) //将尾部元素移动到首部
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出list的值,460123
    }
    fmt.Println("")
    l2 := list.New()
    l2.PushBackList(l) //将l中元素放在l2的末尾
    for e := l2.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出l2的值,460123
    }
    fmt.Println("")
    l.Init()           //清空l</span>
    fmt.Print(l.Len()) //0
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value) //输出list的值,无内容
    }
}

GO中container/list包 可能的坑

list包 对于e *Element操作的元素 可能导致程序崩溃
原因 e是一个Element类型的指针 也可能为nil
但golang中list包 函数 没有对其进行是否为nil的检查
默认其非nil进行操作 所以 可能出现程序崩溃
例子 Remove 函数
package main
import (
    "container/list"
    "fmt"
)
func main() {
    l := list.New()
    l.PushBack(1)
    fmt.Println(l.Front().Value) //1
    value := l.Remove(l.Front())
    fmt.Println(value)            //1
    value1 := l.Remove(l.Front()) //panic: runtime error: invalid memory address or nil pointer dereference
    fmt.Println(value1)
}
程序崩溃 原因是list中只有1个元素 但是删除2个元素
进一步查看一下原因
golang中Front()函数实现
func (l *List) Front() *Element {
    if l.len == 0 {
            return nil
    }
    return l.root.next
}
第一次删除 list的长度变为0
此时 调用l.Remove(l.Front()) 其中l.Front()返回的是一个nil
golang中Remove函数实现 该函数 没有判定e是否为nil
直接默认其为非nil 对其进行e.list或者e.Value取值操作
当e为nil时 这两个操作都将会造成程序崩溃 就是为什么程序会崩溃的原因
func (l *List) Remove(e *Element) interface{} {
    if e.list == l {
        // if e.list == l, l must have been initialized when e was inserted
        // in l or l == nil (e is a zero Element) and l.remove will crash
        l.remove(e)
    }
    return e.Value
}

函数 PushBackList

(l *list)PushBackList(other *list)
该函数用于将other list中元素添加在l list的后面
实现思想是取出other中所有元素
将其顺次挂载在l列表中 但是golang中实现有问题
func (l *List) PushBackList(other *List) {
    l.lazyInit()
    for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
        l.insertValue(e.Value, l.root.prev)
    }
}
首先获取 other 长度n 然后循环n次取出其元素将其插入l中
问题就出现在循环n次 如果在这个过程中other的元素变化
其中有些元素被删除了 这就导致e的指针可能为nil
此时再利用e.Value取值 程序便会崩溃
package main     
import (
    "container/list"
    "runtime"
)
func main() {
    runtime.GOMAXPROCS(8)
    l := list.New()
    ls := list.New()
    for i := 0; i < 10000; i++ {
        ls.PushBack(i)
    }
    go ls.Remove(l.Back())
    l.PushBackList(ls) //invalid memory address or nil pointer dereference
}
ls中元素添加到l过程中 如果ls中元素减少 程序便会崩溃
建议在golang中如果对与list的操作只有串行操作
则只需要注意检查元素指针是否为nil便可避免程序崩溃
如果程序中会并发处理list中元素 建议对list进行加写锁（全局锁） 然后再操作
注意 读写锁无法保证并行处理list时程序的安全性

golang slice 与list 的性能分析

数据很多 频繁的插入和删除用list
频繁的遍历查询选slice



go中container/list包和container相关