go保留的指针特性，但出于安全开来指针不支持位移运算。利用指针可以轻易实现高性能的链表数据结构。

定义结点

双链表的结点指针是递归定义，分别是next、prev。

1
2
3
4
5
type Node struct {
    next, prev *Node
    list *List
    Value interface{}
}

list字段用于判读该链表是否属于某一链表。Value声明为interface{}可以是Node存储任意对象。

为Node添加两个方法，以便访问该Node的前驱和后继。如果后继为空返回nil。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (e *Node) Next() *Node {
    if p := e.next; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

func (e *Node) Prev() *Node {
    if p := e.prev; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

定义链表对象

对链表的一些列操都以面向对象的方式封装，因此需要一个链表对象，用以保存操作的对象数据。添加len控制字段记录链表的长度，当需要查询链表的长度时直接访问该字段而不是遍历链表。

1
2
3
4
type List struct {
    root Node
    len int
}

实现创建链表的函数，

1
2
3
4
5
6
7
func NewList() *List {
    l := new(List)
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}

实现对List对象的各种操作

获取长度。List结构的len字段，当插入节点加1，删除结点时减1，初始化时为0。从而达到记录链表的长度，避免通过遍历链表来计算链表长度。

1
2
3
func (l *List) Len() int {
    return l.len
}

链表插入结点。把元素e插入到指定结点at的后面。每一次插入长度都会加1。这是一个通用函数。当要实现把元素插入到队尾的函数，复用该函数，同时指定at元素为队尾元素即可。同理，队头。

1
2
3
4
5
6
7
8
9
10
func (l *List) insert(e, at *Node) *Node {
    n := at.next
    at.next = e
    e.prev = at
    e.next = n
    n.prev = e
    e.list = l
    l.len++
    return e
}

链表插入具体的值。插入具体的值，只需要用Node包装该值然后调用insert方法即可。

1
2
3
func (l *List) insertValue(v interface{}, at *Node) *Node {
    return l.insert(&Node{Value: v}, at)
}

把元素插入到链表尾，复用insert函数即可。

1
2
3
4
func (l *List) Push(v interface{}) *Node {
    l.lazyInit()
    return l.insertValue(v, l.root.prev)
}

把元素插入到链表头。

1
2
3
4
func (l *List) PushLeft(v interface{}) *Node {
    l.lazyInit()
    return l.insertValue(v, &l.root)
}

移除结点元素

1
2
3
4
5
6
7
8
9
func (l *List) remove(e *Node) *Node {
    e.prev.next = e.next
    e.next.prev = e.prev
    e.next = nil // 避免内存泄漏
    e.prev = nil 
    e.list = nil
    l.len--
    return e
}

移除结点具体值。要判断指定的结点是否属于当前操作的链表。

1
2
3
4
5
6
func (l *List) Remove(e *Node) interface{} {
    if e.list == l {
        l.remove(e)
    }
    return e.Value
}

移除最后一个元素

1
2
3
4
5
func (l *List) Pop() interface{} {

}


移除第一个元素

1
2
3
func (l *List) PopLeft() interface{} {
}

上面就实现了双向链表及其基本功能。关于链表的相关操作见往期文章。