面试题：请简述ArrayList 与 LinkedList 的区别？

ArrayList 和 LinkedList 是 Java 集合框架中两种常用的列表实现，它们的主要区别在于内部数据结构和性能特点：

1. 内部数据结构：

ArrayList：
- 基于动态数组实现。
- 内部使用一个数组来存储元素。
- 数组在内存中是连续分配的。
LinkedList：
- 基于双向链表实现。
- 内部使用节点（Node）来存储元素，每个节点包含数据以及指向前后节点的引用。
- 节点在内存中是非连续分配的。

2. 性能特点：

访问元素（随机访问）：

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

插入和删除元素：

ArrayList：
- 在列表末尾插入或删除元素的时间复杂度为 O(1)。
- 在列表中间或开头插入或删除元素的时间复杂度为 O(n)，因为需要移动后续元素。
LinkedList：
- 在列表开头或末尾插入或删除元素的时间复杂度为 O(1)。
- 在列表中间插入或删除元素的时间复杂度为 O(n)，因为需要遍历链表找到目标位置。

内存占用：

ArrayList：
- 内存占用较少，因为只需要存储元素和数组的容量。
- 但是可能会有未使用的预留空间（容量大于实际元素数量）。
LinkedList：
- 内存占用较多，因为每个节点都需要存储前后节点的引用。
- 没有预留空间的问题，但每个节点的额外开销较大。

3. 适用场景：

ArrayList：
- 适合频繁访问元素的场景（如随机访问）。
- 适合元素数量相对固定或主要在末尾进行插入和删除的场景。
LinkedList：
- 适合频繁在列表开头或中间插入和删除元素的场景。
- 适合需要实现队列（Queue）或双端队列（Deque）的场景。

4. 代码示例：

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

public class ArrayListVsLinkedList {
    public static void main(String[] args) {
        // ArrayList 示例
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(1); // O(1)
        arrayList.add(2);
        arrayList.add(3);
        System.out.println("ArrayList: " + arrayList.get(1)); // O(1)

        // LinkedList 示例
        List<Integer> linkedList = new LinkedList<>();
        linkedList.add(1); // O(1)
        linkedList.add(2);
        linkedList.add(3);
        System.out.println("LinkedList: " + linkedList.get(1)); // O(n)
    }
}

总结：

特性	ArrayList	LinkedList
内部数据结构	动态数组	双向链表
随机访问性能	O(1)	O(n)
插入/删除性能	末尾：O(1)；中间/开头：O(n)	开头/末尾：O(1)；中间：O(n)
内存占用	较少（连续内存）	较多（节点额外开销）
适用场景	频繁访问、元素数量相对固定	频繁插入/删除、实现队列或双端队列

根据具体需求选择合适的集合实现：

如果需要快速随机访问，选择 ArrayList。
如果需要频繁插入和删除，选择 LinkedList。

THE END

Java 集合类