我要评论list的接口
1 func new() *list //创建list
2 func (l *list) back() *element //返回list的上一个元素
3 func (l *list) front() *element //返回list下一个元素
4 func (l *list) init() *list //初始化list
5 func (l *list) insertafter(v interface{}, mark *element) *element //在指定节点后插入，成功返回插入节点的指针，失败返回nil, 时间复杂度o(1)
6 func (l *list) insertbefore(v interface{}, mark *element) *element //在指定节点之前插入， 成功返回插入节点的指针，失败返回nil, 时间复杂度o(1)
7 func (l *list) len() int //返回链表长度，时间复杂度o(1)
8 func (l *list) moveafter(e, mark *element) //移动节点e到mark节点之后，时间复杂度o(1), 处理方式：先删除然后再插入
9 func (l *list) movebefore(e, mark *element) //移动节点e到mark节点之前，时间复杂度o(1), 处理方式：先删除然后再插入
10 func (l *list) movetoback(e *element) //移动节点e到链表的尾部
11 func (l *list) movetofront(e *element) //移动节点e到链表的头部
12 func (l *list) pushback(v interface{}) *element //在链表尾部追加值为v的新节点
13 func (l *list) pushbacklist(other *list) //把链表other所有节点追加到当前链表的尾部
14 func (l *list) pushfront(v interface{}) *element //在链表的头部插入新节点
15 func (l *list) pushfrontlist(other *list) //把链表other所有节点追加到当前链表头部
16 func (l *list) remove(e *element) interface{} //删除指定节点
从这些接口我们可以看到go的list应该是一个双向链表，不然insertbefore这种操作应该不会放出来。
然后我们再从源码看看list的结构
1 // element is an element of a linked list.
2 type element struct {
3 // next and previous pointers in the doubly-linked list of elements.
4 // to simplify the implementation, internally a list l is implemented
5 // as a ring, such that &l.root is both the next element of the last
6 // list element (l.back()) and the previous element of the first list
7 // element (l.front()).
8 next, prev *element
9
10 // the list to which this element belongs.
11 list *list
12
13 // the value stored with this element.
14 value interface{}
15 }
1 // list represents a doubly linked list.
2 // the zero value for list is an empty list ready to use.
3 type list struct {
4 root element // sentinel list element, only &root, root.prev, and root.next are used
5 len int // current list length excluding (this) sentinel element
6 }
从这里证实了上面的猜想，这是一个双向链表
list的使用
1 package main
2
3 import (
4 "container/list"
5 "fmt"
6 )
7
8 func main() {
9
10 list0 := list.new()
11 e4 := list0.pushback(4)
12 e1 := list0.pushfront(1)
13 list0.insertbefore(3, e4)
14 list0.insertafter(2, e1)
15
16 for e := list0.front(); e != nil; e = e.next() {
17 fmt.print(e.value, " ")
18 }
19 fmt.println("\r")
20
21 front := list0.front()
22 back := list0.back()
23
24 fmt.println("front is:", front.value)
25 fmt.println("back is:", back.value)
26 fmt.println("length is", list0.len())
27
28 list0.insertbefore(0, front)
29 list0.insertafter(5, back)
30
31 list0.pushfront(-1)
32 list0.pushback(6)
33 for e := list0.front(); e != nil; e = e.next() {
34 fmt.print(e.value, " ")
35 }
36 fmt.println("\r")
37 list0.remove(list0.front())
38 for e := list0.front(); e != nil; e = e.next() {
39 fmt.print(e.value, " ")
40 }
41
42 fmt.println("\r")
43 list1 := list.new()
44 list1.pushback(7)
45 list1.pushback(8)
46 list0.pushbacklist(list1)
47 for e := list0.front(); e != nil; e = e.next() {
48 fmt.print(e.value, " ")
49 }
50 fmt.println("\r")
51 }
10-14行往list写入1，2，3，4
16行遍历打印list
21-16行打印front 和back节点
42-48行把另一个list追加到list的back
运行结果是：
1 2 3 4 front is: 1 back is: 4 length is 4 -1 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论