ArrayList随机访问O(1)但中间增删O(n)，LinkedList头尾增删O(1)但随机访问O(n)，选型需结合场景压测，勿机械套用理论。
ArrayList 随机访问快，但中间插入删除慢
因为 ArrayList 底层是动态数组，靠下标直接算内存地址，get(i) 是 O(1)；但一旦在中间 add(index, e) 或 remove(index)，就要把 index 后面所有元素整体拷贝挪位，最坏 O(n)。尤其在循环里反复 add(0, e)，性能会断崖式下跌。
常见错误现象：ConcurrentModificationException 不是因为多线程——哪怕单线程边遍历边用 remove(Object)（非迭代器 remove()），也会触发 fail-fast 机制报错。
- 适合场景：读多写少、按索引频繁访问、尾部追加为主
- 注意
ensureCapacity()可提前预留空间，避免多次扩容拷贝 - 扩容时默认翻倍（
oldCapacity + (oldCapacity >> 1)），但 JDK 21+ 改为更平滑增长
LinkedList 插入删除快，但随机访问极慢
LinkedList 是双向链表，每个节点存前后指针，addFirst()、addLast()、removeFirst() 都是 O(1)；但 get(i) 必须从头或尾开始逐个跳指针，平均 O(n/2)，实际比 ArrayList.get() 慢一个数量级以上。
使用场景非常窄：真正需要高频头/尾增删（比如实现栈、队列、LRU 缓存的双端操作），且几乎不按索引查元素。别因为“它叫 List 就以为能当数组用”。
立即学习“Java免费学习笔记（深入）”；
-
LinkedList实现了Deque接口，offerFirst()、pollLast()等方法比add/remove更语义明确 - 不要用
list.get(list.size() - 1)取末尾元素——改用list.getLast()，O(1) - 每个元素额外存两个指针，内存开销比
ArrayList大约多 50%～100%
迭代器行为一致，但底层机制完全不同
两者都支持 Iterator 和 ListIterator，接口行为一样，但实现逻辑天差地别：ArrayList 的迭代器本质是维护一个游标 cursor，靠数组下标推进；LinkedList 的迭代器则维护当前节点引用，靠 next/prev 指针跳转。
这意味着：用 listIterator().next() 遍历时，LinkedList 不会触发随机访问开销，但如果你在循环里混用 get(i)，就立刻掉进性能坑。
-
ListIterator的add()在ArrayList中仍是 O(n)，在LinkedList中是 O(1) - 两者对
modCount的检查逻辑相同，所以并发修改异常表现一致 - 别依赖
instanceof LinkedList做优化判断——抽象用List，具体实现应由场景决定
实际选型别只看理论，先压测再决定
很多人记住了“数组查得快、链表删得快”，就机械套用。但真实瓶颈往往不在数据结构本身：比如 GC 压力大时，LinkedList 大量小对象更容易触发 Young GC；而 ArrayList 扩容时的大块内存分配可能引发老年代晋升。
还有容易被忽略的点：JVM 对连续内存有预取优化，ArrayList 遍历速度受 CPU cache line 影响小；LinkedList 节点分散，cache miss 高，现代硬件上差距比教科书写的还大。
- 小数据量（ArrayList —— 更省内存、更易调试
- 真要高频头尾操作，考虑
ArrayDeque：数组实现、无扩容碎片、比LinkedList快且省内存 - 如果业务逻辑天然带索引访问（比如分页、排序、二分查找），
LinkedList直接排除
实际用的时候，最常踩的坑不是选错结构，而是没意识到「访问模式」才是关键——同一个 List，读写比例、索引分布、是否并发，全会影响最终性能。别背结论，先抓 profiler 看热点。
