一、數(shù)據(jù)結(jié)構(gòu)與核心特性
1. ArrayList
- 數(shù)據(jù)結(jié)構(gòu):基于動(dòng)態(tài)數(shù)組實(shí)現(xiàn),元素存儲(chǔ)在連續(xù)內(nèi)存中。
- 核心特性:
– 通過索引隨機(jī)訪問元素,時(shí)間復(fù)雜度 O (1)。
– 擴(kuò)容機(jī)制:容量不足時(shí)新建數(shù)組(原容量的 1.5 倍)并復(fù)制元素。
– 尾部添加 / 刪除效率高(O (1)),中間操作需移動(dòng)元素(O (n))。
– 不直接支持 poll/offer,需借助 ArrayDeque 或 LinkedList 包裝。
2. LinkedList
- 數(shù)據(jù)結(jié)構(gòu):雙向鏈表,每個(gè)節(jié)點(diǎn)包含前驅(qū)、后繼指針和元素值。
- 核心特性:
– 任意位置插入 / 刪除僅需修改指針(O (1)),但隨機(jī)訪問需遍歷(O (n))。
– 實(shí)現(xiàn) Deque 接口,原生支持 poll/offer 等隊(duì)列操作。
– 無容量限制,節(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存,內(nèi)存占用高于 ArrayList。
二、核心方法對(duì)比
操作類型 | ArrayList | LinkedList |
---|
構(gòu)造 | new ArrayList<>() (初始容量 10) | new LinkedList<>() |
添加元素 | add(E e) (尾部,O(1))
add(index, e) (中間,O(n)) | add(e) (尾部,O(1))
addFirst(e) / addLast(e) (O(1)) |
刪除元素 | remove(index) (O(n)) | removeFirst() / removeLast() (O(1)) |
隨機(jī)訪問 | get(index) (O(1)) | get(index) (O(n),需遍歷鏈表) |
隊(duì)列操作(poll) | 需包裝為 ArrayDeque ,本質(zhì)數(shù)組操作 | poll() (取頭部,O(1))
pollFirst() / pollLast() (O(1)) |
隊(duì)列操作(offer) | 需包裝為 ArrayDeque ,尾部添加 O(1) | offer(e) (尾部,O(1))
offerFirst(e) / offerLast(e) (O(1)) |
三、poll 和 offer 方法詳解
1. 方法定義與功能
- poll():獲取并移除集合頭部元素,空集合返回 null(區(qū)別于 remove() 的異常)。
- offer(E e):添加元素到集合,成功返回 true(LinkedList 無容量限制,始終成功)。
2. LinkedList 中的隊(duì)列操作
LinkedList<String> deque = new LinkedList<>();
deque.offer("A");
deque.offerFirst("B");
deque.offerLast("C");
String head = deque.poll();
String tail = deque.pollLast();
String empty = deque.poll();
3. ArrayList 實(shí)現(xiàn)隊(duì)列操作(需適配器)
Deque<Integer> queue = new ArrayDeque<>(Arrays.asList(1, 2, 3));
queue.offer(4);
int first = queue.poll();
Queue<Integer> arrayListQueue = new LinkedList<>(new ArrayList<>());
arrayListQueue.offer(5);
四、性能與適用場景
1. 性能對(duì)比
操作 | ArrayList | LinkedList |
---|
尾部添加 | O(1) | O(1) |
中間插入 | O(n) (移動(dòng)元素) | O(1) (修改指針) |
隨機(jī)訪問 | O(1) | O(n) (遍歷鏈表) |
poll/offer 頭部 | 需適配器,O(1) | O(1) |
2. 適用場景
- 選 ArrayList 的場景:
- 頻繁隨機(jī)訪問(如 get(index))。
- 尾部添加 / 刪除為主(如日志記錄)。
- 數(shù)據(jù)量可預(yù)測,避免頻繁擴(kuò)容。
- 選 LinkedList 的場景:
- 頻繁在頭部 / 中間插入 / 刪除(如任務(wù)隊(duì)列)。
- 需要使用 poll/offer 等雙端隊(duì)列操作。
- 數(shù)據(jù)量不確定,不希望有擴(kuò)容開銷。
五、代碼示例:綜合應(yīng)用
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;public class ListComparison {public static void main(String[] args) {ArrayList<String> arrayList = new ArrayList<>();arrayList.add("蘋果");arrayList.add("香蕉");System.out.println("ArrayList 隨機(jī)訪問:" + arrayList.get(1)); Queue<String> taskQueue = new LinkedList<>();taskQueue.offer("數(shù)據(jù)采集");taskQueue.offer("模型訓(xùn)練");System.out.println("隊(duì)列處理順序:");while (!taskQueue.isEmpty()) {System.out.println("- " + taskQueue.poll()); }Deque<String> stack = new LinkedList<>();stack.offerFirst("HTML");stack.offerFirst("CSS");stack.offerFirst("JavaScript");System.out.println("\n棧彈出順序:");while (!stack.isEmpty()) {System.out.println("- " + stack.pollFirst()); }Deque<Integer> arrayQueue = new ArrayDeque<>(Arrays.asList(10, 20));arrayQueue.offer(30); System.out.println("\nArrayDeque 包裝 ArrayList 隊(duì)列:");while (!arrayQueue.isEmpty()) {System.out.println("- " + arrayQueue.poll()); }}
}
六、總結(jié)與注意事項(xiàng)
1. 數(shù)據(jù)結(jié)構(gòu)決定性能:
- ArrayList 適合 “讀多寫少” 場景,尤其隨機(jī)訪問頻繁時(shí)。
- LinkedList 適合 “寫多讀少” 場景,尤其需要隊(duì)列 / 棧操作時(shí)。
2. 隊(duì)列操作的最佳實(shí)踐:
- 優(yōu)先使用 LinkedList 或 ArrayDeque 實(shí)現(xiàn)隊(duì)列 / 棧,而非包裝 ArrayList。
- ArrayDeque 的性能通常優(yōu)于 LinkedList,因數(shù)組連續(xù)存儲(chǔ)減少內(nèi)存跳轉(zhuǎn)。
3. 線程安全:
- 兩者均非線程安全,多線程環(huán)境需用 Collections.synchronizedList() 包裝或使用 CopyOnWriteArrayList。
通過理解兩者的底層實(shí)現(xiàn)與方法特性,可根據(jù)業(yè)務(wù)場景(如數(shù)據(jù)訪問模式、操作頻率)選擇更合適的集合類,優(yōu)化程序效率。