数组和链表在 Java 中的区别是什么这个问题我至少被问过五次了不管是面试别人还是被面试。每次都能听到“数组查询快、链表增删快”这种标准答案但真到写代码选型时很多人还是只会用 ArrayList。今天我从存储模型、操作复杂度、JDK 源码实现到 CPU 缓存聊聊两者本质差异再给出一套可以直接拿去用的面试答题思路和工程判断标准。1. 存储模型差异连续内存 vs 节点跳跃这是所有区别的总根源1.1 数组的底层是一段连续地址空间Java 里的数组本质上就是一个容器对象当执行int[] arr new int[10]时JVM 会在堆上分配一块连续的、大小固定的内存区域元素按顺序紧密排列。后续访问第 i 个元素时JVM 只需要做一次地址计算起始地址 i * 单个元素占用字节数。这就是数组快最根本的原因——它是通过数学计算定位而不是通过遍历寻找。对象数组比如String[]或自定义类数组略有不同数组里存的是引用真正对象存放在堆的其他位置。不过引用的连续排列依然让遍历变得很快CPU 可以按顺序把一批引用加载到缓存行里。另外别忽略 JVM 的边界检查。每次数组访问都会检查索引是否越界越界就抛ArrayIndexOutOfBoundsException这是 JVM 为安全付出的代价。HotSpot JVM 在开启优化后可能消除部分循环中的边界检查这也是为什么 for 循环访问数组比手写 while 更高效的原因之一。1.2 链表靠节点和引用串起来没有“下标”这回事Java 中最典型的链表是LinkedList内部结构是双向链表。每个节点是一个Node对象包含三个部分存储的元素 item、指向前一个节点的 prev、指向后一个节点的 next。private static class NodeE { E item; NodeE next; NodeE prev; }链表的节点在堆内存中完全是离散的前后两个节点之间只通过引用“拉住”。想要访问第 n 个元素没有任何公式可以计算位置只能从头部或尾部开始逐节点跳转这就是顺序访问。如果链表长度是 100000访问中间元素最坏要跳 50000 次引用。用生活里的例子类比数组是电影院里的固定座位座号就是下标你拿到座号直接找对应座椅链表是寻宝游戏每张字条上只写了下一张字条藏在哪你必须一张张找过去才能到终点。这个差异听起来不起眼实际上决定了后面所有性能特征的走向。1.3 随机访问能力是数组最核心的护城河数组支持 O(1) 随机访问链表只能 O(n) 顺序访问这不是常数级别的差异而是规模越大差距越明显。10 万个元素的数组访问第 50000 个元素和访问第 0 个元素耗时基本一致链表访问到中间节点要跨越 25000 次引用。所以判断一个场景适不适合用数组先问自己我需不需要随机访问如果核心操作是按下标取值、按位覆盖、遍历求和数组几乎总是最优解。链表在这里没有任何优势反而因为节点间跳转徒增开销。很多人背过“数组查询快链表查询慢”但真正理解为什么的人不多。查询快不快取决于两件事能否通过下标直接定位以及内存是否连续。数组两个条件都满足链表一个都不满足。2. 增删改查的真实成本别被“链表插入快”这句话骗了2.1 数组插入删除的代价大量元素搬运数组在中间位置插入元素时需要把插入位置及之后的所有元素统一后移一格腾出空位。这个操作在 Java 里由System.arraycopy完成虽然底层是 native 方法、效率很高但仍然是 O(n) 的搬运成本。// 在 index 位置插入 value需要先移动元素 System.arraycopy(elementData, index, elementData, index 1, size - index); elementData[index] value; size;删除中间元素同理要把后面的元素全部往前移一位System.arraycopy(elementData, index 1, elementData, index, size - index - 1);最坏情况是插入到数组头部所有元素都要往右挪复杂度 O(n)。删除头部元素也一样整体前移。插入到尾部最理想如果容量足够O(1) 完成不需要任何移动。同时数组长度固定一旦容量不够就要扩容。扩容操作是创建新数组、把旧元素全部复制过去这也是 O(n) 的单次操作。但均摊下来ArrayList 的尾部追加接近 O(1)因为扩容频率跟插入频率相比很低。2.2 链表插入快的隐藏前提你已经站在目标位置附近“链表插入快”这话只对了一半。链表插入确实只需要断开两个引用、拼上两个新引用不涉及数据搬运NodeE newNode new Node(pred, e, succ); succ.prev newNode; pred.next newNode;但问题在于链表要插入到指定位置绝大多数情况下需要先遍历找到那个位置。比如调用linkedList.add(50000, value)先要执行node(50000)从头或尾遍历 50000 次拿到目标节点之后才是 O(1) 的断链和重连。整体复杂度依然是 O(n)。链表真正能做到 O(1) 插入删除的场景有两个在链表头部或尾部操作以及已经持有某个节点的引用时进行增删。比如addFirst、addLast、pollFirst以及迭代器迭代过程中通过iterator.remove()删除当前元素。所以更准确的说法是链表“改指针”的过程快但“找位置”的过程并不一定快。把整个操作合起来看多数情况下链表并不比数组快多少。ArrayDeque 的头部操作比 LinkedList 还快因为它内部用数组实现了双向循环队列改的是数组下标而不是垃圾回收和指针跳转。2.3 一张操作复杂度表看清全貌我把 ArrayList动态数组和 LinkedList双向链表常见操作的复杂度整理一下面试时可以直接用操作ArrayListLinkedList备注按下标访问 get(i)O(1)O(n)链表需要遍历到目标位置结尾添加 add(value)均摊 O(1)O(1)链表持有 last 节点引用头部添加 addFirst(value)O(n)O(1)数组需要整体右移指定位置插入 add(i, v)O(n)O(n)数组是搬运链表是遍历找位置按值查找 contains(value)O(n)O(n)两者都要遍历按指定节点删除O(n)O(1)链表持有节点引用时可瞬断看这张表就知道真正拉开差距的不是“增删”这个笼统概念而是你在哪个位置操作、是否已经持有引用、是否需要随机访问。如果面试官问你 ArrayList 和 LinkedList 的区别只说“数组查询快、链表插入快”其实是不完整的一定要把复杂度成立的前提讲清楚。2.4 实测带来额外认知链表的高层操作往往输在常数项复杂度相同的操作在实际运行时数组往往更占便宜。比如按索引插入ArrayList 做系统级内存复制内存地址连续LinkedList 要做大量节点对象访问、引用跳转、可能多次触发缺页和缓存未命中。数据量小的时候看不出差距数据量百万级时差距会变得非常明显。我做过一个很粗糙的对比测试向 100 万个元素的列表中部连续插入 10 万次ArrayList 反而比 LinkedList 快。原因很简单LinkedList 每次都要先 O(n) 遍历找位置再把新节点暴露给 GCArrayList 的中部插入虽然也是 O(n)但性能瓶颈只有一个arraycopy常数极小。这个结果可能违背很多人的直觉但工程实践中确实存在这也是我越来越倾向于 ArrayList 的原因。3. JDK 里的真实实现ArrayList 与 LinkedList 的底层逻辑3.1 ArrayList 的扩容机制和默认容量动态数组是数组最常用的封装。ArrayList底层就是Object[] elementData初始容量为 10注意这个 10 是懒加载的第一次 add 时才真正创建数组。当容量不够时触发扩容新容量是旧容量的 1.5 倍int newCapacity oldCapacity (oldCapacity 1); elementData Arrays.copyOf(elementData, newCapacity);为什么是 1.5 倍而不是翻倍这是一个空间和时间之间的折中。扩容倍数太大会浪费内存太小会频繁复制数据。1.5 倍可以保证扩容次数是 O(logn)而均摊插入成本仍然是 O(1)。这里有个实用技巧如果提前能估算数据量就调用new ArrayList(预估容量)或ensureCapacity避免多次扩容造成复制浪费。极端情况下如果数据量是 100 万每次 1.5 倍扩容会额外分配大量数组并整体拷贝提前设置容量能省掉不少无效工作。另外要留意ArrayList的subList返回的是内部视图不是独立副本。对子列表做结构修改会让父列表的modCount变化进而可能触发父列表迭代器的ConcurrentModificationException。这是很多人踩过的坑。3.2 LinkedList 的结构负担每个元素三份引用开销LinkedList继承了AbstractSequentialList实现了List和Deque。它没有扩容概念因为增加节点就是 new 一个 Node 然后改前后引用内存是边用边分配的。但“不用扩容”不等于“省内存”。每个 Node 对象本身有对象头还额外保存 prev 和 next 两个引用。如果你存的是 int 值一个通过LinkedListInteger存储的元素占用的内存可能是int的十几倍。相比之下ArrayList存储基本类型时虽然有自动装箱的开销但至少元素引用是连续排布的内存密度要高得多。LinkedList的节点还让 GC 压力变大。频繁插入删除会产生大量短命 Node 对象会增加 Minor GC 的频率和耗时。如果项目本身就是性能敏感的这是个不可忽视的隐性成本。3.3 为什么很多资深开发者写着写着就放弃 LinkedList先说结论绝大多数业务代码只需要用ArrayList只有极少数场景需要链表。这个结论不是我一个人的偏好你去看很多开源框架的源码内部列表默认实现基本都是ArrayList几乎没人把LinkedList当主力容器。头尾操作看起来是 LinkedList 的强项但 JDK 里还有个ArrayDeque。它底层用环形数组实现头部插入删除通过移动 head 指针完成既没有大量元素移动也不像 LinkedList 那样每个节点都要 new 对象。所以一旦你的场景是“频繁在头尾读写”首选应该是ArrayDeque而不是LinkedList。具备 O(1) 节点删除能力的场景比如实现 LRU 缓存时结合 HashMap 使用双向链表这时候才考虑 LinkedList。因为它能在 O(1) 时间内把任意已知节点摘除同时依靠节点间的引用关系维系顺序这是数组做不到的。所以面试里你说“LinkedList 在已知节点引用时可以 O(1) 删除”这比笼统回答“链表删除快”高一个层次。能用上这个特性才算真正理解了链表的设计价值。4. 那些容易被忽略的细节和坑4.1 数组长度不可变ArrayList 用扩容绕过了限制数组创建后长度固定这既是优势也是约束。固定长度意味着你可以用int[]存一行一年 365 天的数据不用担心自动扩容带来的内存波动。但也意味着你要事先知道上限否则就得自己写一个动态数组逻辑。ArrayList 用扩容解决了长度问题代价是偶尔一次性的大数组复制和内存抖动。写代码时如果知道最终规模直接在构造时传容量能避免这种抖动。这也是“数组和链表区别”背后更实际的问题你更在意确定性还是灵活性数组给的是确定内存和访问时间链表和动态数组给的是灵活规模。4.2 基本类型数组 vs 包装类型链表int[]可以直接存 Java 基本类型内存紧凑近乎零额外开销。而LinkedListInteger或ArrayListInteger存在自动装箱每个 int 都会变成Integer对象带来额外内存分配。做大量数值计算时用基本类型数组和包装类型容器性能差距可以拉开十倍以上。如果你确实需要一个动态大小的数值列表又希望保持较低开销可以分析一下数据量。百万级别的 int 数据int[]占大约 4MB而ArrayListInteger除了引用数组 4MB还要加上 100 万个 Integer 对象每个约 16 字节起步整体轻松超过 20MB。这个差距在移动端或高并发服务里非常致命。4.3 遍历删除时最容易踩的坑用 fori 循环从头到尾删除 ArrayList 中满足条件的元素会出现漏删或越界// 错误示例删除所有值为 2 的元素会漏删 for (int i 0; i list.size(); i) { if (list.get(i) 2) { list.remove(i); // 后面的元素前移i 要回退才对 } }正确做法是使用迭代器的remove或者倒序遍历IteratorInteger it list.iterator(); while (it.hasNext()) { if (it.next() 2) { it.remove(); } }这里背后机制是modCount。任何结构性修改都会让modCount增加迭代器在遍历时会检查expectedModCount是否一致不一致就抛ConcurrentModificationException。链表同样有这个问题它虽然是链式结构但迭代器同样依赖 modCount 做 fail-fast 保护。如果想追求最高性能可以用普通 for 循环倒序删除因为删除只涉及已遍历过的尾部两侧元素不需要维护迭代器契约。这个写法在 ArrayList 里性能最高但可读性稍差看项目取舍。4.4 CPU 缓存局部性数组快还有一个硬核原因现代 CPU 读取内存时不是按字节读而是按缓存行读通常一次拉取 64 字节。一个 int 占 4 字节也就是说 CPU 加载一个缓存行就能顺带把相邻的 15 个 int 全部装进高速缓存。数组遍历时命中缓存行的概率极高连续读取就像在同一本书的连续页里查资料一翻一个准。链表遍历时节点随机散布在内存各处。每跳转一个节点大概率都要重新访问内存缓存行里的数据往往是无效的。这就是缓存未命中带来的性能惩罚。数据量越大链表越吃亏。这也是很多看似“复杂度相同”的操作实测差异极大的底层原因之一。面试如果能聊到这一层说明你对“数组和链表的区别”的理解不只是停留在 API 层面而是已经深入到计算机体系结构层面了。5. 面试怎么答才能加分从背概念到展示工程判断5.1 一套完整的三层答题结构如果面试官问“数组和链表在 Java 中的区别是什么”我建议按三层递进回答而不是一上来背书第一层讲存储结构。数组是连续内存空间通过下标直接寻址支持 O(1) 随机访问链表是由节点和引用串联起来的离散结构访问某个位置必须从头尾开始遍历O(n)。第二层讲操作成本。数组在任意位置插入删除需要移动大量元素尾部追加均摊 O(1)链表在头部尾部和已知节点位置增删可以达到 O(1)但在中间任意索引处插入删除同样要先遍历定位整体还是 O(n)。第三层讲工程落地。Java 中对应的是 ArrayList 和 LinkedList。ArrayList 有扩容机制默认容量 10扩容为 1.5 倍LinkedList 没有扩容问题但每个节点有额外对象头和两个引用内存密度低。实际开发中 ArrayList 因为 CPU 缓存友好、gc 压力小综合表现通常优于 LinkedList头尾频繁读写的场景更推荐 ArrayDeque。这样答完面试官基本能看出你是真用过的而不是背题的。5.2 面试官最常追问的几个问题追问一ArrayList 默认容量为什么是 10这个数字是历史选择没有特别高深的算法含义但你要知道它是懒加载的第一次 add 才创建数组。知道这一点就能回答“为什么提前给定初始容量能提升性能”。追问二contains 在 ArrayList 和 LinkedList 中谁的效率更高两者都是 O(n)。但实际 contains 操作中 ArrayList 遍历底层数组访问连续内存速度更快。这题很多人误以为 LinkedList 某些操作一定更快其实是错的。追问三既然数组中插入删除要移动元素为什么 ArrayList 还叫 List因为 Java 的 List 接口定义的是“有序、可重复、可通过下标访问”的集合契约并不要求必须是链式结构。ArrayList 用数组实现了这一契约名字强调的是底层实现接口类型是 List。追问四如果需要实现一个 LRU 缓存用数组还是链表通常用 HashMap 加双向链表。因为缓存淘汰需要从链表中间摘除节点并移动到头部数组做这种操作要么移动大量数据要么需要额外维护节点位置不如链表灵活。5.3 工程选择参考什么场景用哪种结构场景建议频繁随机访问、遍历、按索引取值ArrayList频繁尾部追加且数据量可预估ArrayList 并预设初始容量需要频繁头尾读写队列、双端队列、栈ArrayDeque需要在已知节点位置进行 O(1) 插入删除LinkedList 或自定义双向链表需要存储大量基本类型数值追求极致内存效率基本类型数组 int[]、long[]需要实现 LRU 等淘汰策略且要求节点快速移动HashMap 双向链表我个人在实际项目里的习惯是能不上链表就不上链表。除非我拿着一个节点的引用并且真的需要 O(1) 摘除它或者我明确在写一个需要频繁移动节点的数据结构否则默认 ArrayList。数组的连续内存、低内存占用、缓存友好三大优势在绝大多数业务场景下都碾压链表。哪怕是要频繁头尾操作的场景ArrayDeque 通常也比 LinkedList 表现更好毕竟它既能 O(1) 头尾操作又能享受连续数组的缓存优势。理解了这些再回头看你写的代码很多 Collections 选型其实可以重新审视一遍。