arraylist底层为连续数组，支持o(1)随机访问；linkedlist为双向链表，get需o(n)遍历，但首尾增删为o(1)，中间操作均需o(n)定位。
ArrayList 和 LinkedList 虽然都实现了 List 接口，对外行为一致，但底层存储方式完全不同——一个靠连续数组，一个靠离散节点。这种差异直接决定了它们在增删、查询、内存占用等操作上的实际表现。
存储结构：连续内存 vs 离散节点
ArrayList 底层是 动态数组，所有元素在 JVM 堆中占据一段连续内存空间，通过 Object[] elementData 存储，靠下标直接定位；LinkedList 则由一个个 双向链表节点（Node）构成，每个节点包含 item、prev 和 next 三个字段，节点之间靠引用连接，物理地址完全不连续。
- 数组连续 → 支持缓存预取，CPU 访问局部性好
- 链表离散 → 每次访问新节点都可能触发缓存未命中，指针跳转开销明显
- ArrayList 需要预分配空间（初始容量 10），扩容时复制整个数组（1.5 倍策略）
- LinkedList 无扩容概念，每 add 一个元素就 new 一个 Node 对象
随机访问：O(1) vs O(n)
调用 get(int index) 时，ArrayList 直接计算内存偏移：elementData[index]，一步到位；LinkedList 必须从头（或尾）开始遍历，它会判断 index 距离哪端更近，再决定从 first 还是 last 出发，平均仍需遍历约 n/2 个节点。
- 查第 0 个或最后一个元素：ArrayList 和 LinkedList 都快（前者下标，后者首尾指针）
- 查中间位置（如 size/2）：ArrayList 稳定毫秒级，LinkedList 随数据量线性变慢
- 循环遍历时：for-each 或迭代器对两者性能差距不大，但传统 for + get(i) 写法会让 LinkedList 性能雪崩
插入与删除：移动数据 vs 修改指针
在末尾操作（add() / removeLast()）两者都接近 O(1)；但在中间位置插入或删除时，关键区别浮现：
- ArrayList：先腾出空位——调用
System.arraycopy()把 index 后所有元素后移（或前移），再填入新元素，移动成本高 - LinkedList：先定位到目标位置的前驱节点（O(n) 遍历），再仅修改三四个指针（prev.next、next.prev 等），指针调整本身极快
- 注意：LinkedList 的“O(1) 插入”前提是已知插入点前驱；实际使用
add(int, E)仍要先找位置，整体仍是 O(n) - 频繁在头部或尾部增删（如模拟栈、队列）：LinkedList 的
addFirst()、removeLast()是真 O(1)
内存开销与 GC 压力
相同数量元素下，LinkedList 占用内存显著更高：
- ArrayList：每个元素只存原始值（装箱后为对象引用），外加一个数组对象头和长度字段
- LinkedList：每个元素额外包裹一层 Node 对象，含两个对象引用（prev/next）+ 对象头 + 对齐填充，单个元素内存占用约为 ArrayList 的 2–3 倍
- 大量短生命周期节点 → 更多小对象，加剧 Young GC 频率
- ArrayList 扩容产生的旧数组，在被替换后立即可被回收；LinkedList 删除节点后，孤立 Node 依赖 GC 清理
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
