Java集合框架深入解析：ArrayList & LinkedList

Java集合框架深入解析：ArrayList & LinkedList

一、 ArrayList 深度解析

核心定义

ArrayList 是基于动态数组实现的有序集合，核心特点：

• 数组是 “定长” 的，但 ArrayList 通过「扩容机制」实现 “动态”；
• JDK8 中无参构造的 ArrayList，初始化时底层数组是空数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA），首次添加元素时才会扩容为 10；
• 数组的优势：随机访问快（通过索引直接定位，时间复杂度 O (1)）；
• 数组的劣势：增删慢（需要移动元素）、扩容有成本（复制数组）。

1. 底层数组实现机制

1.1 数据结构核心

// ArrayList 核心字段,他和Linkedlist都继承了List<E>接口。

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

// 实际存储数据的数组
transient Object[] elementData; // 关键：非私有，包内可见

// 当前元素数量
private int size;

// 空数组（优化内存）
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
}

1.2 数组特性深入

内存连续性优势：

// 内存连续性优势
public class MemoryLayoutDemo {
public static void main(String[] args) {
// ArrayList：内存连续
// 内存地址：0x1000 [元素1], 0x1004 [元素2], 0x1008 [元素3]
// CPU缓存一次加载连续内存块（通常是64字节）

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add(i);
}

// 访问时：CPU预取后续元素到缓存
// 第一次访问 index=0 时，可能把 0-15 都加载到缓存
// 后续访问 index=1~15 时命中缓存，速度极快

// 对比 LinkedList：内存分散，缓存不友好
}
}

2. 扩容机制深度剖析

2.1 扩容流程详解

// 完整的扩容过程
private void grow(int minCapacity) {
// 1. 记录旧容量
int oldCapacity = elementData.length;

// 2. 计算新容量（核心：1.5倍）
int newCapacity = oldCapacity + (oldCapacity >> 1); // 位运算：右移1位=除以2

// 3. 特殊情况处理
if (newCapacity – minCapacity < 0) // 如果1.5倍还不够
newCapacity = minCapacity; // 直接使用所需容量

// 4. 处理最大容量
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);

// 5. 数组复制（真正的扩容操作）
elementData = Arrays.copyOf(elementData, newCapacity);
}

扩容触发条件：当添加元素时，数组的实际元素个数（size）等于数组容量（elementData.length），触发扩容。

oldCapacity >> 1 相当于 “位级写法”的 oldCapacity / 2（效率更高），但有三点要注意：

所以看到

int newCapacity = oldCapacity + (oldCapacity >> 1);

就是

新容量 = 原容量 + 原容量 / 2 ≈ 1.5 倍

这是 ArrayList 扩容时“平滑 1.5 倍”的写法，比直接 / 2 快一点点，习惯上炫技 ,哈哈。

2.2 扩容过程可视化

初始：容量=10，size=0
添加过程：
1. 添加第1个元素：容量10，size=1
2. 添加第11个元素时触发扩容：
oldCapacity = 10
newCapacity = 10 + (10 >> 1) = 10 + 5 = 15
→ 扩容到15，复制原数组

3. 添加第16个元素时再次扩容：
oldCapacity = 15
newCapacity = 15 + (15 >> 1) = 15 + 7 = 22
→ 扩容到22，复制原数组

容量增长序列：10 → 15 → 22 → 33 → 49 → 73 → 109 → …

2.3 扩容性能影响

public class ExpansionCostDemo {
public static void main(String[] args) {
// 测试扩容开销
int testSize = 10000000;

// 情况1：不指定容量（频繁扩容）
long start1 = System.nanoTime();
List<Integer> list1 = new ArrayList<>();
for (int i = 0; i < testSize; i++) {
list1.add(i);
}
long end1 = System.nanoTime();

// 情况2：指定容量（避免扩容）
long start2 = System.nanoTime();
List<Integer> list2 = new ArrayList<>(testSize);
for (int i = 0; i < testSize; i++) {
list2.add(i);
}
long end2 = System.nanoTime();

System.out.printf("未预分配：%.2f ms\\n", (end1 – start1) / 1_000_000.0);
System.out.printf("预分配：%.2f ms\\n", (end2 – start2) / 1_000_000.0);

// 结果可能相差数倍！因为数组复制开销很大
}
}

3. Fail-Fast 机制深度解析

核心定义

fail-fast 是 Java 集合（如 ArrayList、LinkedList、HashMap 等）的错误检测机制，是迭代器的错误检测机制，不是集合的 “功能”，目的是避免数据不一致，且不保证 100% 触发（仅作快速失败提示）。

迭代器遍历 ArrayList 时，若检测到集合被「并发修改」（比如遍历中 add/remove），立即抛出 ConcurrentModificationException，这是一种 “快速失败” 的检测机制，而非线程安全机制。

3.1 机制原理

• ArrayList 有个成员变量 modCount：记录集合被修改的次数（调用集合的add/remove等方法 都会让modCount++）；
• 迭代器创建时，会记录当前的modCount到expectedModCount；
• 遍历过程中，每次next()都会检查 modCount == expectedModCount，不相等则抛异常。

// modCount 机制
public class FailFastDemo {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

// 创建迭代器时记录 expectedModCount = modCount
Iterator<String> iterator = list.iterator();

// 迭代过程中修改列表
while (iterator.hasNext()) {
String item = iterator.next();
System.out.println(item);

if (item.equals("B")) {
// 这里修改列表，modCount++
list.remove(item); // 触发 modCount++（因为这里用的是列表的remove函数，不是迭代器的，此时迭代器会认为外部有人恶意篡改数据，导致脏读。如果用迭代器里的remove函数就不会报错。）
// iterator.next() 会检查：
// if (modCount != expectedModCount)
// throw new ConcurrentModificationException();
}
}
}
}

• modCount = 列表被结构改动的总次数（ArrayList 的“版本号”）
• expectedModCount = 迭代器诞生那一刻拍下来的快照（迭代器眼里的“当前版本号”）

3.2 源码实现细节

// ArrayList.Itr 迭代器实现
private class Itr implements Iterator<E> {
int cursor; // 下一个返回元素的索引
int lastRet = –1; // 上一个返回元素的索引
int expectedModCount = modCount; // 关键！记录创建时的modCount（相当于拍照，为了比较列表是否被动过。）

public boolean hasNext() {
return cursor != size;
}

@SuppressWarnings("unchecked")
public E next() {
checkForComodification(); // 每次next都检查
// … 其他逻辑
}

public void remove() {
// 迭代器自己的remove会同步modCount
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = –1;
expectedModCount = modCount; // 更新expectedModCount
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}

3.3 Fail-Fast 应用场景

public class ConcurrentModificationCase {
// 场景1：单线程错误用法
public void wrongSingleThread() {
//在初始化ArrayList的时候就存入数组{"A","B","C","D"}
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C","D"));
for (String s : list) { // 内部使用迭代器
if (s.equals("B")) {
list.remove(s); //会报错,用的是ArrayList自己的remove方法，抛出ConcurrentModificationException
}
}
}

// 场景2：多线程并发修改
public void multiThreadIssue() {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

Thread t1 = new Thread(() -> {
Iterator<String> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next());
try { Thread.sleep(100); } catch (InterruptedException e) {}
}
});

Thread t2 = new Thread(() -> {
try { Thread.sleep(50); } catch (InterruptedException e) {}
list.add("D"); // 在迭代过程中修改，抛出ConcurrentModificationException
});

t1.start();
t2.start();
}

// 正确做法
public void correctApproach() {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

// 方法1：使用迭代器的remove方法
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if (item.equals("B")) {
iterator.remove(); // 正确！会更新expectedModCount
}
}

// 方法2：使用CopyOnWriteArrayList（并发安全）
// List<String> safeList = new CopyOnWriteArrayList<>(list);

// 方法3：使用并发集合
// List<String> concurrentList = Collections.synchronizedList(list);
}
}

场景一中注释“内部使用迭代器”指的是：
编译器把那句看似简单的

for (String s : list) { … }

偷偷翻译成了带有 Iterator 对象的经典三件套：

for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
String s = it.next();
…
}

你写的“增强 for 循环”只是语法糖，字节码里跑的就是迭代器。
因此：

场景二中线程的操作：

线程一先打印出第一个遍历到的元素，然后休眠50毫秒，，此时线程二几乎也同时休眠了50毫秒。然后线程二会进行增加元素的操作，但此时线程一开始next()，如果此时线程一比线程二稍快，也就是线程二增加元素操作慢了一拍的话，线程一next()时候expectedModCount 仍然等于 modCount，此时不会报错，但是等到下一次next()的时候仍然会抛出异常。

所以，经过上面的分析，总结一句：异常是否抛出取决于“迭代器是否还会再检查一次”

4. ArrayList 面试高频问答

二、 LinkedList 深度解析

1. 双向链表结构详解

LinkedList 是基于双向链表实现的有序集合，核心结构：

1.1 节点结构深入

• 每个节点是一个Node对象，包含 3 个属性：

// Node 类的完整理解
private static class Node<E> {
E item; // 实际存储的数据
Node<E> next; // 后继指针：指向下一个节点
Node<E> prev; // 前驱指针：指向前一个节点

// 构造函数：创建时建立双向链接
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; // 把自己的数据域赋成传进来的元素
this.next = next; // 把自己的后继指向参数 next
this.prev = prev; // 把自己的前驱指向参数 prev

// 下面两行是反向链接：让相邻的节点也认识自己
if (prev != null) prev.next = this; // 前驱的后继 = 我自己
if (next != null) next.prev = this; // 后继的前驱 = 我自己
}
}

• LinkedList 还维护了两个哨兵节点：first（头节点）、last（尾节点），无需遍历就能快速定位头尾；
• 无固定容量，添加元素只需新建节点、修改指针，无需扩容。

1.2 链表结构可视化

public class LinkedListStructure {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();

// 添加元素的过程
list.add("A"); // 创建节点1：[null ← A → null]
list.add("B"); // 创建节点2：[A ← B → null]，并更新A.next=B
list.add("C"); // 创建节点3：[B ← C → null]，并更新B.next=C

// 最终结构：
// first → [null ← A → B] ↔ [A ← B → C] ↔ [B ← C → null] ← last
// (节点1) (节点2) (节点3)

// 双向遍历能力：
// 正向：A → B → C
// 反向：C → B → A
}
}

2. 核心操作原理

2.1 头部插入分析

// linkFirst 方法深度解析
private void linkFirst(E e) {
final Node<E> f = first; // 1. 保存原头节点

// 2. 创建新节点：prev=null, element=e, next=f（指向原头节点）
final Node<E> newNode = new Node<>(null, e, f);

first = newNode; // 3. 更新first指针

if (f == null) // 4. 原链表为空
last = newNode; // 新节点也是尾节点
else
f.prev = newNode; // 5. 原头节点的prev指向新节点

size++;
modCount++;
}

// 时间复杂度：O(1) 常数时间
// 无论链表多长，操作步骤固定

2.2 中间插入分析

// 在指定位置插入
public void add(int index, E element) {
checkPositionIndex(index);//检查传入的参数index是否在数组索引范围内

if (index == size) // 尾部插入
linkLast(element);
else
linkBefore(element, node(index)); // 关键：先找到节点
}

// node(index)：查找节点（耗时操作）
Node<E> node(int index) {
// 优化：根据位置决定从前还是从后遍历
if (index < (size >> 1)) { // 前半部分
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next; // 顺序遍历
return x;
} else { // 后半部分
Node<E> x = last;
for (int i = size – 1; i > index; i—)
x = x.prev; // 逆序遍历
return x;
}
}

// 时间复杂度：
// 查找节点：O(n/2) = O(n) 线性时间
// 插入操作：O(1) 常数时间
// 总复杂度：O(n)

还有尾部插入，指定的节点前插入…这些我都不一一讲述，有兴趣的小伙伴可以去读源码，读源码是一个很方便快捷的方式，对我们提升自身能力有很大帮助！

其实原理很简单，只要你能理解链表的结构，同时关照到每个方面，源码你也能手搓出来！嘻嘻。

3. 适用场景深度分析

场景1：频繁的头部操作

public class StackImplementation {
// LinkedList 实现栈（后进先出）
public class Stack<E> {
private LinkedList<E> list = new LinkedList<>();

public void push(E item) {
list.addFirst(item); // O(1)
}

public E pop() {
return list.removeFirst(); // O(1)
}

public E peek() {
return list.getFirst(); // O(1)
}
}

// 对比 ArrayList 实现栈
public class ArrayListStack<E> {
private ArrayList<E> list = new ArrayList<>();

public void push(E item) {
list.add(0, item); // O(n)！需要移动所有元素
}

public E pop() {
return list.remove(0); // O(n)！
}
}
}

场景2：实现队列和双端队列

public class QueueDequeDemo {
public static void main(String[] args) {
// LinkedList 实现了 Deque 接口
Deque<String> deque = new LinkedList<>();

// 作为队列使用（FIFO）
deque.offer("A"); // 入队
deque.offer("B");
System.out.println(deque.poll()); // 出队：A

// 作为双端队列使用
deque.offerFirst("C"); // 头部入队
deque.offerLast("D"); // 尾部入队
System.out.println(deque.pollFirst()); // C
System.out.println(deque.pollLast()); // D

// 作为栈使用
deque.push("E"); // 压栈
deque.push("F");
System.out.println(deque.pop()); // 弹栈：F
}
}

场景3：LRU缓存实现

public class LRUCache<K, V> {
private final int capacity;
private final Map<K, Node> cache;
private final LinkedList<Node> list;

class Node {
K key;
V value;
}

public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.list = new LinkedList<>();
}

public V get(K key) {
if (!cache.containsKey(key)) return null;

Node node = cache.get(key);
// 移动到头部（最近使用）
list.remove(node); // O(1) 知道节点位置
list.addFirst(node); // O(1)

return node.value;
}

public void put(K key, V value) {
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.value = value;
list.remove(node);
list.addFirst(node);
} else {
if (cache.size() >= capacity) {
Node last = list.removeLast(); // 移除最久未使用
cache.remove(last.key);
}
Node newNode = new Node();
newNode.key = key;
newNode.value = value;
list.addFirst(newNode);
cache.put(key, newNode);
}
}
}

场景4：大数据集的中间位置频繁修改

public class TextEditor {
// 模拟文本编辑器：光标位置频繁插入删除
private LinkedList<Character> text = new LinkedList<>();
private ListIterator<Character> cursor;

public TextEditor() {
cursor = text.listIterator();
}

// 插入字符
public void insertChar(char c) {
cursor.add(c); // O(1) 在迭代器位置插入
}

// 删除字符
public void deleteChar() {
if (cursor.hasPrevious()) {
cursor.previous();
cursor.remove(); // O(1) 删除当前字符
}
}

// 移动光标
public void moveCursorForward() {
if (cursor.hasNext()) cursor.next(); // O(1)
}

public void moveCursorBackward() {
if (cursor.hasPrevious()) cursor.previous(); // O(1)
}
}

4. LinkedList 面试高频问答

5. 性能对比实战

import java.util.ArrayList;
import java.util.LinkedList;

/**
* ArrayList vs LinkedList 性能对比
* 测试维度：头部插入、尾部插入、随机访问、内存占用
* 结论记忆：
* 1. 头插：LinkedList 完胜（O(1) vs O(n)）
* 2. 尾插：两者 O(1) 接近，ArrayList 略快（连续内存 + 扩容公式 1.5 倍）
* 3. 随机读：ArrayList 碾压（O(1) vs O(n)）
* 4. 内存：LinkedList 额外 50% ~ 100%（每个 Node 多两个引用域）
*/
public class PerformanceComparison {

// 测试规模：10 万元素（可自行调大/调小）
private static final int SIZE = 100_000;

public static void main(String[] args) {
System.out.println("=== 头部插入性能测试 ===");
testAddFirst(SIZE);

System.out.println("\\n=== 尾部插入性能测试 ===");
testAddLast(SIZE);

System.out.println("\\n=== 随机访问性能测试 ===");
testRandomAccess(SIZE);

System.out.println("\\n=== 内存占用测试 ===");
testMemoryUsage(SIZE);
}

/* ———- 1. 头部插入 ———- */
private static void testAddFirst(int size) {
// LinkedList：linkFirst 操作，纯指针调整，O(1)
LinkedList<Integer> linkedList = new LinkedList<>();
long start = System.nanoTime();
for (int i = 0; i < size; i++) {
linkedList.addFirst(i);
}
long linkedTime = System.nanoTime() – start;

// ArrayList：每次 add(0, i) 都要整体右移，O(n)
ArrayList<Integer> arrayList = new ArrayList<>();
start = System.nanoTime();
for (int i = 0; i < size; i++) {
arrayList.add(0, i); // 灾难性性能
}
long arrayTime = System.nanoTime() – start;

printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
}

/* ———- 2. 尾部插入 ———- */
private static void testAddLast(int size) {
// LinkedList：linkLast 操作，O(1)
LinkedList<Integer> linkedList = new LinkedList<>();
long start = System.nanoTime();
for (int i = 0; i < size; i++) {
linkedList.addLast(i);
}
long linkedTime = System.nanoTime() – start;

// ArrayList：默认 append，平均 O(1)（偶尔扩容）
ArrayList<Integer> arrayList = new ArrayList<>();
start = System.nanoTime();
for (int i = 0; i < size; i++) {
arrayList.add(i); // 等价 addLast
}
long arrayTime = System.nanoTime() – start;

printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
}

/* ———- 3. 随机访问 ———- */
private static void testRandomAccess(int size) {
// 预填充数据，避免插入耗时干扰
LinkedList<Integer> linkedList = new LinkedList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) {
linkedList.add(i);
arrayList.add(i);
}

// 生成同一批随机下标，保证公平
int[] indices = new int[size];
java.util.Random r = new java.util.Random(0);
for (int i = 0; i < size; i++) indices[i] = r.nextInt(size);

// LinkedList：每次 get 都要从最近端遍历，平均 O(n)
long start = System.nanoTime();
long sum = 0; // 防止 JIT 把循环优化掉
for (int idx : indices) sum += linkedList.get(idx);
long linkedTime = System.nanoTime() – start;

// ArrayList：物理下标，直接内存偏移，O(1)
start = System.nanoTime();
sum = 0;
for (int idx : indices) sum += arrayList.get(idx);
long arrayTime = System.nanoTime() – start;

printReport("LinkedList", linkedTime, "ArrayList", arrayTime);
}

/* ———- 4. 内存占用估算 ———- */
private static void testMemoryUsage(int size) {
Runtime rt = Runtime.getRuntime();
rt.gc(); // 建议 GC，减少干扰
long before = rt.totalMemory() – rt.freeMemory();

LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < size; i++) linkedList.add(i);

rt.gc();
long after = rt.totalMemory() – rt.freeMemory();
double linkedMB = (after – before) / 1024.0 / 1024.0;

// ArrayList 测试
rt.gc();
before = rt.totalMemory() – rt.freeMemory();

ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < size; i++) arrayList.add(i);

rt.gc();
after = rt.totalMemory() – rt.freeMemory();
double arrayMB = (after – before) / 1024.0 / 1024.0;

System.out.printf("LinkedList 占用: %.2f MB\\n", linkedMB);
System.out.printf("ArrayList 占用: %.2f MB\\n", arrayMB);
System.out.printf("LinkedList 多用了 %.1f%% 内存\\n", (linkedMB – arrayMB) / arrayMB * 100);
}

/* ———- 工具：统一打印格式 ———- */
private static void printReport(String fastName, long fastTime, String slowName, long slowTime) {
System.out.printf("%s: %.2f ms\\n", fastName, fastTime / 1_000_000.0);
System.out.printf("%s: %.2f ms\\n", slowName, slowTime / 1_000_000.0);
System.out.printf("%s 是 %s 的 %.2f 倍快\\n",
fastName, slowName, (double) slowTime / fastTime);
}
}

三、选择决策树

需要频繁随机访问吗？
├── 是 → 选择 ArrayList
└── 否 → 需要频繁在头部插入/删除吗？
├── 是 → 选择 LinkedList
└── 否 → 数据量小吗？
├── 是 → 两者都可，ArrayList 通常更好
└── 否 → 需要实现队列/双端队列吗？
├── 是 → 选择 LinkedList（实现 Deque）
└── 否 → 内存敏感吗？
├── 是 → 选择 ArrayList
└── 否 → 根据具体操作模式选择

四、总结要点

ArrayList 关键点

LinkedList 关键点

实际应用建议

• 80% 场景用 ArrayList：大多数应用是读多写少
• 特殊场景用 LinkedList：明确需要队列/栈特性
• 性能关键时实测：用真实数据测试，理论可能不符合实际
• 考虑并发场景：两者都不是线程安全的，需要同步