【数据结构与算法】共享双向链表

简介: 【数据结构与算法】共享双向链表

一.共享双向链表的引入

当我们使用双向链表其数据域是固定的类型,如果我需要另外一种类型的话,就需要重新来定义链表接口了.

问:有没有什么办法可以让多个链表共享同一套链表的操作呢?

答案是有的,就如同原来我们学的双向链表就类型于高铁,只能够载人,现在我们可以将底座于上层分开,可以统一拉货,也可以统一拉人.

二.共享双向链表的原理

结构体一但创建好,内存位置就固定了,我们可以通过offsetof根据链表节点在结构体的地址逆推出结构体变量的位置,然后就可以通过结构体来访问我们想要的数据.

可能不太懂,没事下面我还会讲,我们先来弄清楚其结构.

三.共享双向链表的结构

原来我们定义结构的时候分为数据域和指针域.

现在我们只定义指针域.

而我们想要的数据可以定义在一个结构体中,在结构体中在定义一个只有指针域的链表节点.

可能不太懂,画个图:

就像这样,链表是连起来的,像个小火车拖着数据.

我们通过结构体来关联我们的链表和数据.

这样我们不管是什么数据类型都可以使用我们的链表,都是同一套接口.

四.共享双向链表的初始化

这个就很简单了,因为当我们初始化结构体的时候,就相当于创建了链表.

因为我们在结构体里面定义的不是指针,这里传个引用就可以了.

我们将其赋值为-1,可以作为我们的头节点所装载的数据.

这里是对结构体里面的DbLinkNode node进行传参进行初始化.

五.共享双向链表插入

对于结构体里的链表处理,和我们原来的一样,只不过只能不是传入的指针罢了.

每次都生成一个结构体,然后将其里面的链表进行插入到刚刚初始化好的链表上.

六.共享链表遍历数据

最重要的就是这一步,现在我们结构体的链表已经链接好了,那么如何拿到结构体中的数据呢?

这就需要逆向思维了,我们知道了链表的位置,然后得到结构体的位置,从而可以访问结构体的数据.

我们可以使用offsetof

“offsetof” 是一个 C 语言中的宏定义,用于获取结构体中特定成员的偏移量(offset)。偏移量是指该成员相对于结构体起始位置的字节偏移量。

通过结构体中的链表变量和结构体的名字来算偏移量.

然后用结构体中的链表变量的地址减去偏移量,那么就是结构体的地址.

当然地址不能直接与整数相减,需要将地址类型转换,这里用的是size_t,相当于unsigned long long

然后得到的整数,我们将其转换为结构体指针.

然后就可以通过结构体指针进行数据的访问了.

七.共享链表的销毁

将结构体释放就可以了.

八.总结

共享链表,可以这样想象,首先,数据域与指针域是分开的.

链表只关心指针域.

然后通过结构体来关联数据和链表.

相当于一个个结构体通过其数据成员设置为链表进行关联.

又通过链表的地址与结构体的偏移量来获取结构体的地址.

从而可以对数据进行访问

看似是松散的,其实是紧密连接的,数据可以是任意的,链表的接口是不变的,从而达到了共享的目标.任何数据类型都可以用这只有指针域的链表.

相关文章
|
9天前
|
Java
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
1月前
|
存储 Java 索引
【数据结构】链表从实现到应用,保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同,其元素在内存中非连续分布,通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念,包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表,说明了其拥有前后两个指针的特点,并展示了相关操作的代码实现。最后,对比了ArrayList与LinkedList的不同之处,包括它们底层实现、时间复杂度以及适用场景等方面。
44 10
【数据结构】链表从实现到应用,保姆级攻略
|
2月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
|
2月前
|
存储 测试技术
【初阶数据结构篇】双向链表的实现(赋源码)
因为头结点的存在,plist指针始终指向头结点,不会改变。
|
2月前
|
存储 测试技术
【初阶数据结构篇】单链表的实现(附源码)
在尾插/尾删中,都需要依据链表是否为空/链表是否多于一个节点来分情况讨论,目的是避免对空指针进行解引用造成的错误。
|
2月前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
13 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
32 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
46 1
下一篇
无影云桌面