前言:
现在看官们对“循环链表的合并算法”大致比较看重,兄弟们都想要知道一些“循环链表的合并算法”的相关内容。那么小编在网上收集了一些有关“循环链表的合并算法””的相关内容,希望小伙伴们能喜欢,你们快快来学习一下吧!一、写在前面
标准库的双向循环链表实现是基于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的值等等,实现时可以先在纸上画图,再写代码。如果还有疑问可以参考如下链接中的源码:
标签: #循环链表的合并算法 #双向循环链表的初始化