链表(list)
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
在 Golang 的container/list标准包中，封装了双向链表的实现，需要注意的，list 不是线程安全的。双向链表的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。如下所示：
源码阅读
container/list包对外暴露了两个结构，分别是：
- Element: 一个链表中的元素
- List: 一个双向链表
Element
结构
Element 结构包含了 4 个部分：
- next: 指向前一个元素的指针；
- prev: 指向后一个元素的指针；
- list: 当前元素所属的 List；
- Value: 存储在当前元素的值。
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 contents of this list element.
Value interface{}
}看注释，我们可以注意到，Golang 的 List 是个环形结构（ring）,包含了root节点，既是双向链表中最后一个元素的 next，也是第一个元素的 prev。Element提供的方法也是用到了root节点，root 不存放数据，多这一个节点，可以有效的帮助我们操作头结点和尾结点。
方法
Next()和Prev()方法，定义如下：
// 返回该元素的下一个元素，如果没有下一个元素则返回 nil
func (e *Element) Next() *Element {
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
// 返回该元素的前一个元素，如果没有前一个元素则返回 nil
func (e *Element) Prev() *Element {
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
}List
结构
List 结构包含了 2 个部分
- root: 根节点，对外是不可见的，辅助操作头结点和尾结点；
- len: 记录当前链表的长度。
这里 结构只包含一个 root 元素，并且维护了一个 len 变量，记录当前链表的长度。我们通过 New() 构建出的 List 对象，只包含 root 一个元素，所以它的 next 和 prev 都是自己。
// 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
}
// Init initializes or clears list l.
func (l *List) Init() *List {
l.root.next = &l.root
l.root.prev = &l.root
l.len = 0
return l
}
// New returns an initialized list.
func New() *List { return new(List).Init() }方法
List 提供的方法如下：
func New() *List // 构造一个初始化的list
func (l *List) Back() *Element // 获取list l的最后一个元素
func (l *List) Front() *Element // 获取list l的最后一个元素
func (l *List) Init() *List // list l 初始化或者清除 list l
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之后插入一个值为 v 的元素，并返回该元素，如果 mark 不是list中元素，则 list 不改变
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在 list l 中元素 mark 之前插入一个值为 v 的元素，并返回该元素，如果 mark 不是list中元素，则 list 不改变
func (l *List) Len() int // 获取 list l 的长度
func (l *List) MoveAfter(e, mark *Element) // 将元素 e 移动到元素 mark 之后，如果元素e 或者 mark 不属于 list l，或者 e==mark，则 list l 不改变
func (l *List) MoveBefore(e, mark *Element) // 将元素 e 移动到元素 mark 之前，如果元素e 或者 mark 不属于 list l，或者 e==mark，则 list l 不改变
func (l *List) MoveToBack(e *Element) // 将元素 e 移动到 list l 的末尾，如果 e 不属于list l，则list不改变
func (l *List) MoveToFront(e *Element) // 将元素 e 移动到 list l 的首部，如果 e 不属于list l，则list不改变
func (l *List) PushBack(v interface{}) *Element // 在 list l 的末尾插入值为 v 的元素，并返回该元素
func (l *List) PushBackList(other *List) // 在 list l 的尾部插入另外一个 list，其中l 和 other 可以相等
func (l *List) PushFront(v interface{}) *Element // 在 list l 的首部插入值为 v 的元素，并返回该元素
func (l *List) PushFrontList(other *List) // 在 list l 的首部插入另外一个 list，其中 l 和 other 可以相等
func (l *List) Remove(e *Element) interface{} // 如果元素 e 属于list l，将其从 list 中删除，并返回元素 e 的值头尾节点
有了 root 节点，获取头尾节点就很容易，root 的下一个节点就是头，root 的前一个节点就是尾。
// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
if l.len == 0 {
return nil
}
return l.root.next
}
// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
if l.len == 0 {
return nil
}
return l.root.prev
}使用 list 包
list 包是开箱即用，十分方便。
官方例子：
import (
"container/list"
"fmt"
)
func main() {
// Create a new list and put some numbers in it.
l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)
// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}应用场景
- 数据库有序存储
- 时间轮
- 队列和栈
- 基于 LRU/LFU 的缓存
参考
- https://pkg.go.dev/container/list
- https://cs.opensource.google/go/go/+/tls:src/container/list/list.go
- https://zh.wikipedia.org/wiki/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8
本文由 Chakhsu Lau 创作，采用 知识共享署名4.0 国际许可协议进行许可。
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。