数组和链表在 Java 中的区别是什么？
- 标签：Java 集合、Java
🏛 业务架构师
底层区别两条：内存布局（数组连续内存、链表每个节点带前后指针分散存储）与访问成本（数组按下标 O(1)、链表 O(n) 遍历；链表增删只改指针、数组增删要搬移元素）。
但业务视角的选型结论比"各有所长"更重要：
- ArrayList 是绝大多数业务列表的默认选择。所谓"链表增删快"有陷阱：按位置增删时链表也要先 O(n) 找到位置，只有"已知节点引用"（头尾操作）时优势才成立——而业务代码里 90% 的场景是随机访问和尾部追加，全是数组的主场；
- LinkedList 真正的适用场景极少：频繁头尾操作（用 Deque 语义时）、或极端忌惮数组扩容拷贝的场景。内存上它还更贵——每个元素多 40 来个字节的指针开销，还要承受缓存不友好（节点内存不连续，CPU cache 命中率低），"增删快"的理论优势在实际运行中经常被缓存局部性反杀；
- 数组连续内存的红利常被低估：CPU 缓存行预取让顺序遍历数组远快于链表，这是硬件送给连续内存的免费午餐——数据量大时（百万级元素遍历），数组快数倍是常态。
引申到架构决策：集合选型这类"小决策"的正确姿势——默认用通用最优解（ArrayList），偏离默认值要有明确的场景依据。选型争议消耗的时间往往超过两种方案的性能差异本身，团队要有"约定优于争论"的纪律。真正需要链表特征的队列、栈场景，用 ArrayDeque（数组实现的双端队列）通常仍优于 LinkedList。
🏗 系统架构师
我从数据结构特性与真实负载两个维度对比：
- 内存布局：数组连续内存，CPU 缓存行友好、命中率高，随机访问 O(1)；链表节点分散，指针跳转每步都可能 cache miss，对现代 CPU 是硬伤——理论上链表头尾 O(1)，实测常被数组的 memcpy 与预取击败；
- 操作复杂度：数组随机读写 O(1)、中间插删 O(n)（搬移）；链表按序插删 O(1)（已知节点前提下），查找 O(n)；
- 空间：数组紧凑无额外开销；链表每节点两个指针（双向 16B 引用）+ 对象头，空间放大 2~3 倍，且加剧碎片；
- 扩容：数组整块复制；链表天然无扩容，但频繁小分配对 GC（young 区分配速率）不友好。
工程选型：我 90% 场景用 ArrayList / ArrayDeque——队列、栈、遍历、随机访问全是它们；LinkedList 几乎只在"需要在已知节点处高频 O(1) 增删"且持有节点引用时才有优势（如 LRU 的双向链表，配合 HashMap 持有节点引用，就是 LinkedHashMap 的实现内核）。
架构师视角：数据结构选型的第一变量是内存访问模式而非理论复杂度——缓存局部性对性能的影响经常超过复杂度的差异，这是我评审底层组件代码时的固定检查项。
💻 全栈开发专家
存储结构：数组是连续内存，靠下标偏移寻址；链表是节点 + 指针离散分配。
复杂度：
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头部插删 | O(n)（搬移） | O(1) |
| 已知位置插删 | O(n) 搬移 | O(1) 改指针 |
| 内存 | 紧凑、有扩容代价 | 每节点多 2 个指针 + GC 压力 |
我的实战观点（和教科书不一样的地方）：
- CPU 缓存局部性让数组几乎完胜。链表节点散落在堆里，每次 next 都可能 cache miss；
ArrayList随机访问和遍历远快于LinkedList，我压测过头部频繁插入场景，理论 O(1) 的 LinkedList 因为分配和 miss 反而更慢。 - 删除中间元素：ArrayList 是
System.arraycopy批量搬移（内存级 memmove，非常快），不是想象中的逐个挪。 - 选型：默认 ArrayList；只有"两端频繁操作且无需随机访问"（队列/栈）用 ArrayDeque（数组实现的双端队列，仍然不是链表）；真正需要链表的场景（LRU 的 O(1) 摘除节点、无界监听链）通常是被专门设计的结构（如 LinkedHashMap 内部维护链表关系）。
一句话：工程选型看缓存友好性和分配成本，不只看理论复杂度。