ArrayList vs LinkedList

ArrayList 和 LinkedList 是 Java 集合框架中最常用的两个 List 实现类。理解它们的底层数据结构和性能差异，是面试和实际开发中的必备知识。

一、底层数据结构

1.1 ArrayList

ArrayList 基于动态数组实现，内部维护一个 Object[] 数组存储元素。

ArrayList 内部结构：

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │  ← 数组容量（10）
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
│ A │ B │ C │ D │ E │   │   │   │   │   │  ← 实际元素（5个）
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ↑                           ↑
  └── 元素连续存储 ────────────┘── 空闲空间

public class ArrayList<E> extends AbstractList<E> {
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;
    
    // 空数组（无参构造时使用）
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    // 存储元素的数组
    Object[] elementData;
    
    // 元素个数
    private int size;
}

1.2 LinkedList

LinkedList 基于双向链表实现，每个节点包含数据、前驱指针和后继指针。

LinkedList 内部结构：

        ┌─────────────────────────────────────────┐
        │                                         │
        ▼                                         ▼
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│   Node    │◄──│   Node    │◄──│   Node    │◄──│   Node    │
│  item: A  │──►│  item: B  │──►│  item: C  │──►│  item: D  │
│  prev: null   │  prev: ●  │   │  prev: ●  │   │  prev: ●  │
│  next: ●──┼───│  next: ●──┼───│  next: ●──┼───│  next: null
└───────────┘   └───────────┘   └───────────┘   └───────────┘
      ↑                                               ↑
      │                                               │
   first                                            last

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E> {
    
    // 元素个数
    transient int size = 0;
    
    // 头节点
    transient Node<E> first;
    
    // 尾节点
    transient Node<E> last;
    
    // 节点内部类
    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;
        }
    }
}

1.3 数据结构对比

对比项	ArrayList	LinkedList
底层数据结构	动态数组	双向链表
内存占用	连续内存，可能有浪费	分散内存，每个节点额外存储前后指针
随机访问	O(1)	O(n)
插入/删除（头部）	O(n)	O(1)
插入/删除（尾部）	O(1)（摊销）	O(1)
插入/删除（中间）	O(n)	O(n)（需先查找）
缓存友好性	高（连续内存）	低（分散内存）

二、ArrayList 扩容机制

2.1 扩容触发条件

当添加元素时，如果数组容量不足，就会触发扩容。

public boolean add(E e) {
    ensureCapacityInte

概述 HashMap