从源码看 ArrayList 与 LinkedList 的性能差异

只要下标合法，就能在常数时间内获取元素，这是数组天生的优势。

LinkedList 的随机访问：需要从首节点或尾节点开始遍历，源码如下：

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
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;
    }
}

虽然做了优化（判断 index 靠近头部还是尾部，减少遍历次数），但最坏情况下仍需遍历半个链表，时间复杂度为 O(n)。

结论：频繁随机访问场景，ArrayList 性能碾压 LinkedList。

新增：头部/中间插入 LinkedList 优，尾部插入 ArrayList 更稳

新增操作的性能差异，主要体现在是否需要移动元素和扩容成本。

ArrayList 新增元素：

• 尾部新增：如果数组未扩容，直接赋值，时间复杂度 O(1)；如果需要扩容，会触发 grow() 方法，将原数组复制到新数组，时间复杂度变为 O(n)。

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length) elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

• 中间/头部新增：需要将插入位置后的所有元素向后移动一位，时间复杂度 O(n)，源码如下：

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length) elementData = grow();
    System.arraycopy(elementData, index, elementData, index + 1, s - index);
    elementData[index] = element;
    size = s + 1;
}

LinkedList 新增元素：

• 尾部新增：直接将新节点设为 last，原 last 的 next 指向新节点，时间复杂度 O(1)

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++;
}

• 中间/头部新增：只需找到对应节点，改变前后指针指向，无需移动元素，时间复杂度 O(1)（但查找插入位置需要 O(n) 时间）

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size) linkLast(element);
    else linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null) first = newNode;
    else pred.next = newNode;
    size++;
    modCount++;
}

结论：

1. 频繁在列表头部/中间插入元素，LinkedList 更优（前提是已找到插入位置）；
2. 仅在尾部新增元素，ArrayList 性能更稳定（无扩容时 O(1)，扩容时 O(n)）。

删除：逻辑与新增对称，LinkedList 仍有优势

删除操作的性能逻辑和新增类似，核心差异还是元素移动 vs 指针修改。

ArrayList 删除元素：

• 尾部删除：直接将对应位置置为 null，时间复杂度 O(1)；
• 中间/头部删除：需要将删除位置后的元素向前移动一位，时间复杂度 O(n)，源码如下：

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;
    @SuppressWarnings("unchecked")
    E oldValue = (E) es[index];
    fastRemove(es, index);
    return oldValue;
}
private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i) System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null; // clear to let GC do its work
}

LinkedList 删除元素：只需改变对应节点的前后指针，时间复杂度 O(1)（同样，查找待删除节点需要 O(n) 时间）：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
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;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null; // help GC
    size--;
    modCount++;
    return element;
}

结论：删除操作的性能差异与新增一致，LinkedList 在非尾部删除时更有优势。

修改：ArrayList O(1)，LinkedList O(n)

修改操作的核心是定位元素 + 赋值：

• ArrayList 直接通过下标定位元素，赋值即可，时间复杂度 O(1)；
• LinkedList 需要先遍历找到对应节点，再修改 item 值，时间复杂度 O(n)。

ArrayList 修改源码：

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

LinkedList 修改源码：

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

结论：修改操作 ArrayList 性能远优于 LinkedList。

内存占用：ArrayList 更紧凑，LinkedList 节点开销大

内存占用也是选型的重要参考，尤其是在存储大量数据时。

ArrayList：连续内存，浪费可控

ArrayList 的内存开销主要是数组本身的占用 + 少量扩容预留空间。数组是连续存储的，没有额外指针开销，内存利用率高。即使扩容时会预留一些空间（默认扩容为原容量的 1.5 倍），但这个浪费是可控的。

LinkedList：每个节点额外存储两个指针

LinkedList 的每个节点都要存储 prev 和 next 两个指针，对于存储大量小对象（如 Integer、Short 等）的场景，指针的内存开销甚至会超过数据本身。例如存储 1000 个 Integer 对象，ArrayList 仅需存储 1000 个对象引用，而 LinkedList 需要存储 1000 个对象引用 + 2000 个指针，内存开销明显更大。

选型建议：场景优先，拒绝教条

看完以上分析，我们可以结合实际场景给出选型建议：

优先选择 ArrayList 的场景

1. 频繁进行随机访问（get/set 操作）；
2. 数据量较大，对内存占用敏感；
3. 元素主要在尾部新增/删除，或新增删除操作较少；
4. 需要与数组进行频繁转换（ArrayList 的 toArray() 方法效率很高）。

优先选择 LinkedList 的场景

1. 频繁在列表头部或中间进行新增/删除操作；
2. 不需要随机访问，仅需按顺序遍历（迭代器遍历两者性能相近）；
3. 数据量较小，且需要频繁调整元素位置（如队列、栈场景，LinkedList 可直接实现 Deque 接口）。

总结：底层结构决定性能上限

ArrayList 和 LinkedList 的性能差异，本质是数组和双向链表两种数据结构的特性差异。数组的连续存储带来了高效的随机访问，但也有扩容和元素移动的开销；链表的分散存储让增删操作更灵活，但随机访问效率低下，且内存开销更大。

在实际开发中，不要迷信'ArrayList 比 LinkedList 快'的教条，而是要结合具体场景的核心操作（是随机访问多还是增删多）、数据量大小等因素综合判断。希望本文的源码分析能帮你打破认知误区，在 Java 集合选型上做到胸有成竹。