今天看tcp/ip协议栈的代码时看到一个双向链表，链表吗？听过它的顶顶大名，知道它是由节点构成的，每个节点还有个指针指向下一个节点，但是从来没自己实现过一个，没有实践就不能深刻理解，遂有此文。
以下所有观点都是个人愚见，有不同建议或补充的的欢迎emial我aboutme
何为链表？
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
简单的说链表是一个具有逻辑顺序的线性表，每一个节点里存到下一个节点的指针。
图示
单链表
双向链表
链表有啥用？
因为链表插入很快，而且具有动态性，想添加几个元素就添加几个（内存空间足够），不像数组一样那么死板，正因为链表的灵活性，所有链表的用处是大大的有啊。
链表最适合用于频繁更新变化的数据，比如一个需要异步执行并且不可丢失的命令序列、一个需要进行实时加载与卸载的驱动，无序且数量未知，这个时候就需要链表结构来协助完成数据的管理。如果不需要过度关注数据的顺序，还可以用链表方便快捷地在任意一个地方插入或删除一个元素，并且不会影响到其它的元素。
又或者我在今天看tcp/ip源码中，链表用来构造队列，作为数据段的队列。我想链表用于队列应该是最多的。如果你看过linux内核源码，应该会发现linux内核中多处使用链表这种结构。
go标准库的双向链表
golang的标准库中实现了一个双向链表，该链表可以存储任何数据，先看看使用标准库链表的例子：
package list_test
import (
"container/list"
"fmt"
"testing"
)
func TestList(t *testing.T) {
// 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)
}
}
// output
// 1
// 2
// 3
// 4
该链表实现了链表所有的功能，链表的增删查改。
实现该链表的数据结构
// 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
}
// 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{}
}
可以看到Element结构体看到了链表的结构，next,prev分别指向下一个和前一个元素的指针。Value就是链表中的数据段，可以理解为上图中的object。
介入式链表(intrusive list)
前面的链表都是普通链表，记得<<c语言程序设计>>上讲的链表也是一样，就是链表的节点指针和数据段是放在同一个struct，每实现一个不同的struct就得重新实现一遍链表的功能，这对于“懒惰”的程序员来说是不可忍受的，所以就出来了介入式链表，将数据段和链表的功能区别开来。最经典的例子莫过于linux内核的list_head，详情请看链接klist or Linked List in Linux Kernel，linux中是用c实现的，我想用go实现一个介入式链表。
实现代码
package list
type Intrusive interface {
Next() Intrusive
Prev() Intrusive
AddNext(Intrusive)
AddPrev(Intrusive)
}
// List provides the implementation of intrusive linked lists
type List struct {
prev Intrusive
next Intrusive
}
func (l *List) Next() Intrusive {
return l.next
}
func (l *List) Prev() Intrusive {
return l.prev
}
func (l *List) AddNext(i Intrusive) {
l.next = i
}
func (l *List) AddPrev(i Intrusive) {
l.prev = i
}
func (l *List) Reset() {
l.prev = nil
l.next = nil
}
func (l *List) Empty() bool {
return l.prev == nil
}
// Front returns the first element of list l or nil.
func (l *List) Front() Intrusive {
return l.prev
}
// Back returns the last element of list l or nil.
func (l *List) Back() Intrusive {
return l.next
}
// PushFront inserts the element e at the front of list l.
func (l *List) PushFront(e Intrusive) {
e.AddPrev(nil)
e.AddNext(l.prev)
if l.prev != nil {
l.prev.AddPrev(e)
} else {
l.next = e
}
l.prev = e
}
// PushBack inserts the element e at the back of list l.
func (l *List) PushBack(e Intrusive) {
e.AddNext(nil)
e.AddPrev(l.next)
if l.next != nil {
l.next.AddNext(e)
} else {
l.prev = e
}
l.next = e
}
// InsertAfter inserts e after b.
func (l *List) InsertAfter(e, b Intrusive) {
a := b.Next()
e.AddNext(a)
e.AddPrev(b)
b.AddNext(e)
if a != nil {
a.AddPrev(e)
} else {
l.next = e
}
}
// InsertBefore inserts e before a.
func (l *List) InsertBefore(e, a Intrusive) {
b := a.Prev()
e.AddNext(a)
e.AddPrev(b)
a.AddPrev(e)
if b != nil {
b.AddNext(e)
} else {
l.prev = e
}
}
// Remove removes e from l.
func (l *List) Remove(e Intrusive) {
prev := e.Prev()
next := e.Next()
if prev != nil {
prev.AddNext(next)
} else {
l.prev = next
}
if next != nil {
next.AddPrev(prev)
} else {
l.next = prev
}
}
我们这里用List表示实现了Intrusive接口，也实现了链表的基本功能，所以任何实现了Intrusive接口的对象都是可以作为链表的节点，利用这个介入式链表就很简单了，只要在现有的struct嵌入List这个结构体即可，在举个例子：
package list
import (
"fmt"
"testing"
)
func TestIntrusiveList(t *testing.T) {
type E struct {
List
data int
}
// Create a new list and put some numbers in it.
l := List{}
e4 := &E{data: 4}
e1 := &E{data: 1}
l.PushBack(e4)
l.PushFront(e1)
l.InsertBefore(&E{data: 3}, e4)
l.InsertAfter(&E{data: 2}, e1)
for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("e: %+v\n", e)
fmt.Printf("data: %d\n", e.(*E).data)
}
}
// output
// e: &{List:{prev:<nil> next:0xc4200789c0} data:1}
// data: 1
// e: &{List:{prev:0xc420078960 next:0xc420078990} data:2}
// data: 2
// e: &{List:{prev:0xc4200789c0 next:0xc420078930} data:3}
// data: 3
// e: &{List:{prev:0xc420078990 next:<nil>} data:4}
// data: 4
在E里嵌入List即可作为链表的节点，是不是很方便，其实当我写完介入式链表的栗子后，发现其实标准库的链表更方便，哈哈。。因为golang有interface{}。
参考
https://blog.goquxiao.com/posts/2013/07/06/intrusive-list/
http://blog.nlogn.cn/linked-list-in-linux-kernel/
有疑问加站长微信联系（非本文作者）
