Java中ArrayList和LinkedList的比较

注：Joshua Bloch 就是 LinkedList 的作者

在Java中，ArrayList和LinkedList都是常用的列表实现类，它们都实现了List接口，但在内部工作原理和性能方面有显著差异。

• ArrayList：基于动态数组实现。随着元素的增加，数组的大小会动态调整。如果数组容量不足时，会分配一个新的更大的数组并复制元素。
• LinkedList：基于双向链表实现。每个元素是一个节点，包含指向前后元素的引用。

访问速度

• ArrayList：支持通过索引进行随机访问（get(int index)），由于是基于数组，所以访问速度很快，时间复杂度为O(1)。
• LinkedList：随机访问时，需要从头部或尾部遍历链表，时间复杂度为O(n)，因此访问速度较慢。

内存消耗

• ArrayList：由于是数组实现，元素仅存储数据，因此内存利用率较高，但在动态扩容时可能会浪费一些内存。
• LinkedList：每个节点不仅存储数据，还存储两个引用（前一个和后一个节点），因此需要更多的内存。

关于 ArrayList 和 LinkedList 在添加 (add) 和删除 (remove) 操作上的性能比较，传统观点认为由于 ArrayList 需要移动数据，而 LinkedList 只需调整链表指针，因此 LinkedList 更快。然而，实际性能并不是这么简单，两者在不同情况下的表现差异较大，

ArrayList中的随机访问、添加和删除部分源码如下：

// 获取 index 位置的元素值
public E get(int index) {
    rangeCheck(index); // 首先判断 index 的范围是否合法

    return elementData(index); // 返回 elementData 数组中 index 位置的元素
}

// 将 index 位置的值设为 element，并返回原来的值
public E set(int index, E element) {
    rangeCheck(index); // 检查索引的有效性

    E oldValue = elementData(index); // 保存旧值
    elementData[index] = element; // 将新值 element 赋给 elementData 数组的 index 位置
    return oldValue; // 返回旧值
}

// 将 element 添加到 ArrayList 的指定位置
public void add(int index, E element) {
    rangeCheckForAdd(index); // 检查索引是否适合添加操作

    ensureCapacityInternal(size + 1);  // 确保内部容量足够存储新增的元素，并增加 modCount
    // 将 index 及其后的数据复制到 index+1 的位置，即从 index 开始向后挪了一位
    System.arraycopy(elementData, index, elementData, index + 1, size - index); 
    elementData[index] = element; // 在 index 处插入 element
    size++; // 增加列表大小
}

// 删除 ArrayList 指定位置的元素
public E remove(int index) {
    rangeCheck(index); // 检查索引的有效性

    modCount++; // 增加 modCount
    E oldValue = elementData(index); // 记录被移除元素的旧值

    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 向左挪一位，index 位置原来的数据已经被覆盖
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    // 清空最后一个元素
    elementData[--size] = null; 

    return oldValue; // 返回被移除的旧值
}

  LinkedList中的随机访问、添加和删除部分源码如下：

// 获得第 index 个节点的值
public E get(int index) {
    checkElementIndex(index); // 检查索引的有效性
    return node(index).item; // 返回第 index 个节点的值
}

// 设置第 index 个元素的值
public E set(int index, E element) {
    checkElementIndex(index); // 检查索引的有效性
    Node<E> x = node(index); // 定位到第 index 个节点
    E oldVal = x.item; // 保存旧值
    x.item = element; // 设置新值
    return oldVal; // 返回旧值
}

// 在 index 个节点之前添加新的节点
public void add(int index, E element) {
    checkPositionIndex(index); // 检查索引的有效性
    
    if (index == size) {
        linkLast(element); // 如果在末尾添加，直接调用 linkLast 方法
    } else {
        linkBefore(element, node(index)); // 否则，在指定位置之前添加新节点
    }
}

// 删除第 index 个节点
public E remove(int index) {
    checkElementIndex(index); // 检查索引的有效性
    return unlink(node(index)); // 删除指定节点并返回旧值
}

// 定位 index 处的节点
Node<E> node(int index) {
    // assert isElementIndex(index); // 断言索引的有效性
    // 当 index < size / 2 时，从头开始查找
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else { // 当 index >= size / 2 时，从尾部开始查找
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}

• 随机访问（get 和 set）：ArrayList 远远优于 LinkedList。ArrayList 能在 O(1) 的时间复杂度内完成，而 LinkedList 的查找时间复杂度是 O(n)，性能远不如 ArrayList。
• 插入和删除：这两种操作的性能没有简单的结论。对于 ArrayList，如果插入或删除发生在数组的末尾，操作效率非常高（O(1)）；但是如果操作发生在数组的中间或开头，则需要移动大量元素（O(n)）。LinkedList 的插入和删除操作在理论上更快（O(1)），但由于需要遍历链表查找目标位置，因此查找阶段（O(n)）会拖慢整体性能。对于插入或删除操作，LinkedList 在极端情况下（如频繁在中间插入或删除）可能优于 ArrayList，但通常两者的效率没有明显的优劣。

下面通过程序来测试一下两者插入的速度：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 列表插入测试类
 * 本类用于测试在不同类型的列表（ArrayList和LinkedList）中插入元素的性能
 */
public class ListInsertionTest {

    /**
     * 插入测试方法，在指定索引位置插入元素
     * 
     * @param list 待测试的列表
     * @param insertions 插入的元素数量
     * @param index 插入的索引位置
     * @param listType 列表类型，用于输出信息
     */
    private static void testInsertion(List<Integer> list, int insertions, int index, String listType) {
        long startTime = System.nanoTime();

        // 在指定索引位置插入元素
        for (int i = 0; i < insertions; i++) {
            list.add(index, i);
        }

        long endTime = System.nanoTime();
        long duration = (endTime - startTime) / 1_000_000; // 转换为毫秒
        System.out.println(listType + " 在 index=" + index + " 插入 " + insertions + " 个元素，耗时: " + duration + " 毫秒");
    }

    public static void main(String[] args) {
        int initialSize = 10_000; // 初始容量
        int insertions = 10_000;  // 插入的元素数量

        // 初始化 ArrayList 和 LinkedList
        List<Integer> arrayList = new ArrayList<>(initialSize);
        List<Integer> linkedList = new LinkedList<>();

        // 初始化数据，使得列表的初始容量为 initialSize
        for (int i = 0; i < initialSize; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // 测试 ArrayList
        System.out.println("ArrayList:");
        testInsertion(arrayList, insertions, 1000, "ArrayList");  // 在 index=1000 处插入
        testInsertion(arrayList, insertions, 5000, "ArrayList");  // 在 index=5000 处插入
        testInsertion(arrayList, insertions, 9000, "ArrayList");  // 在 index=9000 处插入

        // 测试 LinkedList
        System.out.println("\nLinkedList:");
        testInsertion(linkedList, insertions, 1000, "LinkedList");  // 在 index=1000 处插入
        testInsertion(linkedList, insertions, 5000, "LinkedList");  // 在 index=5000 处插入
        testInsertion(linkedList, insertions, 9000, "LinkedList");  // 在 index=9000 处插入
    }
}

ArrayList:
ArrayList 在 index=1000 插入 10000 个元素，耗时: 17 毫秒
ArrayList 在 index=5000 插入 10000 个元素，耗时: 21 毫秒
ArrayList 在 index=9000 插入 10000 个元素，耗时: 29 毫秒

LinkedList:
LinkedList 在 index=1000 插入 10000 个元素，耗时: 21 毫秒
LinkedList 在 index=5000 插入 10000 个元素，耗时: 77 毫秒
LinkedList 在 index=9000 插入 10000 个元素，耗时: 148 毫秒

从测试结果来看，ArrayList 在不同插入位置的性能表现明显优于 LinkedList。

• ArrayList 在进行插入操作时，即使是插入到中间和靠后的位置，仍然表现出较为稳定和较快的速度。
• LinkedList 的插入操作在前半部分表现较好，但随着插入位置的增加，性能迅速下降，不适合在长列表中频繁插入大量数据。

根据测试结果，ArrayList 更适合在大多数情况下的插入操作。