一、写在前面

标准库的双向循环链表实现是基于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.prevroot.next指向root节点自己

root节点地址


// 每个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指针

修改e节点的prev指针

4.2.3 修改e节点的next指针

修改e节点的next指针

4.2.4 修改e.next.prev指针

修改e.next.prev指针

4.2.5 修改at指针的next指针

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

修改at指针的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

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

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

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

修改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/gstl/tree/master/linkedlist

作者:|guonaihong|,原文链接: http://www.imooc.com/article/325751

文章推荐

且看这个Node全栈框架,实现了个Cli终端引擎,可无限扩充命...

python常用标准库(os系统模块、shutil文件操作模块)

Unity-自定义事件派发器的两次尝试

C++从静态类型到单例模式

Python技法:用argparse模块解析命令行选项

一文详解 WebSocket 网络协议

python四个性能检测工具,包括函数的运行内存、时间等等...

CentOS 8及以上版本配置IP的方法,你 get 了吗

无需修改代码,用 fcapp.run 运行你的 REST 应用

MSDN系统原版镜像全系列所有历史版本下载

centos换源+安装postgresql

手把手带你自定义 Gradle 插件 —— Gradle 系列(2)