ArrayList 与 LinkedList

一、底层数据结构概览

对比项	ArrayList	LinkedList
底层实现	动态数组（Object[]）	双向链表（Node 节点）
内存布局	连续内存，缓存友好	节点分散，需额外 prev/next
随机访问	支持，O(1)	需遍历，O(n)
头尾增删	尾插 O(1) 摊销，头插/删 O(n)	头尾 O(1)

---

二、ArrayList 关键源码与代码讲解

2.1 核心字段（JDK 源码中的关键定义）

// 存储元素的数组，未序列化（序列化时按元素写出）
transient Object[] elementData;

// 当前元素个数（并非 elementData.length）
private int size;

// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;

• elementData 长度 ≥ size，多余空间为“空位”，便于后续 add 少扩容。
• 无参构造时，JDK 8 中先将 elementData 赋值为空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在第一次 add 时才扩容到默认容量 10，避免创建时即分配 10 个空位。

2.2 扩容：grow / grow 策略

容量不足时会在 add 里触发 grow()，核心逻辑可概括为：

// 新容量 = 旧容量 + (旧容量 >> 1)，即约 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再与 minCapacity 取 max，保证至少满足当前 add 所需
newCapacity = Math.max(newCapacity, minCapacity);

因此：每次扩容约 1.5 倍，均摊后单次 add 的代价为 O(1)，但单次扩容最坏 O(n)。

2.3 添加元素：add(E e) 与 add(int index, E e)

尾部添加 add(E e)：不移动已有元素，仅可能触发一次扩容，时间复杂度 O(1) 均摊。

// 逻辑等价于（便于理解）
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 确保至少 size+1 容量，必要时 grow
    elementData[size++] = e;
    return true;
}

指定下标添加 add(int index, E e)：需要把 [index, size) 整体后移一位，再写入 elementData[index]，O(n)。

// 示例：在 index 处插入，后续元素后移
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 按索引访问与删除

get(int index)：直接 elementData[index]，O(1)。

remove(int index)：用 System.arraycopy 把 [index+1, size) 前移一位，O(n)；越靠前移动越多。

// 删除 index 处元素：后面一段整体前移
E oldValue = elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
    System.arraycopy(elementData, index + 1, elementData, index, numMoved);
elementData[--size] = null;  // 置空便于 GC
return oldValue;

2.5 简单使用示例

ArrayList<String> list = new ArrayList<>();
list.add("A");           // 尾插 O(1)
list.add("B");
list.add(0, "头");       // 头插：移动 2 个元素 O(n)
System.out.println(list.get(1));  // "A"，O(1)
list.remove(0);          // 删头：移动 2 个元素 O(n)

---

三、LinkedList 关键源码与代码讲解

3.1 节点结构：Node

LinkedList 是双向链表，每个节点由私有静态内部类 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;
        this.prev = prev;
    }
}

• prev / next 实现双向链接，便于从首尾或中间做增删。

3.2 首尾引用与长度

transient Node<E> first;   // 头节点
transient Node<E> last;    // 尾节点
transient int size;

• 头尾增删只需改 first/last 及相邻节点的引用，不需要像 ArrayList 那样移动整段元素。

3.3 尾插：linkLast(E e)

add(E e) 默认在尾部插入，内部调用 linkLast：

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; // 原 last 的 next 指向新节点
    size++;
    modCount++;
}

• 只涉及常数个引用修改，O(1)。
• 头插对应 linkFirst，同样 O(1)。

3.4 按索引访问：get(int index)

LinkedList 没有数组下标，需要从 first 或 last 出发遍历到第 index 个节点。源码中会根据 index 与 size/2 比较，决定从前还是从后遍历，但时间复杂度仍为 O(n)。

// 逻辑：若 index 在前半段则从 first 往后找，否则从 last 往前找
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;
    }
}

• getFirst() / getLast() 直接读 first.item / last.item，为 O(1)。

3.5 删除节点：unlink(Node x)

删除已知节点 x 只需改其前驱和后继的引用，O(1)（但“找到该节点”若按 index 找仍是 O(n)）：

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null)   first = next;
    else               prev.next = next;

    if (next == null)   last = prev;
    else               next.prev = prev;

    x.item = null;
    x.next = null;
    x.prev = null;
    size--;
    modCount++;
    return element;
}

3.6 简单使用示例

LinkedList<String> list = new LinkedList<>();
list.add("A");              // 尾插 O(1)
list.addFirst("头");        // 头插 O(1)
list.addLast("尾");         // 等价 add，O(1)
list.get(1);                // 需遍历，O(n)
list.getFirst();            // O(1)
list.removeFirst();         // 头删 O(1)
list.remove(1);             // 按索引删：先 node(1) O(n)，再 unlink O(1)

---

四、性能对比小结

操作	ArrayList	LinkedList
get(index)	O(1)	O(n)
getFirst/getLast	需通过 get(0)/get(size-1)	O(1)
add(E) 尾插	O(1) 均摊	O(1)
add(0, E) 头插	O(n)	O(1)
add(index, E)	O(n)	找节点 O(n)+插入 O(1)
remove(index)	O(n)	找节点 O(n)+删除 O(1)
remove(头/尾)	头 O(n)，尾 O(1)	O(1)

• ArrayList：实现 RandomAccess，适合随机访问多、尾部增删多的场景；可预估大小时尽量指定初始容量，减少扩容。
• LinkedList：实现 Deque，适合头尾增删多、按索引访问少的场景（如队列、栈、双端队列式用法）。

---

五、使用场景建议

1. 以遍历、按索引访问为主：用 ArrayList，CPU 缓存友好，实现简单。
2. 频繁在头/尾做增删、很少按 index 访问：用 LinkedList（或直接使用 ArrayDeque 作队列/栈，往往比 LinkedList 更省内存、更快）。
3. 既有随机访问又有头尾增删：看比例；若以访问为主仍选 ArrayList；若以头尾操作为主可考虑 LinkedList 或 ArrayDeque。
4. 线程安全：二者均非线程安全，需要时用 Collections.synchronizedList 或 CopyOnWriteArrayList 等。

---

六、小结

• ArrayList：动态数组，扩容约 1.5 倍；随机访问 O(1)，尾部 add O(1) 均摊，中间/头部增删 O(n)。
• LinkedList：双向链表，头尾增删 O(1)，按 index 访问/增删需先遍历到节点 O(n)。
• 选择时根据“访问多还是头尾增删多”与“是否需随机访问”即可做出取舍；日常大部分“列表”场景 ArrayList 更合适，队列/栈场景可优先考虑 ArrayDeque。