设为首页 加入收藏

TOP

Golang:List
2018-12-14 16:17:48 】 浏览:71
Tags:Golang:List

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 

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Qt显示Linux desktop natificatio.. 下一篇Golang:sync.Map

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }