Go语言标准库学习之container——Go语言如何实现单链表、循环链表、双向链表、堆

在 Go 语言中我们可以直接使用 container 标准库完成链表和堆操作，非常方便，我们不需要自己去实现这些方法，本文向大家介绍 container 库的使用方法，希望对你有帮助。

一、双向链表

1. Element

Element 中保存了链表的所有信息，我们来看一下源码：

type Element struct {// 双链接元素列表中的下一个和上一个指针。next, prev *Element// 此元素所属的链表。list *List// value 中保存了链表的值Value interface{}
}// List是一个双向链表
type List struct {root Element // 当前节点元素len int // 链表长度
}


2. 生成一个链表

生成一个链表很简单，我们通过下面的函数可以获得一个 List 对象的指针：

func New() *List

然后我们对链表进行初始化：

func (l *List) Init() *List

Init会清空 List 链表中的数据，生成一个全新的链表，因此我们也可以使用 Init 方法来清空一个链表。

3. 链表的增删改查

• 插入链表

  // 将 v 插入链表的第一个位置
func (l *List) PushFront(v interface{}) *Element
// 复制 other 链表，并将 other 的最后一个元素连接到 l 的第一个位置
func (l *List) PushFrontList(other *List)
// 将 v 插入链表的最后一个元素
func (l *List) PushBack(v interface{}) *Element
// 复制 other 链表，并将 other 的第一个元素连接到 l 的最后一个位置
func (l *List) PushBackList(other *List)
// InsertBefore将一个值为v的新元素插入到mark前面，并返回生成的新元素。
// 如果mark不是l的元素，l不会被修改。
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
// InsertAfter将一个值为v的新元素插入到mark后面，并返回新生成的元素。
// 如果mark不是l的元素，l不会被修改。
func (l *List) InsertAfter(v interface{}, mark *Element) *Element

  




• 查询链表

  // Next返回链表的后一个元素。
func (e *Element) Next() *Element
// Prev返回链表的前一个元素
func (e *Element) Prev() *Element
// 查询链表第一个元素
func (l *List) Front() *Element
// 查询链表最后一个元素
func (l *List) Back() *Element

  




• 删除链表

  // Remove删除链表中的元素e，并返回e.Value。
func (l *List) Remove(e *Element) interface{}

  




• 修改链表

  // MoveToFront将元素e移动到链表的第一个位置，如果e不是l的元素，l不会被修改。
func (l *List) MoveToFront(e *Element)
// MoveToBack将元素e移动到链表的最后一个位置，如果e不是l的元素，l不会被修改。
func (l *List) MoveToBack(e *Element)
// MoveBefore将元素e移动到mark的前面。
// 如果e或mark不是l的元素，或者e==mark，l不会被修改。
func (l *List) MoveBefore(e, mark *Element)
// MoveAfter将元素e移动到mark的后面。如果e或mark不是l的元素，或者e==mark，l不会被修改。
func (l *List) MoveAfter(e, mark *Element)

  




• 其他功能

  // 查询链表的长度
func (l *List) Len() int

  

4. 我们实现一个反向链表的功能

题目描述：

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL


func reverseList(l *list.List) *list.List {// 获取 l 的头节点head := l.Front()for head.Next() != nil {// head 移动到最后一个位置结束if head.Next() == nil {break}// 将 head.Next 移动到第一个位置l.MoveToFront(head.Next())}return l
}


二、环形链表

1. Ring

// Ring是一个环形链表，他没有开始和结尾
type Ring struct {next, prev *RingValue interface{} // 用户可以自定义
}


2. 环形链表的初始化

我们可以通过 New 函数初始化一个有 n 个节点的环形链表

func New(n int) *Ring

3. 环形链表管理

• 查看链表长度

  func (r *Ring) Len() int

  




• 返回链表下一个元素

  func (r *Ring) Next() *Ring

  




• 返回链表的上一个元素

  func (r *Ring) Prev() *Ring

  




• 返回指定位置的元素

  // 返回移动n个位置（n>=0向前移动，n<0向后移动）后的元素，r不能为空。
func (r *Ring) Move(n int) *Ring

  




• 连接两个环形链表

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

  




• 删除环形链表中的元素

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

  




• 管理链表中的元素

  // 对链表的每一个元素都执行f（正向顺序）
func (r *Ring) Do(f func(interface{}))

  

4. 举个例子

计算环形链表上所有值的和：

package mainimport ("container/ring""fmt"
)type SumInt struct {Value int
}func (s *SumInt) add(i interface{}) {s.Value += i.(int)
}func main() {r := ring.New(10)for i := 0; i < 10; i++ {r.Value = ir = r.Next()}sum := SumInt{}r.Do(sum.add)fmt.Println(sum.Value)
}


三、堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。

1. 构建堆需要满足的条件

container/heap 标准库中定义了对（最小）堆进行操作的接口：

type Interface interface {sort.InterfacePush(x interface{}) // 向末尾添加元素Pop() interface{} // 从末尾删除元素
}
// sort.Interface
type Interface interface {// 元素个数Len() int// 索引为 i 的元素是否需要排在 索引为 j 的元素前面// Less方法的实现决定了堆是最大堆还是最小堆。Less(i, j int) bool// 交换索引为 i 和 j 的元素Swap(i, j int)
}


任何实现了本接口的类型都可以用于构建最小堆。最小堆，是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

最小堆可以通过heap.Init建立，数据是递增顺序或者空的话也是最小堆。最小堆的约束条件是：

!h.Less(j, i) for 0 <= i