新手问题 链表以及golang介入式链表的实现

sheepbao · 2017年10月14日 · 454 次阅读

链表以及 golang 介入式链表的实现

今天看 tcp/ip 协议栈的代码时看到一个双向链表,链表吗?听过它的顶顶大名,知道它是由节点构成的,每个节点还有个指针指向下一个节点,但是从来没自己实现过一个,没有实践就不能深刻理解,遂有此文。
以下所有观点都是个人愚见,有不同建议或补充的的欢迎 emial 我aboutme

何为链表?

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针 (Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。
简单的说链表是一个具有逻辑顺序的线性表,每一个节点里存到下一个节点的指针。

图示

单链表

list1

双向链表

list2

链表有啥用?

因为链表插入很快,而且具有动态性,想添加几个元素就添加几个(内存空间足够),不像数组一样那么死板,正因为链表的灵活性,所有链表的用处是大大的有啊。
链表最适合用于频繁更新变化的数据,比如一个需要异步执行并且不可丢失的命令序列、一个需要进行实时加载与卸载的驱动,无序且数量未知,这个时候就需要链表结构来协助完成数据的管理。如果不需要过度关注数据的顺序,还可以用链表方便快捷地在任意一个地方插入或删除一个元素,并且不会影响到其它的元素。
又或者我在今天看 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 (
    "container/list"
    "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: %#v\n", e.(*E).data)
    }
}

E里嵌入List即可作为链表的节点,是不是很方便,其实当我写完介入式链表的栗子后,发现其实标准库的链表更方便,哈哈。。因为 golang 有interface{}

参考

https://blog.goquxiao.com/posts/2013/07/06/intrusive-list/
http://blog.nlogn.cn/linked-list-in-linux-kernel/

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册