Java面试——ArrayList与LinkedList的区别及选型_技术教程

ArrayList随机访问快（O(1)），但中间插入/删除慢（O(n)）；LinkedList头尾增删快（O(1)），但随机访问慢（O(n)）；选型需结合实际操作模式，而非仅看理论复杂度。

ArrayList 随机访问快，但中间插入/删除慢

因为 ArrayList 底层是动态数组，支持通过下标直接定位元素，get(int index) 是 O(1) 时间复杂度。但一旦在中间位置调用 add(int index, E element) 或 remove(int index)，就要把后续所有元素整体拷贝移动，最坏是 O(n)。

常见错误：用 ArrayList 在循环中反复 remove() 满足条件的元素，没注意索引偏移，导致漏删或 IndexOutOfBoundsException；或者误以为 list.add(0, x) 很便宜，实际每次都在头部插入，性能急剧下降。

适合场景：读多写少、频繁按索引查值、需要 Arrays.binarySearch() 或 Collection.toArray() 的场合
注意扩容：初始容量默认是 10，触发扩容时会新建数组并 System.arraycopy()，有额外开销；若已知大致大小，建议构造时传入 initialCapacity
线程不安全：多线程环境下直接使用会出错，别指望“偶尔跑一次没问题”

LinkedList 插入删除快，但随机访问极慢

LinkedList 是双向链表实现，addFirst()、addLast()、removeFirst()、removeLast() 全是 O(1)；在已有 ListIterator 位置附近增删也是 O(1)。但它的 get(int index) 必须从头或尾开始遍历指针，平均 O(n/2)，比 ArrayList 慢一个数量级。

很多人以为 “LinkedList 适合频繁增删”，却忽略了前提：必须是头尾操作，或已有迭代器定位点。用 list.get(i) 再 remove(i) 实际是两次遍历，比 ArrayList 还慢。

适合场景：当逻辑天然符合队列（offer()/poll()）、栈（push()/pop()）或需在遍历中动态增删（配合 ListIterator）时才真正受益
内存开销大：每个元素额外存两个指针（prev 和 next），对象头+引用本身比数组元素占用多 50% 以上内存
不支持快速随机访问：subList() 返回的是 SubList 视图，但底层仍是链表遍历，不是切片优化

选型不能只看“理论复杂度”，得看真实操作模式

面试常问“什么情况选哪个”，但真实项目里，多数人卡在“根本没想清楚自己在做什么操作”。比如：

用 for (int i = 0; i —— 这是典型误用，无论 ArrayList 还是 LinkedList 都很糟糕；正确做法是用 Iterator.remove() 或 removeIf()
需要频繁按条件查找后删除：先用 Stream.filter() 收集新列表，比原地删更清晰且往往更快
数据量小（LinkedList，要当数组就用 ArrayList）
若真需要头尾高效 + 随机访问，考虑 ArrayDeque（非 List 实现，但比 LinkedList 更省内存、缓存友好）

别忽略替代方案：Vector、CopyOnWriteArrayList、Collections.synchronizedList

面试可能延伸问线程安全。记住：Vector 是历史遗留类，所有方法加了 synchronized，但锁粒度太粗，实际并发性能差；CopyOnWriteArrayList 适合读远多于写的场景（如监听器列表），但每次写都复制整个数组，大数据量写操作代价极高；Collections.synchronizedList(new ArrayList()) 只是对单个方法加锁，复合操作（如先 size() 再 get()）仍需手动同步。

真正高并发场景，通常应跳过这些 List，改用 ConcurrentHashMap 模拟集合，或用 java.util.concurrent 下更合适的结构（如 ConcurrentLinkedQueue）。

List safeList = Collections.synchronizedList(new ArrayList<>());
// 下面这段仍然不是线程安全的！
if (safeList.size() > 0) {
    String first = safeList.get(0); // 中间可能被其他线程清空
}