golang泛型实现——双向循环链表

一、写在前面

标准库的双向循环链表实现是基于interface{}的，性能一般。为了提升性能，本文基于泛型语法实现一个比标准库更快的链表写法（主要包括双向循环链表的插入和删除的核心操作）。

二、什么是链表

链表用于存储逻辑关系为 "一对一" 的数据，与数组不一样，不要求存储地址是连续的。

三、链表的分类

type Node[T any] struct { 
    next    *Node[T] 
    Element T 
}

type Node[T any] struct { 
    next    *Node[T] 
    prev    *Node[T] 
    Element T 
}

四、双向循环链表的实现

下面主要介绍在工程上用得比较多的双向循环链表（将双向链表的头结点和尾结点链接起来构成循环的链表）的实现。

4.1 双向循环链表的表头定义和初始化函数

root.prevroot.next

root.prevroot.prev.prevroot.nextroot.next.next

 
// 每个Node节点, 包含前向和后向两个指针和数据域 
type Node[T any] struct { 
    next    *Node[T] 
    prev    *Node[T] 
    Element T 
} 
 
// 返回一个双向循环链表 
func New[T any]() *LinkedList[T] { 
    return new(LinkedList[T]).Init() 
} 
 
// 指向自己, 组成一个环 
func (l *LinkedList[T]) Init() *LinkedList[T] { 
    l.root.next = &l.root 
    l.root.prev = &l.root 
    l.length = 0 
    return l 
} 

4.2 插入节点的图示

root.prev

eate

// at e at.next 
// at <- e 
//       e -> at.next 
// at -> e 
//       e <- at.next 
func (l *LinkedList[T]) insert(at, e *Node[T]) { 
    e.prev = at 
    e.next = at.next 
    e.next.prev = e 
    at.next = e 
    l.length++ 
} 

4.2.1 插入节点之前的状态

4.2.2 修改e节点的prev指针

4.2.3 修改e节点的next指针

4.2.4 修改e.next.prev指针

4.2.5 修改at指针的next指针

即，修改2元素的next指针。

4.3 删除节点的图示

删除某个节点，是把这个节点的前面一个节点和后面一个节点搭上关系。
令n为待删除节点

 
// 删除这个元素 
// n.prev n n.next 
// n.prev --> n.next 
// n.prev <-- n.next 
func (l *LinkedList[T]) remove(n *Node[T]) { 
    n.prev.next = n.next 
    n.next.prev = n.prev 
    n.prev = nil 
    n.next = nil 
    l.length-- 
} 

4.3.1 删除节点之前的状态

4.3.2 修改n节点的前一个节点的next指针

n.prev.next = n.next

4.3.3 修改n节点的后一个节点的prev指针

即，下图为删除节点之后的状态。

五、性能压测

stdlib是目前标准库内置的双向循环链表, gstl是本文中提到的双向循环链表实现。benchmark逻辑是对两种链表的尾部节点添加数据，其中本文实现链表(gstl)性能相比标准库快一倍有余。

goos: darwin 
goarch: amd64 
pkg: github.com/guonaihong/gstl/linkedlist 
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz 
Benchmark_ListAdd_Stdlib-8        5918479           190.0 ns/op 
Benchmark_ListAdd_gstl-8         15942064            83.15 ns/op 
PASS 
ok      github.com/guonaihong/gstl/linkedlist    3.157s

六、完整的源代码

双向循环链表的操作除了上文提到的插入、删除外，还有表与表的合并、 分割、获取某个index的值等等，实现时可以先在纸上画图，再写代码。如果还有疑问可以参考如下链接中的源码：CSDN