Java 记忆链表，LinkedList 的升级版

文章目录

记忆链表 MemoryLinkedList
实战
源代码

众所周知，ArrayList 和 LinkedList 是 Java 集合中两个基本的数据结构，对应数据结构理论中的数组和链表。但在这两个数据结构，开发者们通常使用 ArrayList，而不使用 LinkedList。JDK 1.2 源码 LinkedList 的作者 Josh Bloch 也几乎不使用 LinkedList。

为什么会这样呢？从数据结构理论中上看，它们之间应该只是各有千秋。其中，ArrayList 的定标访问效率应该优于 LinkedList，而 LinkedList 的插入和删除效率应该优于 ArrayList 才对。简单来说，ArrayList 的读性能应该优于 LinkedList，而 LinkedList 的写性能应该优于 ArrayList。但实际上，ArrayList 的大多数指标都要优于 LinkedList。

出现这一现象的原因有很多。在内存占用来说，Java 的对象都是匿名的，有名称的变量实际储存的是该变量的指针。因此 ArrayList 和 LinkedList 相当于一个指针数组，而指针本身的数据占用是很小的。由于 LinkedList 每个结点的数据结构过于复杂，有很多额外的数据，如上一个结点的指针、下一个结点的指针。因为储存实际数据元素本身用的就是指针，因此如果除去实际存储那部分有用的数据，LinkedList 占用的的空间将会是 ArrayList 的 2 ~ 3 倍。

内存占用还会体现在时间上。ArrayList 因为内存占用小，在数据量小的情形下，插入和删除时移动整片区域也实际不会耗费多少时间。

另外，就删除来言，一般都是要先查找到目标元素之后才能删除，因此 LinkedList 的理论删除效率也没有比 ArrayList 高多少。

此外，操作系统可能会对内存进行优化（局部性原理），缓存之前用到数据的附近位置的数据，这对 ArrayList 这种底层为连续内存的数据结构非常有利。

总而言之，相比于 ArrayList，LinkedList 是比较糟糕的，通常大家不会使用 LinkedList。

记忆链表 MemoryLinkedList

虽然通常 LinkedList 比 ArrayList 要差，不过我们通常是根据实际场景选择技术，而不能根据刻板印象一概而论。在大数据的定点删除，LinkedList 将会优于 ArrayList。但是，LinkedList 每次删除都要从头开始遍历，有时候，这是没有必要的。而这种从每次头开始遍历会大大削弱 LinkedList 的效率优势。

想象这样的一种情况，需要根据某个条件，在 LinkedList 中删除多个元素。这种情况下，如果每次删除都头开始遍历，就非常浪费时间。因为已经遍历过的区域实际上不存在需要删除的元素。

如果可以在遍历时记住上次遍历的位置就可以解决这一情况。为此，笔者在 LinkedList 的基础上，开发了一种记忆链表 MemoryLinkedList，它可以记住上次遍历的位置，让下一次遍历时可以从上次中止遍历的地方开始。此外，它还提供一种闭包用于进行基本操作的嵌套，如在遍历时删除当前元素、进行子遍历等等。

核心代码如下：

/*** 提供带自定义比较器的判断是否包含的方法。这个自定义比较器用于判断表中的元素是否相等。* 通常在元素为数组时使用本方法，因为数组的 equals 方法无法重写，* 而数组的原 equals 方法只是一种指针比较，因此可以使用本方法来弥补这一缺陷** @since 2023-2-5*/
public boolean contains(E other, Comparator<E> comparator) {if (other == null) {for (Node<E> x = this.first; x != null; x = x.next) {if (x.item == null) {return true;}}} else {for (Node<E> x = this.first; x != null; x = x.next) {if (comparator.compare(x.item, other) == 0) {return true;}}}return false;
}/*** 记忆点** 指向没有被遍历的第一个元素的位置** @since 2023-1-15*/
private transient Node<E> memory = this.first;/*** 快照记忆点** @since 2023-1-15*/
private transient Node<E> snapshotMemory;/*** 开启记忆模式** 调用后面的所有“记忆”函数之前，必须先调用本方法。记忆模式只对记忆函数起作用，其它函数不受影响，因此记忆模式不需要关闭** 个人自增方法** @since 2023-1-15*/
public MemoryLinkedList<E> setMemoryMode() {return this.resetMemory();
}/*** @since 2023-1-15*/
public MemoryLinkedList<E> resetMemory() {this.memory = this.first;return this;
}/*** 保存当前 memory 的一个快照** @since 2023-1-15*/
public MemoryLinkedList<E> saveSnapshotMemory() {this.snapshotMemory = this.memory;return this;
}/*** 将快照 memory 加载到 memory 中。此方法必须在 saveSnapshotMemory 至少调用一次后才能调用** @since 2023-1-15*/
public MemoryLinkedList<E> loadSnapshotMemory() {this.memory = this.snapshotMemory;return this;
}/*** 遍历。此方法不是记忆方法** Function：此方法的入参代表遍历的每个元素，返回值代表是否继续循环（true 代表继续循环）** 个人自增方法** @since 2023-1-15*/
public MemoryLinkedList<E> traverse(ListTraverseProcess<E> process) {for (Node<E> x = this.first; x != null; x = x.next) {if (!process.foreach(x.item)) {break;}}return this;
}/*** 遍历。此方法是记忆方法。在遍历正常到表尾时，此方法会自动重置记忆点** Function：此方法的入参代表遍历的每个元素，返回值代表是否继续循环（true 代表继续循环）** 个人自增方法** @since 2023-1-15*/
public MemoryLinkedList<E> traverseContinuously(ListTraverseProcess<E> process) {Node<E> xN = null;for (Node<E> x = this.memory; x != null; x = xN) {xN = x.next; // 这是为了防止下面的 apply 方法中含删除本结点的操作导致本结点的指针无效，因此需要提前保存下一个结点if (!process.foreach(x.item)) { // 当执行 apply 方法时，memory 指向当前正在遍历的元素 xif (xN == null) {this.resetMemory(); // 此处说明当前遍历的是表尾元素，因此需要重置记忆点} else {this.memory = xN; // 保存遍历元素的下一个元素的位置}return this;}this.memory = xN; // 遍历时，快照记忆点必须立刻保存，而不能等到退出循环的那一刻才保存}this.resetMemory(); // 重置记忆点return this;
}/*** 删除。此方法是记忆方法** 个人自增方法** @param needFeedback 如果为 true，则删除失败时会抛出异常。如果为 false，什么也不会发生* @since 2023-1-15*/
public MemoryLinkedList<E> removeContinuously(Object obj, boolean needFeedback) {for (Node<E> x = this.memory; x != null; x = x.next) {if (Objects.equals(x.item, obj)) {this.memory = x.next; // 保存删除元素的下一个元素的位置。只有在退出循环的那一刻才需要保存this.unlink(x);return this;}}if (needFeedback) {throw new RuntimeException("没有找到删除元素，删除失败");}return this;
}

实战

纸上得来终觉浅，没有实战的讲解没有任何意义。这里结合具体代码来介绍记忆链表 MemoryLinkedList 的使用。

笔者在早年间曾经进行过大量的彩票、股票研究。其中有这样一个场景，需要列出所有满足指定条件双色球号码。这里采取的策略是，先使用 MemoryLinkedList 收集所有的双色球号码，然后遍历每一个号码，从中去掉不符条件的号码。因为双色球总号码数量巨大，所以不适合基于连续内存的 ArrayList。由于在一次遍历中，需要大量的删除操作，因此也不适合原始的 LinkedList。于是，笔者编写的 LinkedList 升级版，记忆链表 MemoryLinkedList 就派上用场了。

双色球的投注规则是，从红色球‌的 1 ~ 33 号码中选择‌ 6 个，从蓝色球‌的 1 ~ 16 号码中选择‌ 1 个。

下面的代码给出了红球 胆码 的筛选过程。

/*** 胆码。numbers 中所有的号码都要存在，因此 numbers 的长度不能超过 6** @since 2023-1-14*/
public DcRedLottery braveNumber(int... numbers) {this.redResults.setMemoryMode().traverseContinuously(ele -> {if (!IntMathSetUtil.contain(ele, numbers)) {this.redResults.removeContinuously(ele, false);}return true;});return this;
}

下面的代码给出了红球 杀码 的筛选过程。

/*** 杀码。去掉所有含 numbers 中任意一个元素的组合** @since 2023-1-14*/
public DcRedLottery killNumber(int... numbers) {this.redResults.setMemoryMode().traverseContinuously(ele -> {// 此处需要求交集，不是用包含来判断if (IntMathSetUtil.intersect(ele, numbers).length >= 1) {this.redResults.removeContinuously(ele, false);}return true;});return this;
}

下面的代码给出了红球 复式 的筛选过程。

/*** 复式。从 numbers 中选择 choiceNum 个号码作为胆码** @param only 为 true 代表 numbers 中只能选择 choiceNum 个号码，numbers 中的其它号码不能存在* @since 2023-1-19*/
public DcRedLottery multiple(int[] numbers, int choiceNum, boolean only) {// 为了提高效率，此层判断必须放到外面if (only) {this.redResults.setMemoryMode().traverseContinuously(ele -> {if (!(IntMathSetUtil.intersect(ele, numbers).length == choiceNum)) {this.redResults.removeContinuously(ele, false);}return true;});} else {this.redResults.setMemoryMode().traverseContinuously(ele -> {if (!(IntMathSetUtil.intersect(ele, numbers).length >= choiceNum)) {this.redResults.removeContinuously(ele, false);}return true;});}return this;
}

下面是一些更复杂的情况。

/*** 横向号码连续情况。本方法允许 continuousNum 或 groupNum 出现大于的情况。* 比如，* 就算限定 2 连续，也可以出现 3 连续。* 就算限定 2 连续为 2 个，则也可以允许 2 连续出现 3 个。* 就算限定 2 连续为 2 个，则也可以允许 2 连续出现 1 个，然后 3 连续出现 1 个。** @param continuousNum 有 continuousNum 个号码连续* @param groupNum 对于 continuousNum 个号码连续的情况，出现了 groupNum 组（不连续的号码群称为一组）* @since 2023-12-17*/
public DcRedLottery hContinuousBigger(int continuousNum, int groupNum) {this.redResults.setMemoryMode().traverseContinuously(ele -> {var groups = GroupAnalysisUtil.generateGroups(ele);var distribution = GroupAnalysisUtil.continuousDistribution(groups);int sum = 0;// 统计连续数不小于 continuousNum 的组数for (int num = continuousNum; num < distribution.length; ++num) {sum += distribution[num];}if (sum < groupNum) {this.redResults.removeContinuously(ele, false);return true;}return true;});return this;
}

下面的代码了筛选出了满足如下条件的双色球号码。

至少有一个号码与 ref 的距离为 1 及以内。其中，ref = {1, 2, 10, 22, 24, 25}
3 区比为 2:3:1
奇偶比为 2:4
有且只有两个号码连续

int[] ref = {1, 2, 10, 22, 24, 25};
var redLottery = DcRedLottery.getInstance().selectAll().near(ref, 1, ComparativePredicate.MOST, 1, ComparativePredicate.LEAST).section3Proportion(2, 3, 1).parity(2, 4).hContinuousEqually(2, 1);