golang 之 List源碼分析

前言

go語言中集合容器類相對貧乏，對比語言可以知道 go 的slice 可以和Java的List想對應。

 go的 List 底層是采用雙向連結清單來實作的，可以類比Java 中的雙向連結清單。

1.源碼分析之結構定義

List結構體定義如下：

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
}      

連結清單中的 元素（節點）結構題定義如下：

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.New()      

//相當于  xxx := List{} 建立一個List結構體的對象，然後初始化

func New() *List { return new(List).Init() }      

// 将 跟節點的 前置節點 指向 根節點 ，将根節點的後置節點指向根節點，設定容量

//為0  傳回list對象的引用。自己指向自己。。。

func (l *List) Init() *List {
   l.root.next = &l.root
   l.root.prev = &l.root
   l.len = 0
   return l
}      

剩下的就開始雙向連結清單的操作了：

歸類分為以下幾種操作

1.判斷連結清單的長度

2.在連結清單中插入節點

3.在連結清單中删除節點

4.雙連結清單的周遊

 注意：此 類在并發情況下不是協程安全的。

總結如下：

 節點 持有 List的指針

 List 持有 root根節點（Element）的指針