基于数组的链表实现
前言
链表是一种由“节点”组成的数据结构,每个节点都储存着指向下一个节点的指针。通常来讲,指针都是存储的物理地址,因此在无法获取物理地址的语言里无法实现(比如BASIC);不过,其实也有别的方法在这些语言里实现指针的功能——即使用数组,以对象在数组内的索引作为指针的值。
传统的链表实现是定义节点对象的结构,用一个个独立的节点构建链表,不过这种做法在Java中空间效率并不是最高的。在64位Hotspot中,每个对象都有128位的对象头,里面包含了对象类型、对象锁、GC分代信息等。一个单向链表的节点对象最小需要两个引用,即16字节,加上对象头一共32字节,对象头的占比高达50%,这对内存而言是非常大的浪费。
传统的关系型数据库是按行存储的,每条记录都存储在“行”中;后来发展出了列数据库,数据被存在“列”中。这种列式存储的思维可以帮助我们实现另一种形式的“列式”链表。
基本思路
以数组表达的列的形式储存节点的所有属性,我们实现的是一个单向链表,需要两个数组,分别是next数组和value数组。我们使用一个变量head表示列表头,head指向列表头,而被head指向的节点则指向它的下一个节点,以此类推。为了支持从队列尾添加数据,我们还需要一个tail变量用来缓存链表尾的索引。同时,我们还有一个缓存链表大小的size
我们这个链表如果每次增删对象都要拷贝或者复制数组的话,运行效率会变得非常低(时间复杂度O(n)),因此我们在一个数组中实现了两个平行的链表,我将其命名为values链表(简称V)和empty链表(简称E),V用来存储数据,而E则用来暂存被删除的节点以待复用。从V中删除的节点都会同步加入E中,而当插入节点的时候也会优先取用E的节点。
参考 ArrayList 的实现,为了防止频繁复制数组,我们在empty链表用尽,需要扩容的时候还会额外扩容一部分空间。由于前文定义的E链表与V链表的性质,我们可以推导出E与V的组合体储存在一片连续的空间中,我们用变量used来表示这一段内存的结尾。当我们需要新的节点时,我们直接取used所指向的节点即可。
实现完备性证明
push 函数
push 函数把元素添加到链表头。
数组容量校验过程略。
push对象需要先获取一个节点,根据前面的定义,我们会优先从E链表中取节点,否则从used取节点。我们将这两种情况分开讨论。
当E链表为空时
当E链表不为空时
未完待续