基础

基础结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 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
}
  1. Element，封装保存在list中的值，
    1. Element中的变量next,prev是指针，分别指向当前元素的下一个元素与前一个元素
    2. Element中的变量list是指针，指向该Element所属的list
    3. Value存储的为List中存放的值
  2. List，list本身
    1. List中的变量root变量存储着List中的第一个元素，该元素Value为nil，只做为根，不存储数据
    2. List中的变量len变量表示List的长度
  3. 本质就是数据结构中的双向循环链表

主要操作：

Remove(e *Element)

移除元素

PushFront(v interface{})

在列表头部增加元素

PushBack(v interface{})

在列表尾部增加元素

InsertBefore(v interface{},mark *Element)*Element

在mark前增加元素

InsertAfter(v interface{},mark *Element)*Element

在mark后增加元素

MoveToFront(e *Element)

将元素移至列表头部

MoveToBack(e *Element)

将元素移至列表尾部

MoveBefore(e mark *Element)

将元素e移至mark前边

MoveAfter(e mark *Element)

将元素e移至mark后边

PushBackList(other *List)

将列表other放入当前列表尾部

PushFrontList(other *List)

将列表other放至当前列表头部