【數據結構】-5- 順序表（下）

一、集合框架?

這是 Java 集合框架（Java Collections Framework）的核心繼承關系樹狀圖

1. 最頂層：`Iterable`（接口）

作用：所有 “可迭代” 的集合（如?List、Set、Queue）都必須實現它，提供遍歷元素的能力（通過?iterator()?方法生成迭代器）。
關鍵方法：Iterator<T> iterator()?→ 返回迭代器，用于遍歷集合元素。

2. 第二層：`Collection`（接口）

地位：Java 集合框架的根接口（除?Map?體系外，所有集合都直接 / 間接繼承它）。
定義：規范了集合的基礎行為（增、刪、查、遍歷等），是所有單列集合（單個元素存儲）的 “通用契約”。
關鍵方法：
- add(E e)：添加元素
- remove(Object o)：刪除元素
- contains(Object o)：判斷是否包含元素
- size()：獲取元素個數
- iterator()：獲取迭代器（繼承自?Iterable）

3. 第三層：三大子接口（`List`、`Queue`、`Set`）

Collection?派生出三個核心子接口，代表三種不同的集合特性：

（1）`List`（接口）

特點：有序、可重復（元素按插入順序排列，允許存重復值）。
典型實現類：
- ArrayList：基于動態數組，查詢快（下標訪問?O(1)）、增刪慢（需移動元素）。
- LinkedList：基于雙向鏈表，增刪快（改變指針?O(1)）、查詢慢（需遍歷鏈表）。
- Vector：古老實現（線程安全，但性能差，已被?ArrayList?替代）。
- Stack：繼承?Vector，實現棧結構（后進先出，LIFO）。

（2）`Queue`（接口）

特點：隊列特性（通常 “先進先出，FIFO”，但部分實現支持優先級）。
典型實現類：
- LinkedList：同時實現?List?和?Queue，作為鏈表隊列使用。
- PriorityQueue：優先隊列（元素按優先級排序，不嚴格遵循插入順序）。
- Deque（子接口）：雙端隊列（兩端都可增刪），LinkedList?也實現了它。

（3）`Set`（接口）

特點：無序、不可重復（元素無順序，且 equals 相等的元素只能存一個）。
典型實現類：
- HashSet：基于哈希表（HashMap?實現），增刪查快（平均?O(1)），無序。
- TreeSet：基于紅黑樹，元素自動排序（需實現?Comparable），查詢慢（O(log n)）。
- SortedSet（子接口）：規范 “有序 Set” 行為，TreeSet?實現它。

4. 抽象類（`AbstractList`）

作用：簡化集合實現，為?List?接口的實現類提供通用邏輯（如部分方法默認實現）。
典型繼承：ArrayList、LinkedList?都繼承它，避免重復寫?add、remove?等基礎邏輯。

? 核心設計思想

接口分層：
- Iterable?定義 “可遍歷” 能力 →?Collection?定義 “集合基礎行為” → 子接口（List/Queue/Set）細化特性。
- 解耦 “通用行為” 和 “具體特性”，方便擴展（如新增集合類型只需實現接口）。
實現類分工：
- 不同實現類（ArrayList/LinkedList/HashSet?等）針對不同場景優化（數組查快、鏈表增刪快、哈希表去重等）。
- 開發時根據需求選實現類（查多改少用?ArrayList；增刪多用?LinkedList；去重用?Set）。
復用與擴展：
- 抽象類（如?AbstractList）封裝通用邏輯，減少實現類代碼量。
- 接口（如?Deque?繼承?Queue）擴展功能，讓集合支持更多特性（雙端操作）。

? 典型應用場景

存有序可重復數據 → 選?List（如?ArrayList?存學生名單，允許重復姓名）。
存無序不可重復數據 → 選?Set（如?HashSet?存用戶 ID，避免重復）。
需隊列 / 棧行為 → 選?Queue/Stack（如?PriorityQueue?實現任務優先級調度）。

掌握這張圖，就能清晰理解 Java 集合的體系脈絡，開發時也能更合理地選集合類型～

二、集合和數組區別?

你觀察得很敏銳！ArrayList?底層確實是用數組實現的（順序表本質），但 “集合轉數組” 的操作依然有其必要性，核心原因在于?“集合的抽象特性” 與 “數組的具體特性” 之間的差異，具體可以從三個角度理解：

? 接口與實現的分離：集合是 “抽象容器”，數組是 “具體存儲”

ArrayList?雖然底層用數組存儲，但它對外暴露的是?List?接口的抽象方法（如?add、get、size?等），隱藏了數組的具體實現細節（比如擴容邏輯、下標管理等）。

這種 “抽象” 帶來了便利（比如無需手動管理容量），但也限制了對底層數組的直接操作。例如：

你不能直接用?ArrayList?調用數組特有的工具方法（如?Arrays.sort()、Arrays.binarySearch()）；
某些 API 或框架可能只接收?Object[]?類型的參數（而非?List?集合）。

此時，toArray()?的作用就是?“打破抽象”，將集合中 “隱藏的數組元素” 提取出來，轉換為可直接操作的數組對象，以便使用數組的特性或兼容外部需求。

? 功能場景的差異：集合擅長 “動態管理”，數組擅長 “靜態操作”

ArrayList?作為集合，核心優勢是?動態管理數據（自動擴容、簡化增刪邏輯）；而數組的優勢是?靜態高效操作（如固定長度下的快速遍歷、使用?Arrays?工具類的各種功能）。

舉兩個典型場景：

需要使用數組工具類：
Arrays?類提供了大量便捷方法（排序、二分查找、填充等），但這些方法的參數必須是數組。例如，要對?ArrayList?中的元素排序，直接操作集合不方便，但轉成數組后就很簡單：
```
List<Integer> list = new ArrayList<>(Arrays.asList(3, 1, 2));
Integer[] arr = list.toArray(new Integer[0]); // 轉數組
Arrays.sort(arr); // 用數組工具排序
System.out.println(Arrays.toString(arr)); // [1, 2, 3]
```
需要固定長度的不可變結構：
集合是 “動態的”（可以隨時?add/remove?元素），而有時我們需要一個 “固定不變的快照”（比如傳遞數據時不希望被修改）。數組的長度固定，轉成數組后可以避免誤操作導致的元素變化：
```
Object[] arr = list.toArray(); // 數組長度固定為3
// 此時即使修改原集合，數組也不受影響
list.add("西瓜"); 
System.out.println(arr.length); // 仍為3（數組長度不變）
```

? 類型系統的限制：集合的泛型與數組的 “具體化”

ArrayList?雖然通過泛型（如?List<String>）保證了元素類型安全，但這種泛型是?編譯時檢查，運行時會被擦除（類型擦除）。而數組是?“具體化類型”（運行時也能確定類型），兩者在類型處理上有差異。

例如，當需要將集合元素傳遞給一個?“要求具體類型數組”?的方法時（如?void process(String[] strs)），直接傳?List<String>?會編譯報錯，必須通過?toArray(String[])?轉換為具體類型的數組：

process在編譯檢查時會確定里面的參數是不是string類型數組，但是List<String>里面會被擦除，無法判斷是不是確切的String類型，編譯會報錯。

// 定義一個接收 String[] 參數的方法
public static void process(String[] strs) {for (String s : strs) {System.out.println(s);}
}// 調用方法時，必須將 List<String> 轉為 String[]
List<String> list = new ArrayList<>(Arrays.asList("a", "b"));
process(list.toArray(new String[0])); // 正確：傳遞 String[] 數組

總結

ArrayList?底層用數組實現，但它作為 “集合” 提供的是更高層次的抽象功能（動態管理）。而?toArray()?的作用是?在需要時 “降級” 到數組層面，利用數組的特性（工具類支持、固定長度、具體類型）來滿足特定場景需求。

簡單說：集合是 “包裝好的數組”，方便日常使用；toArray()?是 “拆包裝” 的工具，讓我們在需要時能直接操作里面的 “數組內核”。

?三、toArray()?

在 Java 集合框架中，toArray()?是?Collection?接口（所有集合類的頂層接口，如?ArrayList、LinkedList、HashSet?等都實現了它）?定義的核心方法，作用是?將集合中的所有元素，轉換為一個「數組」并返回，本質是實現「集合 → 數組」的類型轉換。

[1]?核心作用：集合轉數組的 “橋梁”

集合（如?ArrayList）是動態存儲結構（大小可自動擴容），而數組是靜態存儲結構（初始化后大小固定）。

當需要用數組的方式操作集合元素（比如兼容某些只接收數組參數的方法、或需要數組的高效隨機訪問特性）時，toArray()?就是兩者之間的關鍵橋梁。

// 1. 創建一個集合，存入元素
List<String> list = new ArrayList<>();
list.add("蘋果");
list.add("香蕉");
list.add("橙子");// 2. 調用 toArray()，將集合轉為數組
Object[] fruitArray = list.toArray();// 3. 遍歷數組（此時可以用數組的操作方式處理原集合元素）
for (Object fruit : fruitArray) {System.out.println(fruit); // 輸出：蘋果、香蕉、橙子
}

在代碼?Object[] fruitArray = list.toArray();?中，toArray()?方法括號里沒有?new Object[0]，是因為調用的是?無參的?toArray()?方法，而不是帶參數的?toArray(T[] a)?方法。這兩個方法的設計目的和返回值有本質區別：

1. 無參?`toArray()`：直接返回?`Object[]`?數組

無參的?toArray()?方法是?Collection?接口定義的默認實現，它的行為是：

返回值固定為?Object[]?類型，無論集合的泛型是什么（即使是?List<String>，返回的也是?Object[]）。
內部會創建一個新的?Object[]?數組，并將集合中的元素復制進去。

因此，當我們寫?list.toArray()?時，不需要傳入任何參數，方法會自動創建并返回一個?Object[]?數組，所以代碼中直接寫成?list.toArray()?即可，無需?new Object[0]。

2. 帶參?`toArray(T[] a)`：需要傳入數組參數

另一個重載方法?toArray(T[] a)?的作用是?返回指定類型的數組（如?String[]、Integer[]），而非默認的?Object[]。此時需要傳入一個數組參數（如?new String[0]），目的是：

告訴方法 “我需要返回什么類型的數組”（參數的類型決定了返回數組的類型）。
例如?list.toArray(new String[0])?會返回?String[]?類型，而不是?Object[]。

3. 為什么這里不需要?`new Object[0]`？

因為代碼的需求是?獲取?Object[]?類型的數組，而無參?toArray()?正好直接返回?Object[]，完全滿足需求。此時如果畫蛇添足地傳入?new Object[0]，寫成：

Object[] fruitArray = list.toArray(new Object[0]); // 多余的參數

雖然功能上沒問題（返回的也是?Object[]），但參數是多余的 —— 無參方法已經能實現同樣的效果，傳入參數反而增加了代碼的冗余。

[2]?兩種常用重載形式（重點區分）

toArray()?有兩個核心重載方法，用法和返回值差異很大，實際開發中需根據需求選擇：

方法簽名	返回值類型	核心特點	適用場景
`Object[] toArray()`	`Object[]`	固定返回?`Object`?類型數組，無論集合泛型是什么	僅需 “遍歷元素”，不關心元素具體類型時（但有類型轉換風險，需謹慎）
`<T> T[] toArray(T[] a)`	傳入的數組類型?`T[]`	可指定返回數組的具體類型（如?`String[]`、`Integer[]`），避免后續強制類型轉換	需要明確數組類型（如調用需?`String[]`?參數的方法），是更常用、更安全的方式

（1）無參?`toArray()`：返回?`Object[]`

特點：無論原集合的泛型是?String、Integer?還是其他類型，返回的數組元素類型都是?Object（因為數組的編譯時類型是?Object[]）。
注意：不能直接將返回的?Object[]?強制轉為具體類型數組（如?String[]），會觸發?ClassCastException（類型轉換異常）。

List<String> list = new ArrayList<>();
list.add("a");
// 錯誤！Object[] 不能直接強轉 String[]
String[] arr = (String[]) list.toArray(); // 運行時拋 ClassCastException

（2）帶參?`toArray(T[] a)`：返回指定類型數組

特點：傳入一個 “指定類型的數組” 作為參數，方法會根據該數組的類型，返回一個同類型的數組（存儲集合元素），避免類型轉換風險。
內部邏輯：
1. 如果傳入的數組?a?大小?≥ 集合元素個數：直接將集合元素填入數組?a，多余位置填?null，返回?a?本身；
2. 如果傳入的數組?a?大小?＜集合元素個數：創建一個 “和?a?同類型、大小等于集合元素個數” 的新數組，填入元素后返回新數組。

List<String> list = new ArrayList<>();
list.add("a");
list.add("b");// 方式1：傳入一個大小足夠的數組（推薦，避免創建新數組）
String[] arr1 = new String[list.size()];
arr1 = list.toArray(arr1); // 返回 String[]，可直接使用// 方式2：傳入一個空數組（簡潔，JDK 1.8+ 常用）
String[] arr2 = list.toArray(new String[0]); // 內部會創建大小為 2 的新 String[]// 遍歷數組（無需強制轉換，類型安全）
for (String s : arr2) {System.out.println(s); // 輸出 a、b
}

[3]?關鍵注意點（避坑）

（1）無參?`toArray()`?的類型限制

再次強調：無參方法返回的?Object[]?只能存?Object?類型，不能強轉具體類型數組。若需具體類型，必須用帶參?toArray(T[] a)。

（2）返回數組是 “新數組” 還是 “原集合底層數組”？

對于?ArrayList：toArray()?返回的是復制后的新數組，修改數組元素不會影響原集合（因為數組和集合底層存儲的是兩個獨立的數組）。

List<Integer> list = new ArrayList<>();
list.add(10);
Integer[] arr = list.toArray(new Integer[0]);
arr[0] = 20; // 修改數組元素
System.out.println(list.get(0)); // 輸出 10（原集合無變化）

對于其他集合（如?Vector）：邏輯類似，均返回 “元素副本的數組”，避免外部通過數組修改集合內部狀態。

（3）集合元素為?`null`?時的處理

若集合中包含?null?元素，toArray()?會將?null?也存入數組（數組允許?null），遍歷數組時需注意判空，避免?NullPointerException。

List<String> list = new ArrayList<>();
list.add("a");
list.add(null); // 集合允許存 null
String[] arr = list.toArray(new String[0]);
System.out.println(arr[1]); // 輸出 null

四、`List`?接口常用方法?

一、增（添加元素）

boolean add(E e)
- 功能：在順序表末尾插入元素（尾插）。
- 邏輯：檢查容量 → 數組末尾賦值 →?size++?。
- 示例：
```
ArrayList<Integer> list = new ArrayList<>();
list.add(10); // 末尾插入10，size 變為1
```
void add(int index, E element)
- 功能：在指定下標?index?處插入元素，后續元素后移。
- 邏輯：檢查下標合法性 → 擴容（如需） → 從?index?開始后移元素 → 插入新值 →?size++?。
- 注意：index?范圍?[0, size]（允許末尾插入，對應?index=size?）。
- 示例：
- ```
list.add(1, 20); // 在索引1處插入20，原索引1及之后元素后移
```
boolean addAll(Collection<? extends E> c)
- 功能：把另一個集合?c?的元素全部尾插到當前表。
- 邏輯：遍歷集合?c?，逐個尾插元素；若插入成功（至少一個），返回?true?。
- 示例：
```
List<Integer> other = Arrays.asList(30, 40);
list.addAll(other); // 末尾插入30、40，size 增加2
```

二、刪（刪除元素）

E remove(int index)
- 功能：刪除指定下標?index?處的元素，返回被刪元素；后續元素前移。
- 邏輯：檢查下標合法性 → 保存被刪元素 → 從?index+1?開始前移元素 →?size--?→ 返回被刪值。
- 示例：
```
int removed = list.remove(1); // 刪除索引1的元素，返回該元素
```
boolean remove(Object o)
- 功能：刪除第一個遇到的元素?o（基于?equals?比較），刪除成功返回?true?。
- 邏輯：遍歷查找第一個與?o?相等的元素 → 找到則刪除（后續元素前移） → 返回是否刪除成功。
- 注意：若存儲自定義對象，需重寫?equals?保證比較邏輯正確。
- 示例：
```
list.remove(Integer.valueOf(20)); // 刪除第一個值為20的元素
```

三、改（修改元素）

E set(int index, E element)
- 功能：將下標?index?處的元素替換為?element，返回原元素。
- 邏輯：檢查下標合法性 → 保存原元素 → 賦值新元素 → 返回原元素。
- 示例：
- ```
int old = list.set(1, 25); // 索引1的元素改為25，返回原元素
```

四、查（獲取 / 查找元素）

E get(int index)
- 功能：獲取下標?index?處的元素。
- 邏輯：檢查下標合法性 → 直接返回數組對應位置的值（時間復雜度?O(1)?）。
- 示例：
```
int val = list.get(1); // 獲取索引1處的元素值
```
boolean contains(Object o)
- 功能：判斷元素?o?是否存在于表中（基于?equals?遍歷比較）。
- 邏輯：遍歷表，用?equals?比較元素；找到則返回?true?，否則?false?。
- 注意：自定義對象需重寫?equals?，否則比較地址而非內容。
- 示例：
```
boolean has = list.contains(25); // 判斷25是否在表中
```
int indexOf(Object o)
- 功能：返回第一個?o?所在的下標（基于?equals?遍歷）；不存在返回?-1?。
- 邏輯：遍歷表，找到第一個與?o?equals?的元素，返回其下標。
- 示例：
```
int idx = list.indexOf(25); // 找25第一次出現的下標
```
int lastIndexOf(Object o)
- 功能：返回最后一個?o?所在的下標（反向遍歷，基于?equals?）；不存在返回?-1?。
- 邏輯：從表末尾往前遍歷，找到第一個與?o?equals?的元素，返回其下標。
- 示例：
```
int lastIdx = list.lastIndexOf(25); // 找25最后一次出現的下標
```

五、工具操作

void clear()
- 功能：清空順序表（元素個數置 0，數組引用可保留或重置，不同實現可能有差異）。
- 邏輯：size = 0?（或額外把數組元素置?null?，幫助 GC 回收）。
- 示例：
```
list.clear(); // 清空后 size=0，元素全被移除
```
List<E> subList(int fromIndex, int toIndex)
- 功能：截取從?fromIndex（含）到?toIndex（不含）的子表，返回新?List?。
- 邏輯：創建新?List?，遍歷原表對應區間，復制元素；子表與原表共享底層數組（修改子表會影響原表，需注意）。
- 示例：
```
List<Integer> sub = list.subList(1, 3); // 截取索引1、2的元素，生成子表
```

六、方法調用關系 & 核心特點

依賴關系：增刪操作常依賴擴容（如?add?時檢查容量）、元素移動（插入 / 刪除時數組拷貝）；查找依賴?equals（自定義對象需重寫）。
時間復雜度：
- 尾插 / 尾刪（不擴容時）：O(1)?；
- 指定位置增刪（需移動元素）：O(n)?；
- 查找（遍歷）：O(n)?；
- 下標訪問（get/set）：O(1)?。
適用場景：適合頻繁按下標訪問、尾插操作；若需大量中間增刪，優先選鏈表（如?LinkedList?）。

五、?Java 集合的迭代器（`Iterator`）遍歷機制?

一、迭代器的作用：“指針” 式遍歷集合

迭代器（Iterator）是 Java 集合框架中用于安全遍歷集合元素的工具，它像一個 “移動的指針”，依次訪問集合中的每個元素。

核心優勢：

支持在遍歷中安全刪除元素（避免普通?for?循環遍歷刪除時的?ConcurrentModificationException）；
統一了各類集合的遍歷方式（List、Set、Queue?都能用迭代器遍歷）。

二、代碼執行流程

假設?list?是一個?List<Integer>，存儲元素?[1, 2, 3]，代碼：

Iterator<Integer> it = list.iterator(); // 1. 獲取迭代器
while (it.hasNext()) {                  // 2. 檢查是否有下一個元素System.out.println(it.next() + " "); // 3. 獲取并移動到下一個元素
}

1. 獲取迭代器：`list.iterator()`

作用：創建一個與?list?關聯的迭代器對象?it，初始時指向集合第一個元素之前（類似指針在數組下標?-1?的位置）。

2. 檢查是否有下一個元素：`it.hasNext()`

作用：判斷迭代器當前位置之后是否還有未訪問的元素。
執行邏輯：
- 第一次調用：指針在?-1，檢查到下標?0?有元素（1），返回?true。
- 第二次調用：指針在?0（已訪問?1），檢查到下標?1?有元素（2），返回?true。
- 第三次調用：指針在?1（已訪問?2），檢查到下標?2?有元素（3），返回?true。
- 第四次調用：指針在?2（已訪問?3），檢查到下標?3?無元素，返回?false，結束循環。

3. 獲取并移動指針：`it.next()`

作用：返回當前指針位置的下一個元素，并將指針向后移動一位（“自動向下執行” 的本質）。
執行邏輯：
- 第一次?it.next()：返回下標?0?的元素?1，指針移動到?0?→?1?之間（指向?1?之后）。
- 第二次?it.next()：返回下標?1?的元素?2，指針移動到?1?→?2?之間。
- 第三次?it.next()：返回下標?2?的元素?3，指針移動到?2?→?3?之間。

三、迭代器的 “指針” 模型（對應圖中結構）

圖中右側的 “豎排方框” 代表集合?list?的元素（1、2、3），it?是迭代器指針，執行流程對應：

初始狀態：it?指向第一個元素（1）之前（無具體位置，邏輯上在?-1）。
第一次?hasNext()：檢測到?1?存在 → 進入循環 →?next()?返回?1，指針移動到?1?之后。
第二次?hasNext()：檢測到?2?存在 → 進入循環 →?next()?返回?2，指針移動到?2?之后。
第三次?hasNext()：檢測到?3?存在 → 進入循環 →?next()?返回?3，指針移動到?3?之后。
第四次?hasNext()：檢測到無元素 → 退出循環。

四、迭代器的關鍵特點

單向遍歷：只能從前往后遍歷，無法回退（若需回退，用?ListIterator?子接口）。
快速失敗（fail-fast）：遍歷中若集合被修改（如?list.add/list.remove），會立即拋出?ConcurrentModificationException，避免臟讀。
與集合狀態綁定：迭代器遍歷的是創建時集合的 “快照”（但如果是?ArrayList?等基于數組的集合，遍歷中修改會觸發快速失敗）。

五、對比普通?`for`?循環遍歷

雖然?for-each?本質也是迭代器遍歷，但手動用?Iterator?的優勢在于：

支持遍歷中刪除元素（it.remove()，安全且不會報錯）；
更靈活（可控制遍歷過程，比如跳過某些元素）。

示例：遍歷中刪除元素（安全寫法）

Iterator<Integer> it = list.iterator();
while (it.hasNext()) {Integer num = it.next();if (num == 2) {it.remove(); // 安全刪除當前元素}
}

理解迭代器的 “指針移動” 模型后，就能掌握集合遍歷的底層邏輯，遇到遍歷相關的問題（如并發修改異常）也能快速定位啦～