就算业务逻辑写得再溜，也可能把应用搞成蜗牛速度。
坑不在算法本身，而在你选的 “容器” 上。
选不对 List，每次循环都像绕远路散步；
选对了，同样的代码能立马精神起来。
ArrayList 和 LinkedList 表面看像双胞胎，
骨子里却像两个物种。
就是这种 “货不对板”，悄悄决定了性能是翻车还是封神。
读完这篇，你就能掌握一个简单法则，不用跑分也能选对。
两个 List 的暗战
ArrayList 是个可扩容的数组，内存里是一整块连续空间，支持直接索引。
LinkedList 是串节点，每个节点存着值和两个指针（.prev 和.next）。
一张图胜过千次微基准测试：
ArrayList（连续内存）
Index: 0 1 2 3 4 Data: [A] [B] [C] [D] [E] Access: direct by index → O(1)
LinkedList（双向链表）
+-----+----+ +-----+----+ +-----+----+ | A | ↔ | <-> | B | ↔ | <-> | C | ↔ | +-----+----+ +-----+----+ +-----+----+ Each node has: - the value - a pointer to previous - a pointer to next Access: must follow links → O(n)
每个节点包含：
- 实际值
- 指向前一个节点的指针
- 指向后一个节点的指针
访问：必须顺着链条找 → O (n)
内存布局几乎决定了所有性能差异。
为啥一个飞似闪电，一个爬如蜗牛
随机访问：
- ArrayList：O (1)（唰一下就到）。
- LinkedList：O (n)（得一个个节点挪过去）。
尾部追加：
- ArrayList：平均 O (1)（偶尔扩容，但总体很快）。
- LinkedList：O (1)（有尾指针的话，直接挂上去）。
头部插入 / 删除：
- ArrayList：O (n)（后面所有元素都得挪位置）。
- LinkedList：O (1)（改两个指针就行，快得很）。
中间插入 / 删除：
除非手里握着迭代器定位到了目标位置，否则俩都得先 “找” 到位置。
如果用 ListIterator 定位好了，LinkedList 实际插入只要 O (1)；ArrayList 还是得挪一堆元素。
内存开销：
ArrayList 只存元素本身。
LinkedList 每个元素要带俩指针。数据量到百万级，内存能差出一大截。
所以结论很简单：
多数时候是按索引读，或者往末尾加东西 → 选 ArrayList。
边迭代边修改，或者频繁在头部增删 → 可以瞅瞅 LinkedList。
代码揭露真面目
随机访问：ArrayList 飞，LinkedList 爬。
var a = new ArrayList<Integer>(1000000); for (int i = 0; i < 1000000; i++) { a.add(i); } var l = new LinkedList<Integer>(); for (int i = 0; i < 1000000; i++) { l.add(i); } // 同样操作，成本天差地别 int x = a.get(700000); // O(1) 直接定位 int y = l.get(700000); // O(n) 慢慢爬吧
LinkedList 的秘密：在 “当前位置” 修改才快。
var list = new LinkedList<String>(); list.add("A"); list.add("B"); list.add("D"); // 用迭代器遍历并插入 var it = list.listIterator(); while (it.hasNext()) { if (it.next().equals("B")) { it.add("C"); // 直接插在B后面 break; } }
代码评审时常见的坑
- 用 LinkedList 还写索引循环
如果你写for (int i = 0; i < n; i++) list.get(i)，LinkedList 能慢到让你怀疑人生。
换成 ArrayList，或者用迭代器遍历吧。
- 迷信 “插入快”
LinkedList 只有在 “已经站在目标位置” 时才快。
多数时候，找位置的成本早就抵消了插入的优势。
- 忽略缓存 locality
ArrayList 的数据在内存里是一整块，CPU 缓存友好得很；
LinkedList 的节点散落在内存各处，访问起来自然慢。
- 用 LinkedList 实现队列
要做队列，用 ArrayDeque！
它更快、更省空间，就是为这场景设计的。
靠谱的简单法则
- 先从 ArrayList 开始
多数情况它都是最佳选择：内存占用小，读操作飞快，用起来还简单。
- LinkedList 只在特殊场景用
只有两种情况考虑它：一是边迭代边频繁修改（比如遍历的时候就地增删），二是必须频繁在头部增删。
- 队列和栈首选 ArrayDeque
别用 LinkedList 搞这个，ArrayDeque 专门优化了队列和栈操作，快得多。
- 改之前先实测
别瞎猜！先 profiling 看看代码到底慢在哪。很多时候瓶颈根本不在 List 本身。
这几条能搞定 Java 里大部分 List 性能问题。
选错 List 让 get (i) 变龟速的真实案例
有个同事用 LinkedList 存用户 ID，觉得它 “更灵活”。
后来他写了个循环，反复调用list.get(i)检查每个 ID。
在 LinkedList 上，每次 get (i) 都得从头爬一遍。
用户多到几千时，程序慢得像卡住了。
我们换成 ArrayList，get (i) 变成常数时间，
同样的代码瞬间变快，其他啥都没改。
就因为换了个 List 而已。
最终判决：默认选手 vs 专精选手
ArrayList 是日常主力，
LinkedList 是那种 “只租一个周末干活” 的专用工具。
如果你的访问模式是频繁按索引读，或者往末尾加元素，ArrayList 完胜。
如果你的修改操作集中在当前位置，而且用迭代器操作，LinkedList 能超常发挥。
摸清自己的使用模式，按内存布局选，别被传言忽悠。
