• list
• heap
• ring

list

list包实现了双向链表。

type Element

type Element struct {
    // Next and previous pointers in the doubly-linked list of elements.
    // To simplify the implementation, internally a list l is implemented
    // as a ring, such that &l.root is both the next element of the last
    // list element (l.Back()) and the previous element of the first list
    // element (l.Front()).
    next, prev *Element

    // The list to which this element belongs.
    list *List

    // The value stored with this element.
    Value interface{}
}

Element类型代表是双向链表的一个元素。

func (*Element) Next

func (e *Element) Next() *Element

Next返回链表的后一个元素或者nil。

func (*Element) Prev

func (e *Element) Prev() *Element

Prev返回链表的前一个元素或者nil。

type List

type List struct {
    root Element // sentinel list element, only &root, root.prev, and root.next are used
    len  int     // current list length excluding (this) sentinel element
}

代表一个双向链表。List零值为一个空的、可用的链表。

func New

func New() *List

New创建一个链表。

func (*List) Init

func (l *List) Init() *List

Init清空链表。

func (*List) Len

func (l *List) Len() int

Len返回链表中元素的个数，复杂度O(1)。

func (*List) Front

func (l *List) Front() *Element

Front返回链表第一个元素或nil。

func (*List) Back

func (l *List) Back() *Element

Back返回链表最后一个元素或nil。

func (*List) PushFront

func (l *List) PushFront(v interface{}) *Element

PushBack将一个值为v的新元素插入链表的第一个位置，返回生成的新元素。

func (*List) PushFrontList

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

PushFrontList创建链表other的拷贝，并将拷贝的最后一个位置连接到链表l的第一个位置。

func (*List) PushBack

func (l *List) PushBack(v interface{}) *Element

PushBack将一个值为v的新元素插入链表的最后一个位置，返回生成的新元素。

func (*List) PushBackList

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

PushBack创建链表other的拷贝，并将链表l的最后一个位置连接到拷贝的第一个位置。

func (*List) InsertBefore

func (l *List) InsertBefore(v interface{}, mark *Element) *Element

InsertBefore将一个值为v的新元素插入到mark前面，并返回生成的新元素。如果mark不是l的元素，l不会被修改。

func (*List) InsertAfter

func (l *List) InsertAfter(v interface{}, mark *Element) *Element

InsertAfter将一个值为v的新元素插入到mark后面，并返回新生成的元素。如果mark不是l的元素，l不会被修改。

func (*List) MoveToFront

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

MoveToFront将元素e移动到链表的第一个位置，如果e不是l的元素，l不会被修改。

func (*List) MoveToBack

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

MoveToBack将元素e移动到链表的最后一个位置，如果e不是l的元素，l不会被修改。

func (*List) MoveBefore

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

MoveBefore将元素e移动到mark的前面。如果e或mark不是l的元素，或者e==mark，l不会被修改。

func (*List) MoveAfter

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

MoveAfter将元素e移动到mark的后面。如果e或mark不是l的元素，或者e==mark，l不会被修改。

func (*List) Remove

func (l *List) Remove(e *Element) interface{}

Remove删除链表中的元素e，并返回e.Value。

func main() {
   l := list.New()

   for i := 0; i < 5; i++ {
      l.PushBack(i)
   }
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //01234
   }
   fmt.Println("")
   fmt.Println(l.Front().Value) //0
   fmt.Println(l.Back().Value)  //4

   l.InsertAfter(6, l.Front())  //首部元素之后插入一个值为6的元素
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //061234
   }
   fmt.Println("")
   l.MoveBefore(l.Front().Next(), l.Front()) //首部两个元素位置互换
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //601234
   }
   fmt.Println("")
   l.MoveToFront(l.Back()) //将尾部元素移动到首部
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //,460123
   }
   fmt.Println("")
   l2 := list.New()

   for i := 0; i < 5; i++ {
      l2.PushBack(i)
   }
   l2.PushBackList(l) //将l中元素放在l2的末尾
   for e := l2.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //01234460123
   }
   fmt.Println("")

   l.Init() //清空l
   fmt.Print(l.Len())                  //0
   for e := l.Front(); e != nil; e = e.Next() {
      fmt.Print(e.Value) //
   }
}

heap

heap包提供了对任意类型（实现了heap.Interface接口）的堆操作。（最小）堆是具有“每个节点都是以其为根的子树中最小值”属性的树。

树的最小元素为其根元素，索引0的位置。

heap是常用的实现优先队列的方法。要创建一个优先队列，实现一个具有使用（负的）优先级作为比较的依据的Less方法的Heap接口，如此一来可用Push添加项目而用Pop取出队列最高优先级的项目。

type Interface

type Interface interface {
    sort.Interface
    Push(x interface{}) // 向末尾添加元素
    Pop() interface{}   // 从末尾删除元素
}

任何实现了本接口的类型都可以用于构建最小堆。最小堆可以通过heap.Init建立，数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是：

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

注意接口的Push和Pop方法是供heap包调用的，请使用heap.Push和heap.Pop来向一个堆添加或者删除元素。

func Init

func Init(h Interface)

一个堆在使用任何堆操作之前应先初始化。Init函数对于堆的约束性是幂等的（多次执行无意义），并可能在任何时候堆的约束性被破坏时被调用。本函数复杂度为O(n)，其中n等于h.Len()。

func Push

func Push(h Interface, x interface{})

向堆h中插入元素x，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。

func Pop

func Pop(h Interface) interface{}

删除并返回堆h中的最小元素（不影响约束性）。复杂度O(log(n))，其中n等于h.Len()。等价于Remove(h, 0)。

func Remove

func Remove(h Interface, i int) interface{}

删除堆中的第i个元素，并保持堆的约束性。复杂度O(log(n))，其中n等于h.Len()。

func Fix

func Fix(h Interface, i int)

在修改第i个元素后，调用本函数修复堆，比删除第i个元素后插入新元素更有效率。

复杂度O(log(n))，其中n等于h.Len()。

ring

ring实现了环形链表的操作。

type Ring

type Ring struct {
    next, prev *Ring
    Value      interface{} // for use by client; untouched by this library
}

Ring类型代表环形链表的一个元素，同时也代表链表本身。环形链表没有头尾；指向环形链表任一元素的指针都可以作为整个环形链表看待。Ring零值是具有一个（Value字段为nil的）元素的链表。

func New

func New(n int) *Ring

New创建一个具有n个元素的环形链表。

func (*Ring) Len

func (r *Ring) Len() int

Len返回环形链表中的元素个数，复杂度O(n)。

func (*Ring) Next

func (r *Ring) Next() *Ring

返回后一个元素，r不能为空。

func (*Ring) Prev

func (r *Ring) Prev() *Ring

返回前一个元素，r不能为空。

func (*Ring) Move

func (r *Ring) Move(n int) *Ring

返回移动n个位置（n>=0向前移动，n<0向后移动）后的元素，r不能为空。

func (*Ring) Link

func (r *Ring) Link(s *Ring) *Ring

Link连接r和s，并返回r原本的后继元素r.Next()。r不能为空。

如果r和s指向同一个环形链表，则会删除掉r和s之间的元素，删掉的元素构成一个子链表，返回指向该子链表的指针（r的原后继元素）；如果没有删除元素，则仍然返回r的原后继元素，而不是nil。如果r和s指向不同的链表，将创建一个单独的链表，将s指向的链表插入r后面，返回s原最后一个元素后面的元素（即r的原后继元素）。

func (*Ring) Unlink

func (r *Ring) Unlink(n int) *Ring

删除链表中n % r.Len()个元素，从r.Next()开始删除。如果n % r.Len() == 0，不修改r。返回删除的元素构成的链表，r不能为空。

func (*Ring) Do

func (r *Ring) Do(f func(interface{}))

对链表的每一个元素都执行f（正向顺序），注意如果f改变了*r，Do的行为是未定义的。

func main() {
   r := ring.New(10) //初始长度10
   for i := 0; i < r.Len(); i++ {
      r.Value = i
      r = r.Next()
   }
   for i := 0; i < r.Len()*2; i++ {
      fmt.Print(r.Value)
      fmt.Print("|")
      r = r.Next()
   } // 0|1|2|3|4|5|6|7|8|9|0|1|2|3|4|5|6|7|8|9|
   fmt.Println("")
   r = r.Move(16)
   fmt.Println(r.Value) // 6
   r1 := r.Unlink(29)   //移除19%10=9个元素
   for i := 0; i < r1.Len(); i++ {
      fmt.Print(r1.Value)
      fmt.Print("|")
      r1 = r1.Next()
   }  // 7|8|9|0|1|2|3|4|5|1
   fmt.Println("")
   fmt.Println(r.Len())  // 1
   fmt.Println(r1.Len()) // 9

   r = r.Link(r1)
   fmt.Println(r.Len())  // 1

   r.Do(func(i interface{}) {
      fmt.Print(i.(int) * 5)
      fmt.Print("|")
   }) // 30|35|40|45|0|5|10|15|20|25|
}