在 Java 中建立鍊錶數組
1.概述
某些程式設計場景需要對動態清單進行分組，同時仍保持基於索引的快速存取。鍊錶數組結合了數組的固定位置存取和鍊錶的靈活結構，提供了一個有效的解決方案。
在本教程中，我們將探討鍊錶數組是什麼、它在實際場景中適用的位置以及如何在 Java 中有效地實現和測試它。
2.什麼是鍊錶數組？
在 Java 中，鍊錶數組是一種結構，其中每個索引都保存一個LinkedList<T>而不是單一值。這使我們能夠維護索引訪問，同時支援在每個索引處進行動態插入和刪除：
LinkedList<Integer>[] listArray = new LinkedList[3];每個插槽都用 LinkedList 初始化，可以像任何陣列元素一樣存取：
listArray[0] = new LinkedList<>();
listArray[0].add(5);當我們需要透過索引快速存取和每個群組內的靈活儲存時，它很有用。
現在，讓我們探討一下它的一些用例。
3.我們可以在哪裡使用鍊錶數組？
這種結構不僅僅是一種編碼技巧；它解決了實際問題。以下是它發揮作用的幾個場景：
- 圖表示（鄰接表）：圖中的每個節點都可以儲存相鄰節點的清單。鍊錶數組是實現此目的的理想結構。
- 帶有連結的雜湊表：當多個鍵哈希到同一個索引時，連結列表可以將衝突的值儲存在該索引處。
- 桶排序：此排序演算法根據數字的範圍將數字分成桶，並對每個桶進行單獨排序。
- 基於索引的分組：可以使用索引清單按優先順序、區域或年齡組等屬性對使用者、日誌或事件等項目進行分類。
現在我們了解了為什麼要使用這種資料結構，我們將研究幾種實現它的方法。
4. 使用鍊錶數組
為了示範鍊錶數組的用法，讓我們考慮以下問題。
給定一個整數列表，讓我們將它們分為三類：
- 第 0 組：小於 10 的數字
- 第一組：10 至 19 的數字
- 第 2 組：20 號以上
讓我們定義一些實用方法來將數字分組到適當的鍊錶中。這些輔助方法展示了創建此資料結構後我們將如何使用它，以便我們可以專注於創建這些資料結構的各種方法。
我們將提供兩個版本的實用程式方法allocateNumbers(),一個用於外部List ，另一個用於外部Array .
第一個版本適用於連結清單的List ：
public static void allocateNumbers(int[] numbers, List<LinkedList<Integer>> groups) {
for (int num : numbers) {
int index = (num < 10) ? 0 : (num < 20 ? 1 : 2);
groups.get(index).add(num);
}
}第二個版本使用鍊錶數組：
public static void allocateNumbers(int[] numbers, LinkedList<Integer>[] groups) {
for (int num : numbers) {
int index = (num < 10) ? 0 : (num < 20 ? 1 : 2);
groups[index].add(num);
}
}在這兩個例子中，我們使用三元組來選擇要儲存數字的鍊錶的索引，然後將該數字新增到正確的清單中。
現在我們知道如何使用這些資料結構，讓我們專注於創建鍊錶數組的各種方法。
5. 使用帶有初始化循環的原始數組
使用原始數組是建立鍊錶數組最直接的方法。我們將宣告一個所需大小的數組，然後初始化數組的每個元素：
public static LinkedList<Integer>[] createUsingRawArray() {
@SuppressWarnings("unchecked")
LinkedList<Integer>[] groups = new LinkedList[3];
for (int i = 0; i < groups.length; i++) {
groups[i] = new LinkedList<>();
}
return groups;
}在這個方法中，我們建立一個大小為 3 的原始陣列來保存三個鍊錶。由於 Java 不允許直接建立泛型數組，我們使用@SuppressWarnings(“unchecked”)來抑制警告。然後，我們循環遍歷該數組，並用一個新的LinkedList初始化每個位置。這種方法可以快速存取索引，並且在大小固定的情況下非常理想。
現在，我們可以使用它來按照我們預期的方式對一些數字進行分組：
int[] numbers = {3, 7, 12, 19, 25, 32};
LinkedList<Integer>[] groups = createUsingRawArray();
LinkedListArray.allocateNumbers(numbers, groups);這將建立資料結構，然後根據我們的分組規則用給定數組中的數字填充每個列表。
原始數組方法反映了 C 風格語言中數組的使用方式，非常適合解決固定大小的 bucket 風格問題。
6. 使用LinkedLists List
與使用原始Array相比，更安全、更靈活的選擇是使用ArrayList來儲存LinkedList物件：
public static List<LinkedList<Integer>> createUsingList() {
List<LinkedList<Integer>> groups = new ArrayList<>();
for (int i = 0; i < 3; i++) {
groups.add(new LinkedList<>());
}
return groups;
}這裡，我們建立一個ArrayList並在其中加入三個空鍊錶。這種方法完全類型安全，並且避免了 unchecked warnings 。它比使用原始數組稍微靈活一些，並且是實際 Java 應用程式中的常見模式。
讓我們用這種方法來解決我們的問題：
int[] numbers = {3, 7, 12, 19, 25, 32};
List<LinkedList<Integer>> groups = createUsingList();
LinkedListArray.allocateNumbers(numbers, groups);我們首先建立資料結構，然後使用實用方法對數字進行分組。
7.使用 Java 8 Streams
如果我們更喜歡函數式風格，我們可以使用 Java 8 中首次引入的 Stream API。它可以簡潔地填充鍊錶列表：
public static List<LinkedList<Integer>> createUsingStreams() {
List<LinkedList<Integer>> groups = new ArrayList<>();
IntStream.range(0, 3).forEach(i -> groups.add(new LinkedList<>()));
return groups;
}在這裡，我們使用IntStream.range()從零循環到二，並且對於每個索引，我們會在主列表中新增一個新的鍊錶。
我們可以以同樣的方式使用這個資料結構：
List<LinkedList<Integer>> groups = createUsingStreams();
LinkedListArray.allocateNumbers(numbers, groups);當我們更喜歡聲明式程式碼或想要減少樣板時，這很有用。
8. Java 8+ 版本中使用Arrays.setAll()
如果堅持使用原始陣列很重要，但又想避免明確循環，我們可以使用Arrays.setAll() .此方法允許我們為每個索引分配值，而無需編寫明確循環：
public static LinkedList<Integer>[] createUsingSetAll() {
@SuppressWarnings("unchecked")
LinkedList<Integer>[] groups = new LinkedList[3];
Arrays.setAll(groups, i -> new LinkedList<>());
return groups;
}由於我們創建的是原始數組，因此我們仍然需要隱藏警告，但Arrays.setAll()讓初始化步驟更加簡潔。它使用新的鍊錶來設定數組中的每個索引。
讓我們將其應用到我們的問題中：
LinkedList<Integer>[] groups = createUsingSetAll();
LinkedListArray.allocateNumbers(numbers, groups);這種方法簡潔且富有表現力，特別是在使用 Java 8 或更高版本時。
9. 結論
在本文中，我們使用了鍊錶數組，將索引存取與動態資料處理結合。無論是對圖進行建模、使用鍊式結構實作雜湊表，還是將元素組織到多個動態列表中，這種結構都既靈活又有效率。
Java 支援多種建立和組織鍊錶數組的方法。這些方法包括手動初始化的原始數組，以及更現代、類型安全的列表或流等替代方案。每種方法都有其優缺點，正確的選擇取決於用例、效能目標和程式碼可讀性偏好。
與往常一樣，本文中提供的程式碼可在 GitHub 上找到。