共计 1920 个字符,预计需要花费 5 分钟才能阅读完成。
一、写在后面
规范库的双向循环链表实现是基于 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.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 的值 等等,实现时能够先在纸上画图,再写代码。如果还有疑难能够参考如下链接中的源码:https://github.com/guonaihong…