ArrayList vs LinkedList 详解

ArrayList 和 LinkedList 是最常用的 List 实现，理解它们的差异对性能优化至关重要。

一、核心差异

1.1 底层结构

ArrayList = 动态数组

[0] [1] [2] [3] [4] ...
连续内存，支持随机访问

LinkedList = 双向链表

node1 <-> node2 <-> node3
离散内存，只能顺序访问

1.2 性能对比

二、ArrayList 详解

2.1 源码结构

public class ArrayList<E> extends AbstractList<E> {
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 存储数组
    transient Object[] elementData;
    
    // 实际大小
    private int size;
}

2.2 扩容机制

// 扩容规则
newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5 倍

// 示例
10 → 15 → 22 → 33 → 49 ...

// 源码
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.3 添加元素

// 尾部添加（快）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

// 指定位置添加（慢）
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    
    // 移动元素
    System.arraycopy(elementData, index, 
                     elementData, index + 1, 
                     size - index);
    
    elementData[index] = element;
    size++;
}

2.4 随机访问

// O(1) 时间复杂度
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

三、LinkedList 详解

3.1 源码结构

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable {
    
    // 节点数
    transient int size;
    
    // 头节点
    transient Node<E> first;
    
    // 尾节点
    transient Node<E> last;
    
    // 节点结构
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

3.2 添加元素

// 尾部添加
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));
}

3.3 查找节点

// 优化：从近的一端开始查找
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;
    }
}

四、性能测试

4.1 随机访问

// 测试代码
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

// 填充数据
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

// 随机访问
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.get(i);
}
System.out.println("ArrayList get: " + (System.currentTimeMillis() - start) + "ms");
// 约 5ms

start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.get(i);
}
System.out.println("LinkedList get: " + (System.currentTimeMillis() - start) + "ms");
// 约 5000ms

// ArrayList 快 1000 倍！

4.2 尾部添加

// 尾部添加
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    arrayList.add(i);
}
System.out.println("ArrayList add: " + (System.currentTimeMillis() - start) + "ms");
// 约 10ms

start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    linkedList.add(i);
}
System.out.println("LinkedList add: " + (System.currentTimeMillis() - start) + "ms");
// 约 8ms

// 两者相当

4.3 中间插入

// 中间插入
int mid = 50000;
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    arrayList.add(mid, i);
}
System.out.println("ArrayList add(mid): " + (System.currentTimeMillis() - start) + "ms");
// 约 500ms

start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    linkedList.add(mid, i);
}
System.out.println("LinkedList add(mid): " + (System.currentTimeMillis() - start) + "ms");
// 约 300ms

// LinkedList 稍快（不需要移动元素）

五、适用场景

5.1 选择 ArrayList

// ✅ 场景 1：随机访问频繁
List<User> users = new ArrayList<>();
User user = users.get(index);

// ✅ 场景 2：读多写少
List<String> configList = new ArrayList<>();
// 初始化后很少修改

// ✅ 场景 3：内存敏感
List<Integer> numbers = new ArrayList<>();
// 比 LinkedList 节省内存

5.2 选择 LinkedList

// ✅ 场景 1：频繁头尾操作
Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
deque.removeFirst();

// ✅ 场景 2：频繁中间插入/删除
// 已知位置，不需要查找
ListIterator<String> it = list.listIterator(index);
it.add("new element");

// ✅ 场景 3：实现队列/栈
Queue<String> queue = new LinkedList<>();
queue.offer("a");
queue.poll();

5.3 不推荐 LinkedList

// ❌ 随机访问
for (int i = 0; i < list.size(); i++) {
    list.get(i); // O(n)，性能差
}

// ✅ 改为迭代器
for (String s : list) {
    // O(1)
}

六、最佳实践

6.1 初始化容量

// ArrayList 指定初始容量，避免扩容
List<String> list = new ArrayList<>(1000);

// 使用 Collections.nCopies
List<String> list = new ArrayList<>(Collections.nCopies(1000, ""));

6.2 批量添加

// 使用 addAll，减少扩容次数
List<String> list = new ArrayList<>(source.size());
list.addAll(source);

6.3 遍历时删除

// ❌ 错误：ConcurrentModificationException
for (String s : list) {
    if ("remove".equals(s)) {
        list.remove(s);
    }
}

// ✅ 正确：迭代器
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if ("remove".equals(it.next())) {
        it.remove();
    }
}

// ✅ Java 8：removeIf
list.removeIf(s -> "remove".equals(s));

6.4 空列表优化

// 使用空列表
List<String> empty = Collections.emptyList();
// 优于 new ArrayList<>()

// 单元素列表
List<String> single = Collections.singletonList("one");

七、总结

ArrayList vs LinkedList 核心对比：

默认选择 ArrayList，特殊场景（频繁头尾操作、实现队列）再用 LinkedList。