List的接口
func New() *List //创建List
func (l *List) Back() *Element //返回List的上一个元素
func (l *List) Front() *Element //返回List下一个元素
func (l *List) Init() *List //初始化List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element //在指定节点后插入,成功返回插入节点的指针,失败返回nil, 时间复杂度O(1)
func (l *List) InsertBefore(v interface{}, mark *Element) *Element //在指定节点之前插入, 成功返回插入节点的指针,失败返回nil, 时间复杂度O(1)
func (l *List) Len() int //返回链表长度,时间复杂度O(1)
func (l *List) MoveAfter(e, mark *Element) //移动节点e到mark节点之后,时间复杂度O(1), 处理方式:先删除然后再插入
func (l *List) MoveBefore(e, mark *Element) //移动节点e到mark节点之前,时间复杂度O(1), 处理方式:先删除然后再插入
func (l *List) MoveToBack(e *Element) //移动节点e到链表的尾部
func (l *List) MoveToFront(e *Element) //移动节点e到链表的头部
func (l *List) PushBack(v interface{}) *Element //在链表尾部追加值为v的新节点
func (l *List) PushBackList(other *List) //把链表other所有节点追加到当前链表的尾部
func (l *List) PushFront(v interface{}) *Element //在链表的头部插入新节点
func (l *List) PushFrontList(other *List) //把链表other所有节点追加到当前链表头部
func (l *List) Remove(e *Element) interface{} //删除指定节点
从这些接口我们可以看到Go的list应该是一个双向链表,不然InsertBefore这种操作应该不会放出来。
然后我们再从源码看看List的结构
// Element is an element of a linked list.
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{}
}
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
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的使用
package main import (
"container/list"
"fmt"
) func main() { list0 := list.New()
e4 := list0.PushBack()
e1 := list0.PushFront()
list0.InsertBefore(, e4)
list0.InsertAfter(, e1) for e := list0.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println("\r") front := list0.Front()
back := list0.Back() fmt.Println("front is:", front.Value)
fmt.Println("back is:", back.Value)
fmt.Println("length is", list0.Len()) list0.InsertBefore(, front)
list0.InsertAfter(, back) list0.PushFront(-)
list0.PushBack()
for e := list0.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println("\r")
list0.Remove(list0.Front())
for e := list0.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
} fmt.Println("\r")
list1 := list.New()
list1.PushBack()
list1.PushBack()
list0.PushBackList(list1)
for e := list0.Front(); e != nil; e = e.Next() {
fmt.Print(e.Value, " ")
}
fmt.Println("\r")
}
10-14行往list写入1,2,3,4
16行遍历打印list
21-16行打印front 和back节点
42-48行把另一个list追加到list的back
运行结果是:
front is:
back is:
length is
-