真实面经题目 · 原创解析
ArrayList 和 LinkedList 都实现了 List 接口，但核心差异来自底层结构：ArrayList 基于可扩容数组，擅长随机访问、顺序遍历和末尾追加；LinkedList 基于双向链表，单个节点插入删除本身很快，但定位节点通常需要线性遍历。面试中不能只背数组查询快、链表增删快，还要结合容量扩容、内存占用、CPU 缓存、迭代器删除、fail-fast 和真实业务场景来回答。
ArrayList 和 LinkedList 的区别首先要看底层结构。ArrayList 底层是连续数组，元素按下标存储，所以通过 index 随机访问是 O(1)，遍历时内存连续、缓存命中率高，实际性能通常很好。它的主要代价在于中间插入或删除时需要移动后续元素，另外容量不足时会触发扩容和数组复制，但末尾追加在摊还意义上仍然是 O(1)。LinkedList 底层是双向链表，每个元素包装成节点，节点中保存前驱、后继和元素值。它不支持真正的 O(1) 随机访问，get(index) 需要从头或尾向中间遍历，因此频繁按下标访问会很慢。LinkedList 的优势在于已经拿到节点位置后，插入和删除只需要改指针；但如果只是调用 add(index, e) 或 remove(index)，仍然要先定位 index，整体往往还是 O(n)。实际开发中，如果主要是查询、遍历、排序、按下标访问、末尾追加，优先选择 ArrayList；如果需要队列、双端队列语义，或通过迭代器在遍历过程中频繁删除当前元素，可以考虑 LinkedList，但多数普通 List 场景 ArrayList 更常用。
ArrayList 的核心是一个可扩容数组，元素在逻辑上按下标连续排列，底层通过数组索引直接定位。LinkedList 的核心是双向链表，每个元素都被封装在节点中，节点除了保存元素本身，还保存前驱和后继引用。这个结构差异决定了两者在访问、插入删除、内存占用和 CPU 执行效率上的表现完全不同。
ArrayList 实现了 RandomAccess 标记接口，get(index) 可以通过数组下标直接取值，时间复杂度是 O(1)。LinkedList 的 get(index) 不是直接定位，它会根据 index 离头部还是尾部更近，选择从 first 或 last 开始遍历，平均仍然是 O(n)。因此频繁使用 for 循环按下标访问 LinkedList，性能会明显变差。
两者使用迭代器顺序遍历时，理论复杂度都是 O(n)，但 ArrayList 通常更快。原因是数组内存连续，CPU 缓存局部性好，访问下一个元素成本低；LinkedList 的节点分散在堆内存中，每次访问下一个节点都要追踪引用，可能带来更多缓存未命中和对象访问开销。所以即使复杂度相同，实际性能也可能差很多。
ArrayList 在容量足够时向末尾 add 元素只需要写入数组并增加 size，复杂度是 O(1)。容量不足时会扩容，创建更大的数组并复制旧元素，这一次操作是 O(n)，但分摊到多次追加后，摊还复杂度仍然是 O(1)。LinkedList 末尾追加只需要创建新节点并修改尾节点引用，也是 O(1)，但每个元素都会额外创建节点对象。
ArrayList 在中间插入或删除元素时，需要移动 index 后面的元素，复杂度是 O(n)。LinkedList 如果已经持有目标节点，插入或删除只需要改前后节点指针，操作本身是 O(1)。但常见的 add(index, e)、remove(index) 需要先按 index 遍历定位节点，定位过程是 O(n)，所以不能简单说 LinkedList 的中间增删一定更快。
ArrayList 主要存储一个对象引用数组，除了预留容量造成的空槽位，单个元素的额外结构成本较低。LinkedList 每个元素对应一个节点对象，节点里通常包含元素引用、prev 引用、next 引用，还会有对象头等额外开销。元素数量较大时，LinkedList 的内存占用通常明显高于 ArrayList，并且更多对象也会增加垃圾回收压力。
ArrayList 有容量概念，size 表示实际元素数量，capacity 表示底层数组长度。当元素数量超过容量时，需要分配新数组并复制数据。提前知道元素规模时，可以通过指定初始容量或 ensureCapacity 降低扩容次数。LinkedList 没有数组扩容问题，但每次插入都要创建节点对象，所以它避免了数组复制，却引入了频繁对象分配的成本。
两者的迭代器都支持 fail-fast 机制：在迭代过程中，如果集合被非迭代器自身的结构性修改影响，通常会抛出 ConcurrentModificationException。正确的遍历删除方式是使用 Iterator 的 remove 方法。LinkedList 的 ListIterator 在已定位位置附近执行 add、remove 更符合链表优势；ArrayList 的 Iterator 删除仍会触发数组元素移动。
大多数业务 List 场景优先选择 ArrayList，例如按顺序保存结果集、下标访问、分页数据、批量遍历、排序、末尾追加。LinkedList 更适合需要 Deque 能力的场景，例如队列、双端队列、头尾插入删除，或者在遍历过程中通过迭代器频繁修改当前位置附近元素。若只是普通列表，不应因为增删快就默认选 LinkedList。
因为底层是数组，可以通过 base address 加 index 偏移直接定位元素引用，get(index) 是 O(1)。同时数组连续存储，顺序遍历时 CPU 缓存友好，实际访问效率也较高。
不一定。如果已经拿到目标节点，LinkedList 改指针很快；但如果通过 add(index, e) 插入，需要先遍历找到 index，整体是 O(n)。ArrayList 虽然要移动元素，但在数据量不大或缓存命中较好时，实际可能更快。
扩容会创建更大的数组并复制旧元素，当次操作成本较高。频繁扩容会带来时间和内存抖动，因此在预计元素数量较明确时，应设置初始容量。
普通列表常见操作是遍历、随机访问、排序和末尾追加，这些场景 ArrayList 通常更简单、更省内存、更快。LinkedList 的节点开销和缓存不友好会让它在多数普通场景下没有优势。
ArrayList 和 LinkedList 本身都不是线程安全集合。并发修改时需要外部加锁，或根据场景选择并发集合、不可变集合、同步包装集合等方案。
fail-fast 指迭代过程中检测到集合被异常结构性修改时，迭代器会尽快抛出 ConcurrentModificationException。它用于暴露错误用法，不应被当作严格的并发安全保证。
