Java中何时使用LinkedList而非ArrayList

技术背景

在Java编程里，ArrayList 和 LinkedList 都是实现了 List 接口的常用集合类。ArrayList 借助动态可调整大小的数组来实现，而 LinkedList 则是利用双向链表来实现。由于实现方式不同，它们在不同操作上有着不同的性能表现，因此理解何时使用 LinkedList 而非 ArrayList 十分重要。

实现步骤

1. 了解基本操作的时间复杂度

• ArrayList：
  • get(int index)：时间复杂度为 O(1)，能快速随机访问元素。
  • add(E element)：平均时间复杂度为 O(1)，但在数组需扩容时，最坏情况为 O(n)。
  • add(int index, E element)：平均时间复杂度为 O(n)，需移动后续元素。
  • remove(int index)：平均时间复杂度为 O(n)，需移动后续元素。
• LinkedList：
  • get(int index)：平均时间复杂度为 O(n)，需遍历链表。
  • add(E element)：时间复杂度为 O(1)，在链表尾部添加元素。
  • add(int index, E element)：平均时间复杂度为 O(n)，但在 index = 0 或 index = list.size() - 1 时为 O(1)。
  • remove(int index)：平均时间复杂度为 O(n)，但在 index = 0 或 index = list.size() - 1 时为 O(1)。
  • Iterator.remove()：时间复杂度为 O(1)。
  • ListIterator.add(E element)：时间复杂度为 O(1)。

2. 考虑操作场景

• 频繁随机访问：若需要频繁随机访问元素，ArrayList 是更好的选择，因为它能在常数时间内访问元素。
• 频繁插入和删除：如果经常在列表头部或中间进行插入和删除操作，LinkedList 可能更合适，特别是使用迭代器进行插入和删除时，其时间复杂度为 O(1)。
• 作为队列使用：LinkedList 实现了 Deque 接口，适合作为队列使用，在队列头部和尾部的插入和删除操作效率高。

核心代码

以下是一个简单的示例代码，用于测试 ArrayList 和 LinkedList 在插入操作上的性能差异：

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

public class ArrayListVsLinkedList {
    public static void main(String[] args) {
        int size = 100000;

        // 测试ArrayList插入性能
        List<Integer> arrayList = new ArrayList<>();
        long startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            arrayList.add(0, i);
        }
        long endTime = System.nanoTime();
        System.out.println("ArrayList插入耗时: " + (endTime - startTime) + " 纳秒");

        // 测试LinkedList插入性能
        List<Integer> linkedList = new LinkedList<>();
        startTime = System.nanoTime();
        for (int i = 0; i < size; i++) {
            linkedList.add(0, i);
        }
        endTime = System.nanoTime();
        System.out.println("LinkedList插入耗时: " + (endTime - startTime) + " 纳秒");
    }
}

最佳实践

• 优先选择 ArrayList：在大多数情况下，由于 ArrayList 具有更好的缓存局部性和随机访问性能，优先选择 ArrayList。
• 提前设置初始容量：若已知要添加大量元素到 ArrayList 中，可通过构造函数设置较大的初始容量，以减少数组扩容的开销。
• 使用 LinkedList 特定场景：当需要频繁在列表头部或中间进行插入和删除操作，或者需要使用队列功能时，选择 LinkedList。

常见问题

1. LinkedList 为什么占用更多内存？

LinkedList 的每个节点除了存储元素本身，还需要存储指向前一个节点和后一个节点的引用，因此会占用更多的内存。

2. 如何选择 ArrayList 和 LinkedList 以提高性能？

如果应用程序主要进行随机访问操作，应选择 ArrayList；如果主要进行插入和删除操作，特别是在列表头部或中间，LinkedList 可能更合适。但在实际使用中，应根据具体的性能测试结果来做出选择。

3. ArrayList 扩容机制是怎样的？

当 ArrayList 中的元素数量超过数组的容量时，会创建一个新的数组，其大小通常为原数组的 1.5 倍，并将原数组中的元素复制到新数组中。