ArrayList和LinkedList的区别、扩容机制及底层的实现方式是什么

在Java集合框架中，ArrayList和LinkedList是两种常用的列表实现类。它们都实现了List接口，但在底层实现、性能特点和使用场景上有显著的区别。本文将详细探讨ArrayList和LinkedList的区别、扩容机制以及底层的实现方式。

1. ArrayList和LinkedList的基本区别

1.1 底层数据结构

• ArrayList：ArrayList的底层是基于动态数组实现的。它使用一个数组来存储元素，并且可以根据需要自动扩容。

• LinkedList：LinkedList的底层是基于双向链表实现的。它通过节点（Node）来存储元素，每个节点包含对前一个节点和后一个节点的引用。

1.2 性能特点

• ArrayList：

  • 随机访问：由于底层是数组，ArrayList支持通过索引快速访问元素，时间复杂度为O(1)。
  • 插入和删除：在列表的末尾插入或删除元素的时间复杂度为O(1)，但在列表的中间或开头插入或删除元素时，需要移动后续元素，时间复杂度为O(n)。
  • 内存占用：ArrayList的内存占用相对较小，因为它只需要存储元素和数组的容量。

• LinkedList：

  • 随机访问：由于底层是链表，LinkedList不支持通过索引快速访问元素，访问某个元素需要从头或尾开始遍历，时间复杂度为O(n)。
  • 插入和删除：在列表的任何位置插入或删除元素的时间复杂度为O(1)，因为只需要调整节点的引用。
  • 内存占用：LinkedList的内存占用相对较大，因为每个节点除了存储元素外，还需要存储对前一个节点和后一个节点的引用。

1.3 使用场景

• ArrayList：适用于需要频繁随机访问元素的场景，例如读取操作远多于插入和删除操作的场景。

• LinkedList：适用于需要频繁插入和删除元素的场景，例如实现队列或栈等数据结构。

2. ArrayList的扩容机制

2.1 初始容量

ArrayList在创建时，可以指定初始容量。如果不指定初始容量，默认的初始容量为10。

List<Integer> list = new ArrayList<>(); // 默认初始容量为10
List<Integer> listWithCapacity = new ArrayList<>(20); // 指定初始容量为20

2.2 扩容过程

当ArrayList中的元素数量超过当前数组的容量时，ArrayList会自动进行扩容。扩容的过程如下：

1. 计算新容量：新容量通常是当前容量的1.5倍（即oldCapacity + (oldCapacity >> 1)）。
2. 创建新数组：创建一个新的数组，容量为计算得到的新容量。
3. 复制元素：将旧数组中的元素复制到新数组中。
4. 更新引用：将ArrayList的内部数组引用指向新数组。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量为旧容量的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

2.3 扩容的性能影响

扩容操作涉及到数组的复制，因此会带来一定的性能开销。为了避免频繁扩容，可以在创建ArrayList时指定一个较大的初始容量，或者在添加大量元素之前调用ensureCapacity(int minCapacity)方法来确保容量足够。

list.ensureCapacity(1000); // 确保容量至少为1000

3. LinkedList的底层实现

3.1 节点结构

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

3.2 插入和删除操作

由于LinkedList是基于链表实现的，插入和删除操作只需要调整节点的引用，而不需要移动元素。

• 插入操作：

  1. 创建一个新节点。
  2. 调整新节点的前驱和后继引用。
  3. 调整相邻节点的引用。

• 删除操作：

  1. 找到要删除的节点。
  2. 调整相邻节点的引用。
  3. 将被删除节点的引用置为null。

// 插入操作
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++;
}

// 删除操作
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;
    size--;
    modCount++;
    return element;
}

3.3 内存占用

由于LinkedList的每个节点都需要存储前驱和后继节点的引用，因此它的内存占用比ArrayList要大。每个节点除了存储元素外，还需要额外的内存来存储引用。

4. 总结

ArrayList和LinkedList是Java集合框架中两种常用的列表实现类，它们在底层实现、性能特点和使用场景上有显著的区别。

• ArrayList：基于动态数组实现，支持快速随机访问，但在中间插入和删除元素时性能较差。适用于需要频繁读取操作的场景。

• LinkedList：基于双向链表实现，支持快速插入和删除操作，但在随机访问时性能较差。适用于需要频繁插入和删除操作的场景。

在实际开发中，应根据具体需求选择合适的列表实现类。如果需要频繁读取元素，ArrayList是更好的选择；如果需要频繁插入和删除元素，LinkedList则更为合适。