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);