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）的指针