List雙向連結清單

container/list是一個雙向連結清單，以下是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
}
           

相應方法

func (e *Element) Next() *Element  //傳回連結清單中e的下一個元素
func (e *Element) Prev() *Element  //傳回連結清單中e的上一個元素
func (l *List) Init() *List        //初始化或重置list
func New() *List                   //建立List對象
func (l *List) Len() int           //元素個數
func (l *List) Front() *Element    //傳回第一個元素，如果list為空傳回nil
func (l *List) Back() *Element     //傳回最後一個元素，如果list為空傳回nil
func (l *List) Remove(e *Element) interface{}  //移除e元素
func (l *List) PushFront(v interface{}) *Element   //将v封裝成*Element并插入到list的最前面，傳回v封裝的*Element
func (l *List) PushBack(v interface{}) *Element    //将v封裝成*Element并插入到list的最後面，傳回v封裝的*Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element    //将v封裝成*Element并插入到mark前面，傳回v封裝的*Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element     //将v封裝成*Element并插入到mark後面，傳回v封裝的*Element
func (l *List) MoveToFront(e *Element)    //将e移到list的最前面
func (l *List) MoveToBack(e *Element)     //将e移到list的最後面
func (l *List) MoveBefore(e, mark *Element)   //将e移到mark前面
func (l *List) MoveAfter(e, mark *Element)    //将e移到mark後面
func (l *List) PushBackList(other *List)      //将other *List中的所有元素插入到l List的尾部
func (l *List) PushFrontList(other *List)     //将other *List中的所有元素插入到l List的前面
           

*list.List的所有增删改都會調用其私有的方法插入或移除，func (l *List) insert(e, at *Element) *Element，func (l *List) remove(e *Element) *Element。也是其核心代碼

連結清單插入元素
func (l *List) insert(e, at *Element) *Element {
	n := at.next
	at.next = e
	e.prev = at
	e.next = n
	n.prev = e
	e.list = l
	l.len++
	return e
}
連結清單移除元素
func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
	return e
}
           

注意1：在擷取list的最後一個元素時在執行Next()時，按道理來說應該傳回的是root *Element,但是其傳回的是nil，來看源碼

func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}
           

如果e.next的指針和e.list.root的指針相同或者e.list(List,也就是根)為nil都傳回nil

注意2：在擷取list的第一個元素時在執行Prev()時，也會出現注意1的情況

示例：

import (
	"container/list"
	"fmt"
)

func main() {
	list1 := list.New()
	fmt.Println(list1.Len())                //0
	fmt.Println(list1.Back())               // <nil>  注意1
 	list1.PushBack("no.1")                  //["no.1"]
	fmt.Println(list1.Back().Value)         //no.1
	list1.PushBack(1)                       //["no.1",1]
	fmt.Println(list1.Back().Value)         //1
	list1.PushFront(true)                   //[true,"no.1",1]
	fmt.Println(list1.Front().Value)        //true
	list1.MoveToBack(list1.Front())         //["no.1",1,true]
	fmt.Println(list1.Back().Value)         //true
	list1.MoveToFront(list1.Front().Next()) //[1,"no.1",true]
	fmt.Println(list1.Front().Value)        //1
	fmt.Println(list1.Back().Next())        //傳回nil
	//list1.MoveToBack(list1.Back().Next())  //報錯，(注意1)
	list1.Remove(list1.Front())                         //["no.1",true]
	fmt.Println(list1.Front().Value)                    //no.1
	fmt.Println(list1.Len())                            //2
	list1.InsertAfter(10, list1.Front())                //["no.1",10,true]
	fmt.Println(list1.Front().Next().Value)             //10
	list1.InsertBefore(22, list1.Front())               //[22,"no.1",10,true]
	fmt.Println(list1.Front().Value)                    //22
	list1.MoveAfter(list1.Front(), list1.Back().Prev()) //["no.1",10,22,true]
	fmt.Println(list1.Back().Prev().Value)              //22
	print(list1)  //[no.1 10 22 true ]

	list2 := list.New()
	list2.PushBack(88)
	list2.PushBack(true)
	list2.PushBack("no.2")
	list1.PushBackList(list2)
	print(list1) //[no.1 10 22 true 88 true no.2 ]

	list3 := list.New()
	list3.PushBack(99)
	list3.PushBack(false)
	list3.PushBack("no.3")
	list1.PushFrontList(list3)
	print(list1)  //[99 false no.3 no.1 10 22 true 88 true no.2 ]
}

func print(list *list.List)  {
	for p := list.Front();p != nil;p = p.Next() {
		fmt.Printf("%v ",p.Value)
	}
	fmt.Println()
}
           

運作結果

0
<nil>
no.1
1
true
true
1
<nil>
no.1
2
10
22
22
no.1 10 22 true 
no.1 10 22 true 88 true no.2 
99 false no.3 no.1 10 22 true 88 true no.2