LinkedList 与 ArrayList 详细对比

Java 集合框架中的 LinkedList 和 ArrayList 是两种最常用的 List 实现，它们都实现了 List 接口，但内部结构和性能特性存在显著差异。本文将深入分析这两种数据结构的区别，并通过具体场景说明它们的最佳应用场景。

1. 基本概念

1.1 ArrayList

ArrayList 是基于动态数组实现的列表，它可以存储任意类型的对象，并且可以自动扩容。ArrayList 在 Java 集合框架中是最常用的列表实现之一。

1.2 LinkedList

LinkedList 是基于双向链表实现的列表，它不仅实现了 List 接口，还实现了 Deque 接口，因此它可以作为列表、队列或栈使用。

2. 内部实现原理

2.1 ArrayList 实现原理

ArrayList 内部使用对象数组来存储元素：

public class ArrayList<E> extends AbstractList<E> 
        implements List<E>, RandomAccess, Cloneable, Serializable {
    // 用于存储元素的数组
    transient Object[] elementData;

    // 实际元素个数
    private int size;

    // 其他代码...
}

关键特点：

• 初始容量默认为 10
• 当容量不足时，进行自动扩容（通常扩容为当前容量的 1.5 倍）
• 扩容操作涉及创建新数组并复制旧数组内容，开销较大
• 支持随机访问（通过索引直接访问元素）
• 实现了 RandomAccess 接口，表明其支持快速随机访问

2.2 LinkedList 实现原理

LinkedList 内部使用双向链表存储元素：

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable {
    // 链表大小
    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;
        }
    }

    // 其他代码...
}

关键特点：

• 每个元素存储在单独的节点中，包含前后引用
• 不需要初始容量，可以动态增长
• 不需要连续内存空间
• 不支持高效的随机访问
• 实现了 Deque 接口，可以作为双端队列使用

3. 性能特性对比

3.1 时间复杂度对比

| 操作 | ArrayList | LinkedList | 备注 |
|——|———–|————|——|
| 访问元素（get/set） | O(1) | O(n) | ArrayList 支持随机访问，LinkedList 需要遍历查找 |
| 头部添加/删除（add/remove first） | O(n) | O(1) | ArrayList 需要移动元素，LinkedList 只需修改指针 |
| 尾部添加/删除（add/remove last） | 平均 O(1)* | O(1) | ArrayList 在需要扩容时为 O(n)，通常是 O(1) |
| 中间添加/删除（add/remove at index） | O(n) | O(n) | ArrayList 需要移动元素，LinkedList 需要先遍历找到位置 |
| 搜索元素（contains/indexOf） | O(n) | O(n) | 两者都需要遍历，但 ArrayList 有更好的内存局部性 |

3.2 内存消耗对比

• ArrayList:

• 仅存储元素本身和少量管理信息

• 可能会浪费一些未使用的数组空间

• 内存连续，有更好的缓存局部性（cache locality）

• LinkedList:

• 每个元素需要额外存储两个引用（前后节点）

• 不存在未使用的空间浪费

• 内存不连续，缓存局部性较差

在相同元素数量情况下，LinkedList 通常比 ArrayList 消耗更多内存。

3.3 迭代性能

• ArrayList: 迭代性能优秀，因为内存连续，CPU缓存命中率高
• LinkedList: 迭代性能较差，因为节点分散在内存各处，缓存命中率低

3.4 并发修改

两者都不是线程安全的，在多线程环境下需要外部同步。两者都会在迭代过程中检测结构修改，并抛出 ConcurrentModificationException。

4. 功能特性对比

| 特性 | ArrayList | LinkedList |
|——|———–|————|
| 实现接口 | List, RandomAccess | List, Deque |
| 允许 null 元素 | 是 | 是 |
| 有序性 | 是（维持插入顺序） | The 是（维持插入顺序） |
| 可作为栈使用 | 可以但不推荐 | 推荐（实现了 Deque） |
| 可作为队列使用 | 可以但效率低 | 推荐（实现了 Deque） |
| 可作为双端队列 | 不适合 | 推荐（实现了 Deque） |
| 随机访问效率 | 高 | 低 |
| 序列化方式 | 默认序列化 | 默认序列化 |

5. 应用场景对比

5.1 ArrayList 适用场景

1. 频繁随机访问场景

// 适合ArrayList的场景：需要频繁通过索引访问元素
ArrayList<Customer> customers = new ArrayList<>();
// 添加大量客户记录...

// 随机访问特定索引的元素
Customer tenthCustomer = customers.get(9);  // O(1)复杂度
Customer lastCustomer = customers.get(customers.size() - 1);  // O(1)复杂度

// 高效遍历
for (int i = 0; i < customers.size(); i++) {
    processCustomer(customers.get(i));  // 每次访问都是O(1)
}

1. 元素数量相对固定，查询频繁的场景

// 适合ArrayList的场景：加载后主要用于查询的数据集
ArrayList<Product> productCatalog = new ArrayList<>();
// 初始化加载所有产品...

// 后续主要是查询操作
public List<Product> searchProductsByName(String name) {
    List<Product> results = new ArrayList<>();
    for (Product product : productCatalog) {
        if (product.getName().contains(name)) {
            results.add(product);
        }
    }
    return results;
}

1. 需要通过索引快速定位元素的排序算法

// 适合ArrayList的场景：需要高效交换元素位置的排序算法
ArrayList<Integer> numbers = new ArrayList<>();
// 添加数字...

// 基于索引的高效元素交换，快速排序算法
public void quickSort(ArrayList<Integer> list, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(list, low, high);
        quickSort(list, low, pivotIndex - 1);
        quickSort(list, pivotIndex + 1, high);
    }
}

private int partition(ArrayList<Integer> list, int low, int high) {
    int pivot = list.get(high);
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (list.get(j) <= pivot) {
            i++;
            // 高效交换元素
            int temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }
    int temp = list.get(i + 1);
    list.set(i + 1, list.get(high));
    list.set(high, temp);
    return i + 1;
}

1. 批量操作场景（如批量添加到尾部）

// 适合ArrayList的场景：批量添加元素到尾部
ArrayList<LogEntry> logEntries = new ArrayList<>(10000); // 预分配容量
for (int i = 0; i < 10000; i++) {
    logEntries.add(new LogEntry("Log message " + i)); // 添加到尾部，平均O(1)
}

5.2 LinkedList 适用场景

1. 频繁在两端添加/删除元素的场景（队列/栈）

// 适合LinkedList的场景：实现一个消息队列
LinkedList<Message> messageQueue = new LinkedList<>();

// 生产者添加消息到队尾
public void produceMessage(Message message) {
    messageQueue.addLast(message);  // O(1)复杂度
}

// 消费者从队首获取并移除消息
public Message consumeMessage() {
    if (messageQueue.isEmpty()) {
        return null;
    }
    return messageQueue.removeFirst();  // O(1)复杂度
}

1. 频繁在中间插入/删除元素，且有迭代器位置的场景

// 适合LinkedList的场景：在迭代过程中频繁删除元素
LinkedList<Task> tasks = new LinkedList<>();
// 添加任务...

// 使用迭代器在迭代中移除元素
public void removeCompletedTasks() {
    Iterator<Task> iterator = tasks.iterator();
    while (iterator.hasNext()) {
        Task task = iterator.next();
        if (task.isCompleted()) {
            iterator.remove();  // O(1)复杂度，不需要移动元素
        }
    }
}

1. 实现LRU缓存

// 适合LinkedList的场景：实现LRU缓存（最近最少使用）
public class LRUCache<K, V> {
    private final int capacity;
    private final Map<K, V> cache = new HashMap<>();
    private final LinkedList<K> accessOrder = new LinkedList<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null;
        }

        // 将访问的键移到链表末尾（最近使用）
        accessOrder.remove(key);  // O(1) 如果使用迭代器
        accessOrder.addLast(key); // O(1)
        return cache.get(key);
    }

    public void put(K key, V value) {
        if (cache.containsKey(key)) {
            accessOrder.remove(key);
        } else if (cache.size() >= capacity) {
            // 移除最久未使用的元素（链表头部）
            K leastUsed = accessOrder.removeFirst(); // O(1)
            cache.remove(leastUsed);
        }

        cache.put(key, value);
        accessOrder.addLast(key); // O(1)
    }
}

1. 双端队列实现

// 适合LinkedList的场景：实现一个工作窃取队列
public class WorkStealingQueue<T> {
    private final LinkedList<T> deque = new LinkedList<>();

    // 本地线程从头部获取任务
    public synchronized T pollFirst() {
        return deque.isEmpty() ? null : de