ArrayList 和 LinkedList 都是 Java 集合框架中常用的列表实现类，它们都实现了 List 接口，但在底层数据结构、性能特点等方面存在一些区别，下面将详细介绍。

区别

1. 底层数据结构

  • ArrayList：基于动态数组实现。它使用一个数组来存储元素，当数组空间不足时，会自动进行扩容操作，一般是创建一个更大的新数组，并将原数组中的元素复制到新数组中。
  • LinkedList：基于双向链表实现。它由一系列节点组成，每个节点包含数据元素、指向前一个节点的引用和指向后一个节点的引用。

2. 随机访问性能

  • ArrayList：支持快速的随机访问，因为它可以通过索引直接访问数组中的元素，时间复杂度为 $O(1)$。
  • LinkedList：随机访问性能较差，因为它需要从头节点或尾节点开始遍历链表，直到找到指定索引的节点，时间复杂度为 $O(n)$。

3. 插入和删除性能

  • ArrayList：在数组末尾插入或删除元素的性能较好，时间复杂度为 $O(1)$；但在数组中间或开头插入或删除元素时，需要移动后续元素，时间复杂度为 $O(n)$。
  • LinkedList：在链表的任意位置插入或删除元素的性能较好，因为只需要修改相邻节点的引用，时间复杂度为 $O(1)$；但在查找要插入或删除的位置时，需要遍历链表，时间复杂度为 $O(n)$。

4. 内存占用

  • ArrayList：由于是数组实现，会预先分配一定的内存空间，可能会存在一定的内存浪费；但每个元素只需要存储数据本身。
  • LinkedList：由于每个节点需要额外存储指向前一个节点和后一个节点的引用，因此会占用更多的内存空间。

使用场景

适合使用 ArrayList 的场景

  • 随机访问频繁：如果需要频繁地根据索引访问列表中的元素，例如遍历列表、获取指定位置的元素等，ArrayList 是更好的选择，因为它的随机访问时间复杂度为 $O(1)$。
  • 插入和删除操作较少：如果列表的插入和删除操作主要发生在列表的末尾，并且插入和删除操作的频率较低，ArrayList 可以提供较好的性能。

以下是一个使用 ArrayList 的示例代码：

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

public class ArrayListExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        // 添加元素
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        // 随机访问元素
        System.out.println("Element at index 5: " + list.get(5));
    }
}

适合使用 LinkedList 的场景

  • 插入和删除操作频繁：如果需要频繁地在列表的任意位置插入或删除元素，例如实现栈、队列等数据结构，LinkedList 是更好的选择，因为它的插入和删除操作时间复杂度为 $O(1)$。
  • 顺序访问为主：如果对列表的访问主要是顺序访问，而不是随机访问，LinkedList 可以提供较好的性能。

以下是一个使用 LinkedList 的示例代码：

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

public class LinkedListExample {
    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        // 添加元素
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        // 在列表中间插入元素
        list.add(5, 100);
        System.out.println("List after insertion: " + list);
    }
}

综上所述，在选择 ArrayList 还是 LinkedList 时，需要根据具体的应用场景和性能需求来决定。