一、写在后面

规范库的双向循环链表实现是基于interface{}的，性能个别。为了晋升性能，本文基于泛型语法实现一个比规范库更快的链表写法（次要包含双向循环链表的插入和删除的外围操作）。

二、什么是链表

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

三、链表的分类

  • 链表依据指针的指向分为 单向链表 和 双向链表 。

    • 单向链表：通常应用Next指针
    type Node[T any] struct {    next    *Node[T]    Element T}
    • 双向链表：通常应用Next、Prev两个指针.
    type Node[T any] struct {    next    *Node[T]    prev    *Node[T]    Element T}

  • 链表依据是否循环, 又分为

    • 单向循环链表
    • 双向循环链表
    • 单向链表
    • 双向链表

四、双向循环链表的实现

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

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

循环链表和一般的双向链表最大的区别是初始化的时候root.prev和root.next要指向root节点本人。

阐明：

这是一个递归定义,能够试着打印root.prev，root.prev.prev或者root.next，root.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节点，如何指向最初一个元素呢? 就是root.prev，下图展现双向循环链表插入节点的过程。

  • e是待插入节点
  • at是实现插入动作之后e节点后面的一个节点
// at e at.next// at <- e//       e -> at.next// at -> e//       e <- at.nextfunc (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.nextfunc (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: darwingoarch: amd64pkg: github.com/guonaihong/gstl/linkedlistcpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHzBenchmark_ListAdd_Stdlib-8        5918479           190.0 ns/opBenchmark_ListAdd_gstl-8         15942064            83.15 ns/opPASSok      github.com/guonaihong/gstl/linkedlist    3.157s

六、残缺的源代码

双向循环链表的操作除了上文提到的插入、删除外，还有表与表的合并、 宰割、获取某个index的值等等，实现时能够先在纸上画图，再写代码。如果还有疑难能够参考如下链接中的源码：https://github.com/guonaihong...