golang 的container/list (一)
golang 的container/list (一)
问题1：有了slice，还要list做什么？ 问题2：list的底层实现是什么？ 带着这两个问题来什么有浅入深的学习golang 语言 。 首先来看官方的解释：
包list 实现 linked list (链表) 而且是双向（doubly）链表。思路顺着双向链表走。 双向链表： 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，相对于单链表来讲：往前往后遍历都很方便。 双向链表他也是链表，既然是链表就具有链表的该有的特点。 借用一下wiki百科对链表的解释： *链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。 在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（”links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。
链表一个很大的优点：插入快，删除快。 而数组的有优点就是遍历快，索引快。
等等等，这里有一个疑问，slice的底层的是什么？ 查阅官方文档和度娘，slice 的底层实现就是数组。这下知道google 那些程序员们为什么要搞出来一个list了。 很明显两者有不同的适用场景。 list适合于那些频繁插入删除操作的场景。 而slice适合于那些多次查询的场景。 在我的下一片博客里面我会对slice和list 的性能对比分析。
这里我先介绍list 的基本使用方式，来看代码。
package main
import (
"container/list"
"fmt"
)
func main() {
// 创建一个 list
l := list.New()
//把4元素放在最后
e4 := l.PushBack(4)
//把1元素放在最前
e1 := l.PushFront(1)
//在e4元素前面插入3
l.InsertBefore(3, e4)
//在e1后面插入2
l.InsertAfter(2, e1)
// 遍历所有元素并打印其内容
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}运行结果：
1
2
3
4对着代码看： 创建一个list
l := list.New()在list 中插入一个元素并且放在list的最后节点。
e4 := l.PushBack(4)在list中插入一个元素并且放在list的第一个节点。
e1 := l.PushFront(1)在list的中的指定节点前插入
l.InsertBefore(3, e4)在list的中的指定节点后插入
l.InsertAfter(2, e1)最后遍历list
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}下面给出list 常用操作的示例： 每一个方法在代码中都有详细的解释。
package main
import (
"container/list"
"fmt"
)
func main() {
// 创建一个 list
l := list.New()
//把4元素放在最后
e4 := l.PushBack(4)
//把1元素放在最前
e1 := l.PushFront(1)
//在e4元素前面插入3
l.InsertBefore(3, e4)
//在e1后面插入2
e2:=l.InsertAfter(2, e1)
// 遍历所有元素并打印其内容
fmt.Println(" 元素 ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
//获取l 最前的元素
et1:=l.Front();
fmt.Println("list 最前的元素 Front ",et1.Value)
//获取l 最后的元素
et2:=l.Back()
fmt.Println("list 最后的元素 Back ",et2.Value)
//获取l的长度
fmt.Println("list 的长度为： Len ",l.Len())
//向后移动
l.MoveAfter(e1,e2)
fmt.Println("把1元素移动到2元素的后面 向后移动后 MoveAfter :")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
//向前移动
l.MoveBefore(e1,e2)
fmt.Println("\n把1元素移动到2元素的前面 向前移动后 MoveBefore :")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
//移动到最后面
l. MoveToBack(e1)
fmt.Println("\n 1元素出现在最后面 MoveToBack ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
//移动到最前面
l. MoveToFront(e1)
fmt.Println("\n 1元素出现在最前面 MoveToFront ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
//删除元素
fmt.Println("")
l.Remove(e1)
fmt.Println("\n e1元素移除后 Remove ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
// init 可以用作 clear
l.Init()
fmt.Println("\n list init()后 ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
fmt.Println("list 的长度Init ",l.Len())
//向前移动
//
}运行结果： 元素 1 2 3 4 list 最前的元素 Front 1 list 最后的元素 Back 4 list 的长度为： Len 4 把1元素移动到2元素的后面 向后移动后 MoveAfter : 2 1 3 4 把1元素移动到2元素的前面 向前移动后 MoveBefore : 1 2 3 4 1元素出现在最后面 MoveToBack 2 3 4 1 1元素出现在最前面 MoveToFront 1 2 3 4
e1元素移除后 Remove 2 3 4 list init()后 list 的长度Init 0 最后list 还提供两种方法。
func (*List) PushFrontList
func (*List) PushBackList这种两者方法可以批量向链表后端或者链表前端添加元素，有兴趣的读者可以仔细写个小demo测试测试。
踩坑： 添加元素为nil，向链表添加nil 元素 。经过测试完全没有问题。 添加的元素不是同一种类型，依然可添加成功。
func main() {
l := list.New()
//把4元素放在最后
e4 := l.PushBack(4)
//把1元素放在最前
e1:=l.PushFront(1)
//在e4元素前面插入3
l.InsertBefore(nil, e4)
//在e4元素前面插入3
l.InsertAfter("123132", e1)
fmt.Println(" 元素 ")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value," ")
}
}运行结果：1 123132 4 成功运行。