💡 摘要：你是否曾在ArrayList和LinkedList之间犹豫不决？是否疑惑为什么有时候查询很快而插入很慢，或者反过来？
别担心，集合框架是Java中最重要且最常用的组件，而List作为最基础的集合类型，理解其实现原理至关重要。
本文将带你从Collection架构讲起，深入理解List接口的核心特性与常用方法。
接着重点剖析ArrayList的数组实现机制和自动扩容原理，然后对比LinkedList的双向链表结构及其适用场景。
最后详解Vector和Stack的线程安全特性以及为什么现在不推荐使用。从时间复杂度分析到内存布局，从迭代器模式到并发修改异常，让你彻底掌握List的实现细节。文末附性能对比和面试高频问题，助你在实际开发中做出最佳选择。
一、集合框架概述：List的定位
1. Java集合框架架构
text
Collection接口 (单列集合)
├── List接口 (有序、可重复)
│ ├── ArrayList：动态数组实现
│ ├── LinkedList：双向链表实现
│ ├── Vector：线程安全的动态数组（已过时）
│ └── Stack：栈结构（继承自Vector）
│
├── Set接口 (无序、不可重复)
│ ├── HashSet
│ ├── LinkedHashSet
│ └── TreeSet
│
└── Queue接口 (队列)
├── LinkedList
├── PriorityQueue
└── ArrayDeque
Map接口 (双列集合，键值对)
├── HashMap
├── LinkedHashMap
├── TreeMap
└── Hashtable
2. List接口核心特性
List的特点：
- ✅ 有序性：元素按插入顺序存储
- ✅ 可重复：允许存储重复元素
- ✅ 索引访问：支持通过索引快速访问元素
- ✅ null元素：允许包含null元素
核心方法：
java
// 添加元素
boolean add(E e); // 尾部添加
void add(int index, E e); // 指定位置插入
// 获取元素
E get(int index); // 根据索引获取
// 删除元素
E remove(int index); // 删除指定位置元素
boolean remove(Object o); // 删除指定元素
// 查找元素
int indexOf(Object o); // 查找元素首次出现位置
int lastIndexOf(Object o); // 查找元素最后一次出现位置
// 修改元素
E set(int index, E e); // 修改指定位置元素
// 其他操作
int size(); // 元素数量
boolean isEmpty(); // 是否为空
void clear(); // 清空所有元素
List<E> subList(int from, int to); // 获取子列表
二、ArrayList：动态数组的实现
1. 内部结构与初始化
底层实现：基于Object[]数组，支持动态扩容
java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 存储元素的数组
transient Object[] elementData;
// 元素数量
private int size;
// 构造方法
public ArrayList() {
this.elementData = new Object[DEFAULT_CAPACITY]; // 默认初始化
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; // 指定容量
} else if (initialCapacity == 0) {
this.elementData = new Object[]{}; // 空数组
} else {
throw new IllegalArgumentException("非法容量: " + initialCapacity);
}
}
}
2. 自动扩容机制
扩容原理：当数组已满时，创建新数组（通常为原容量的1.5倍）并拷贝数据
java
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保容量足够
elementData[size++] = e; // 添加元素
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 修改计数器（用于快速失败机制）
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 需要扩容
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); // 数组拷贝
}
3. 性能特点与使用场景
时间复杂度分析：
- get(int index)：O(1) - 直接数组索引访问
- add(E e)：O(1) - 平均时间复杂度（分摊后）
- add(int index, E e)：O(n) - 需要移动元素
- remove(int index)：O(n) - 需要移动元素
- contains(Object o)：O(n) - 需要遍历数组
适用场景：
- ✅ 频繁的随机访问（按索引查询）
- ✅ 尾部添加操作较多
- ❌ 频繁在中间位置插入/删除
最佳实践：
java
// 预分配容量，避免多次扩容
List<String> list = new ArrayList<>(1000); // 预计需要1000个元素
// 批量添加
Collections.addAll(list, "a", "b", "c", "d");
// 使用foreach遍历（基于迭代器）
for (String item : list) {
System.out.println(item);
}
三、LinkedList：双向链表的实现
1. 内部节点结构
底层实现：基于双向链表，每个节点包含前后指针
java
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
// 节点定义
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;
this.prev = prev;
}
}
// 头节点和尾节点
transient Node<E> first;
transient Node<E> last;
transient int size = 0;
}
内存布局：
text
first → Node1 → Node2 → Node3 → last
↓ ↓ ↓
item1 item2 item3
2. 链表操作原理
java
// 添加元素到尾部
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode; // 第一个元素
else
l.next = newNode; // 链接到链表尾部
size++;
modCount++;
}
// 在指定位置插入
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element); // 尾部插入
else
linkBefore(element, 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;
}
}
3. 性能特点与使用场景
时间复杂度分析：
- get(int index)：O(n) - 需要遍历链表
- add(E e)：O(1) - 直接修改尾部指针
- add(int index, E e)：O(n) - 需要找到插入位置
- remove(int index)：O(n) - 需要找到删除位置
- contains(Object o)：O(n) - 需要遍历链表
适用场景：
- ✅ 频繁在头部/尾部插入删除
- ✅ 实现栈、队列、双端队列
- ❌ 频繁的随机访问
作为Deque使用：
java
LinkedList<String> deque = new LinkedList<>();
// 作为队列使用（FIFO）
deque.offer("first"); // 尾部添加
deque.offer("second");
String first = deque.poll(); // 头部移除 → "first"
// 作为栈使用（LIFO）
deque.push("bottom"); // 头部添加
deque.push("top");
String top = deque.pop(); // 头部移除 → "top"
四、Vector与Stack：已过时的线程安全实现
1. Vector：同步的ArrayList
java
public class Vector<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 所有方法都使用synchronized修饰
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
}
为什么不推荐使用：
- 🔴 性能差：所有方法同步，并发性能低
- 🔴 过时的设计：有更好的并发替代方案
- 🟢 需要线程安全时，推荐用
Collections.synchronizedList()或CopyOnWriteArrayList
2. Stack：继承自Vector的栈实现
java
public class Stack<E> extends Vector<E> {
public E push(E item) { /* 入栈 */ }
public synchronized E pop() { /* 出栈 */ }
public synchronized E peek() { /* 查看栈顶 */ }
public boolean empty() { /* 是否为空 */ }
}
为什么不推荐使用：
- 🔴 继承自Vector，有同样的性能问题
- 🔴 设计不佳：栈不应该继承自动态数组
- 🟢 推荐使用
Deque接口的实现类：
java
Deque<String> stack = new ArrayDeque<>();
stack.push("a");
stack.push("b");
String top = stack.pop(); // "b"
五、性能对比与选型指南
1. 三大List实现对比
| 特性 | ArrayList | LinkedList | Vector |
| 底层结构 | 动态数组 | 双向链表 | 同步数组 |
| 随机访问 | ⭐⭐⭐⭐⭐ (O(1)) | ⭐⭐ (O(n)) | ⭐⭐⭐⭐⭐ (O(1)) |
| 头部插入 | ⭐ (O(n)) | ⭐⭐⭐⭐⭐ (O(1)) | ⭐ (O(n)) |
| 尾部插入 | ⭐⭐⭐⭐ (O(1)分摊) | ⭐⭐⭐⭐⭐ (O(1)) | ⭐⭐⭐⭐ (O(1)分摊) |
| 中间插入 | ⭐⭐ (O(n)) | ⭐⭐⭐ (O(n)) | ⭐⭐ (O(n)) |
| 内存占用 | 较小（仅数组） | 较大（每个元素额外两个指针） | 同ArrayList |
| 线程安全 | 否 | 否 | 是（但性能差） |
| 适用场景 | 随机访问频繁 | 插入删除频繁 | 已过时，不推荐 |
2. 选型建议
选择ArrayList当：
- 需要频繁按索引访问元素
- 主要在尾部添加元素
- 元素数量可以预估
选择LinkedList当：
- 需要频繁在头部/中间插入删除
- 需要实现栈、队列等数据结构
- 元素数量变化较大
永远不要直接使用Vector/Stack：
- 使用
Collections.synchronizedList(new ArrayList<>())获得线程安全 - 使用
CopyOnWriteArrayList用于读多写少的并发场景 - 使用
ArrayDeque代替Stack
六、实战技巧与常见陷阱
1. 迭代器与快速失败机制
java
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
// 错误做法：在遍历过程中修改集合
for (String item : list) {
if ("B".equals(item)) {
list.remove(item); // 抛出ConcurrentModificationException
}
}
// 正确做法：使用迭代器的remove方法
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String item = iterator.next();
if ("B".equals(item)) {
iterator.remove(); // 安全删除
}
}
2. 子列表的注意事项
java
List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
List<String> subList = original.subList(1, 3); // ["B", "C"]
// 子列表是原列表的视图，修改会相互影响
subList.set(0, "X");
System.out.println(original); // [A, X, C, D]
// 原列表结构修改后，子列表操作会失效
original.add("E");
// subList.get(0); // 抛出ConcurrentModificationException
3. 数组与集合的转换
java
// List转数组
List<String> list = Arrays.asList("A", "B", "C");
String[] array1 = list.toArray(new String[0]); // 推荐
String[] array2 = list.toArray(new String[list.size()]);
// 数组转List
String[] array = {"A", "B", "C"};
List<String> list1 = Arrays.asList(array); // 固定大小List
List<String> list2 = new ArrayList<>(Arrays.asList(array)); // 可修改List
七、总结：掌握List的精髓
- 理解底层实现：ArrayList基于数组，LinkedList基于链表
- 根据场景选择：随机访问选ArrayList，插入删除选LinkedList
- 避免线程安全陷阱：不要用Vector，用合适的并发集合
- 注意迭代安全：使用迭代器进行遍历时的修改操作
- 预分配容量：特别是ArrayList，避免频繁扩容
🚀 List是Java集合框架的基础，深入理解其实现原理和特性，是成为Java高手的重要一步。
八、面试高频问题
❓1. ArrayList和LinkedList的区别？
答：主要区别在底层数据结构：
- ArrayList基于动态数组，随机访问快O(1)，插入删除慢O(n)
- LinkedList基于双向链表，随机访问慢O(n)，插入删除快O(1)
根据具体的使用场景选择合适实现。
❓2. ArrayList的扩容机制是怎样的？
答：当数组已满时，创建新数组（通常为原容量的1.5倍），然后用Arrays.copyOf()拷贝数据。默认初始容量为10。
❓3. 如何在遍历时安全地删除元素？
答：使用Iterator的remove()方法，而不是直接调用List的remove()方法，否则会抛出ConcurrentModificationException。
❓4. Vector为什么过时了？
答：Vector的所有方法都是同步的，性能较差。现在推荐使用Collections.synchronizedList()包装ArrayList，或者使用CopyOnWriteArrayList。
❓5. Arrays.asList()得到的List有什么特点？
答：返回的是固定大小的List， backed by原数组，不能进行add/remove等结构修改操作，否则会抛出UnsupportedOperationException。
