ArrayList底层是连续数组，支持O(1)随机访问；LinkedList是双向链表，get需O(n)遍历，但插入删除只需改指针。选型应依据实际高频操作：重随机访问用ArrayList，重首尾增删且少访问用LinkedList。
ArrayList 和 LinkedList 底层到底差在哪
差在内存布局和寻址方式：ArrayList 是一块连续的 Object[] 数组，元素挨着存；LinkedList 是一堆离散的 Node 节点，每个节点里存着 prev、next 和数据本身。
这意味着：
- ArrayList 支持靠下标直接跳转，get(500) 就是数组第 500 个位置，一步到位；
- LinkedList 的 get(500) 得从头（或尾）开始，一个一个顺着 next 指针走，平均要走 250 步；
- 插入时，ArrayList 在中间加一个元素，得把后面所有元素往后挪一位（System.arraycopy），而 LinkedList 只需改两个指针（比如 prev.next = newNode、newNode.prev = prev）。
什么时候该用 ArrayList，什么时候非得选 LinkedList
看操作重心——不是“听说 LinkedList 插入快”就盲目换，而是盯住你代码里真正高频的动作：
- 频繁调用
get(i)、set(i, x)或遍历用for (int i = 0; i ？→ 选 <code>ArrayList - 大量在头部或中间做
add(0, x)、remove(0)、add(100, x)，且已知位置（比如用迭代器定位后删）？→LinkedList确实更省事 - 只在末尾增删（
add(x)、removeLast()），又需要随机访问？→ 还是ArrayList，因为它的尾部操作也是 O(1)，还省内存 - 想用作栈（
push/pop）或队列（addFirst/removeLast）？→LinkedList语法上方便，但注意：它不是线程安全的，也不如ArrayDeque高效（后者才是 JDK 推荐的栈/队列实现）
别被 get(i) 欺骗：LinkedList 的索引访问有多慢
LinkedList.get(i) 看起来和 ArrayList.get(i) 一样用，但背后行为天壤之别。JDK 实现会判断 i 靠近头还是尾，再决定从哪边开始遍历，可即便如此，最坏仍是 O(n)。
常见错误现象：
- 用 for (int i = 0; i 遍历 <code>LinkedList → 实际时间复杂度是 O(n²)
- 把 LinkedList 当成“能随便查的链表”，结果压测时 CPU 突然飙高
正确做法：
- 遍历一律用增强 for 或迭代器：for (String s : list) 或 Iterator<string> it = list.iterator()</string>
- 真需要按索引查，先问自己：能不能重构逻辑避免？比如缓存位置、改用 Map 存索引映射、或干脆换 ArrayList
内存开销和扩容行为的实际影响
ArrayList 会预留空间：初始容量 10，满后扩到 15（1.5 倍），再满扩到 22……这些空位不存数据但也占内存；LinkedList 每个元素多占两个引用（约 16 字节 JVM 对齐后），10 万个字符串，光指针就多占 ~1.6MB。
容易踩的坑：
- 用 new LinkedList() 存几百万条日志，发现堆内存比预估高一截 → 检查对象图，很可能是 Node 的指针膨胀了
- 初始化 ArrayList 时不指定初始容量，反复 add 导致多次扩容复制 → 如果已知最终规模（比如读取 CSV 的 5 万行），直接 new ArrayList(50000)
- 认为 LinkedList “不用扩容所以更省内存” → 错，它的“动态”靠的是堆上分散分配，GC 压力反而可能更大
真实项目里，90% 场景 ArrayList 更稳妥。LinkedList 的优势非常具体：已知位置 + 频繁中间增删 + 不怎么查。一旦条件缺一环，它就成了性能陷阱。
