container 包中的 list

list

list 是一个双向链表（环）。
提供的方法如下：

type List
    func New() *List

    func (l *List) Back() *Element   // 返回最后一个元素
    func (l *List) Front() *Element  // 返回第一个元素

    func (l *List) Init() *List  // 链表初始化

    func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某个元素前插入
    func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在某个元素后插入

    func (l *List) Len() int // 返回链表长度

    func (l *List) MoveAfter(e, mark *Element)  // 把e元素移动到mark之后
    func (l *List) MoveBefore(e, mark *Element)  // 把e元素移动到mark之前
    func (l *List) MoveToBack(e *Element) // 把e元素移动到队列最后
    func (l *List) MoveToFront(e *Element) // 把e元素移动到队列最头部

    func (l *List) PushBack(v interface{}) *Element  // 在队列最后插入元素
    func (l *List) PushBackList(other *List)  // 在队列最后插入接上新队列
    func (l *List) PushFront(v interface{}) *Element  // 在队列头部插入元素
    func (l *List) PushFrontList(other *List) // 在队列头部插入接上新队列

    func (l *List) Remove(e *Element) interface{} // 删除某个元素

结构体定义

type List struct {
    root Element 
    len  int
}

type Element struct {
    list       *List
    Value      interface{}
    next, prev *Element
}

List第一个节点为哨兵节点，不存储任何信息，List的头从哨兵节点的下一个节点开始

初始化方法

插入元素

删除元素

列表插入函数的返回值会提供一个 *list.Element 结构，这个结构记录着列表元素的值以及与其他节点之间的关系等信息，从列表中删除元素时，需要用到这个结构进行快速删除

package main
import "container/list"
func main() {
    l := list.New()
    l.PushBack("canon")    // canon
    l.PushFront(67)    // 67, canon
    element := l.PushBack("fist")  // 67, canon, fist
    l.InsertAfter("high", element)  // 67, canon, fist, high
    l.Remove(element)  // 67, canon, high
}

移动元素

合并元素