Java中ArrayList与LinkedList怎么选？

应使用 ArrayList；因其基于数组实现，支持 O(1) 时间复杂度的随机访问，适合频繁通过下标取值或遍历场景。

随机访问多就用 ArrayList

如果代码里频繁通过下标取值，比如 list.get(1000)、循环中 for (int i = 0; i < list.size(); i++) 配合 get(i)，ArrayList 是更优选择。它的底层是数组，get() 是 O(1) 时间复杂度。

LinkedList 的 get(i) 必须从头或尾开始遍历节点，平均 O(n/2)，实际就是 O(n)。哪怕只是查第 5000 个元素，也要跳过近一半节点。

• 常见错误：把 LinkedList 当作“更快的列表”用于大量下标访问，结果性能骤降
• 注意 ArrayList 的扩容机制：初始容量 10，超出时按 1.5 倍扩容（JDK 17+），可能触发数组复制；若已知大小，建议构造时传入初始容量，如 new ArrayList<>(10000)
• 迭代器遍历（for-each 或 iterator.next()）两者性能接近，但 ArrayList 缓存局部性更好，实际仍略快

头部/中间插入删除频繁就考虑 LinkedList

LinkedList 在首尾增删是 O(1)，因为它维护了 first 和 last 指针；在已知位置（比如已有 ListIterator）做插入/删除也是 O(1)。

而 ArrayList 在非末尾位置增删，例如 add(0, item) 或 remove(5)，需要移动后续所有元素，最坏 O(n)。

• 真实场景中，“频繁在头部插入”往往出现在模拟队列、日志缓冲、解析 token 流等；但注意：Java 自带的 ArrayDeque 在首尾操作上比 LinkedList 更快且内存更省，优先考虑它
• LinkedList 的每个元素额外携带两个引用（prev 和 next），内存开销约是 ArrayList 的 2–3 倍；小对象集合下 GC 压力更明显
• 不要误以为 “LinkedList 插入快” 就适合所有增删场景——如果插入前得先 get(i) 定位，那总时间仍是 O(n)

是否需要实现 Queue 或 Deque 接口

如果业务语义是队列（FIFO）、双端队列（支持首尾进出），别硬套 ArrayList 或 LinkedList，直接用接口对应实现类更清晰、更安全。

• ArrayDeque：非线程安全，无容量限制，首尾操作 O(1)，内存紧凑，是 Stack 和 Queue 场景的首选
• LinkedList 实现了 Deque，但因双向链表结构，实际比 ArrayDeque 慢 2–5 倍（基准测试常见），仅当必须使用 Iterator.remove() 且需在遍历中删中间元素时才值得考虑
• ArrayList 不实现 Deque，强行用它模拟队列（如反复 add(0, x) + remove(size()-1)）会严重拖慢性能

线程安全需求不能靠换列表类型解决

ArrayList 和 LinkedList 都是非线程安全的。加锁、用 Collections.synchronizedList() 或切换到 CopyOnWriteArrayList 才是正解。

• Collections.synchronizedList(new LinkedList<>()) 只保证单个方法原子性，复合操作（如“检查是否存在再添加”）仍需手动同步
• CopyOnWriteArrayList 适合读多写少，但写操作（add/set）会复制整个数组，大列表下代价极高；它和 LinkedList 完全不是同一设计维度
• 别因为听说 “LinkedList 节点独立” 就以为它天然适合并发——节点引用关系在多线程下依然会出竞态，没有任何内置保障

真正决定选哪个的，从来不是“哪个更高级”，而是你代码里 get()、add()、remove() 出现的位置和频次。压测前凭经验猜，压测后看火焰图——中间那几个 hotspot 才是你该盯住的地方。