Java数组与链表区别详解：内存布局、复杂度与场景选型

如果你面前有两种数据结构，第一种是一排连在一起的座位，座位号从0开始递增；第二种是一串珠子，每颗珠子都靠手里的线牵着前一颗。你要找第5个座位，直接抬头看门牌号走过去就行；你要找第5颗珠子，就得顺着线一颗一颗数过去。但如果要在中间加一个座位，你需要把后面所有座位整体挪一遍；而在两颗珠子之间加一颗，只需要把线拆开、重新串上。这个朴素的画面，就是数组和链表最核心的全部区别。

最近做技术面试复盘时，我把“数组和链表在 Java 中的区别是什么”作为开场热身题抛给候选人，结果挺意外的：大多数人能条件反射般背出“数组查询快、链表增删快”，再往下问为什么、在 Java 里具体怎么体现、什么时候该用哪个，就开始卡壳了。这道题看起来是八股，其实背后藏着一整条 Java 基础链：内存模型、时间复杂度的真实含义、ArrayList 和 LinkedList 的设计取舍、甚至 CPU 缓存对性能的影响。这篇文章我不打算给你一份可以直接背的“标准答案”，而是把这道题拆开揉碎，从内存布局讲到源码实现，再说到真实业务里怎么选，最后附上几个面试高频的链表/数组实操题，希望能帮真正想把基础打牢的朋友一次性搞定它。

1. 先别急着背八股：这个问题到底在考察什么

1.1 一道能伺候三届面试者的经典题

我当面试官这些年，这道题几乎可以算“热身题的常青树”。为什么它这么经典？因为一个候选人如果能把这题讲透，他的计算机基础、Java 集合源码熟悉度、复杂度分析能力基本都能反映出来；反过来，如果只会背结论，那后面追问两三句就会露馅。

很多候选人上来就说“数组查询是 O(1)，链表插入是 O(1)”，这句话单看没错，但不够完整。真正的考察点在于你是否理解 O(1) 和 O(n) 是在什么前提下成立的。数组的 O(1) 查询是建立在连续内存和下标偏移上的；链表的 O(1) 插入是建立在“你已经持有目标位置的节点引用”上的，而在 Java 的 LinkedList 里，如果你要插入到中间某个位置，得先花 O(n) 找到那个位置，整体复杂度依然是 O(n)。这个细节就是区分“背过”和“理解”的分水岭。

1.2 拆开标题里的每个关键词

我们把“数组和链表在 Java 中的区别是什么”拆成三部分来看：数组、链表、Java。

数组是一段连续的内存空间，里面存放相同类型的元素。这里“连续”两个字是关键，它决定了数组能够随机访问，也决定了数组天然定长。链表是逻辑上连续、物理上离散的结构，每个节点里存了数据和一个或多个指向相邻节点的引用，Java 里没有指针的说法，我们用引用（reference）来表示这种“牵着线”的关系。而“在 Java 中”这个限定也很重要，因为 Java 的数组和 C 语言不一样，Java 数组是一个对象，有 length 属性，越界访问会抛 ArrayIndexOutOfBoundsException，这些语言特性都会影响我们的使用方式。

1.3 顺序存储和链式存储的第一性原理

计算机里存储数据只有两种基本思路：一种是“大家排排坐”，在内存里找一整块连续空间，按顺序码放，这叫顺序存储；另一种是“各自为政，用线串起来”，每个数据元素单独找地方住，再通过地址把前后邻居串起来，这叫链式存储。

这两个思路没有绝对的优劣，它们是两种不同的“空间管理策略”。顺序存储的空间利用率高、访问快，但对空间的连续性有要求，扩展起来麻烦；链式存储对空间要求宽松，内存里东一块西一块只要能放下一个节点就行，扩展方便，但访问某个节点必须从头开始找。理解到这一层，后面所有的细节都能推导出来，而不是死记硬背了。

2. Java 里的数组：连续内存带来的优势与束缚

2.1 数组的本质：一段连续的内存空间

Java 里声明一个数组很简单，但背后发生的事情值得讲清楚：

int[] arr = new int[10];

这行代码做了两件事：在堆内存里申请了一块能放下 10 个 int 的连续空间，然后把数组对象的引用赋值给变量 arr。数组对象内部除了元素数据，还有一个 length 字段，所以访问arr.length不需要遍历数组就能拿到长度。

因为是连续空间，数组对 CPU 缓存非常友好。CPU 读内存不是一次读一个字节，而是按“缓存行”为单位批量加载，一般来说一个缓存行是 64 字节。访问数组元素时，CPU 会把相邻的一片数据一次性加载到缓存里，所以顺序遍历数组时，大部分数据都能直接从缓存命中，速度非常快。这个特性叫“空间局部性”，是数组在大数据量下依然表现优秀的重要底层原因。

2.2 随机访问为什么能做到 O(1)

数组能随机访问，靠的是一个简单的地址计算公式。假设数组的首地址是 base，每个元素占 size 个字节，那么第 i 个元素的地址就是：

base + i * size

这个公式只需要一次乘法和一次加法，和数组长度 n 完全没有关系，所以不管你访问 arr[0] 还是 arr[999999]，耗时都是常量级，这就是 O(1) 的由来。

我在带新人时经常拿这个公式解释“为什么数组下标从 0 开始”，因为我们想要第 i 个元素，计算偏移量用 i 直接用就是base + i * size，如果下标从 1 开始，那每次都得额外算base + (i - 1) * size，白白多一次减法。这个细节可能有点钻牛角尖，但理解了地址公式，数组的所有行为都能串起来。

2.3 定长与扩容：ArrayList 是怎么绕开这个痛点的

数组最大的痛点就是定长。创建时指定了长度 10，那它就永远是 10，想放第 11 个元素怎么办？只能重新申请一块更大的连续内存，把旧数据一个个拷贝过去，然后把旧数组整体丢掉。这个操作的时间复杂度是 O(n)，如果频繁做，性能很难看。

Java 里我们平时用得更多的其实是 ArrayList，它的本质就是“会自动扩容的数组”。看源码你会发现关键的扩容逻辑：

int newCapacity = oldCapacity + (oldCapacity >> 1); elementData = Arrays.copyOf(elementData, newCapacity);

这里能看出两个重要信息：ArrayList 默认扩容 1.5 倍，而不是固定每次加 10；扩容时调用 Arrays.copyOf 把旧数组元素整体复制到新数组。为什么是 1.5 倍而不是 2 倍？这是空间和时间的折中。扩容倍数太小，扩容频繁，拷贝开销大；倍数太大，浪费的内存多。1.5 倍是 JDK 作者在实践中选出来的经验值。

正因为扩容是 O(n) 操作，ArrayList 的 add 方法在尾部追加时，均摊时间复杂度依然是 O(1)：大部分情况下直接写入尾部就行，只有快满的时候才触发一次扩容，把这次分摊到前面 n 次插入上，每次的平均成本就被拉平了。这个概念叫“摊还分析”，理解它对读懂复杂度大有帮助。

2.4 数组开发中绕不开的常规操作

热词里能看到不少和数组相关的实操点，比如数组去重、数组转字符串、二维数组、数组排序。这些日常场景值得花点笔墨：

排序可以直接用工具类：

int[] arr = {3, 5, 1, 2, 4}; Arrays.sort(arr); System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]

数组转字符串，很多人直接调arr.toString()，结果打出来是一串[I@4554617c之类的地址，这是因为数组没有重写 Object 的 toString。正确做法是用Arrays.toString(arr)，如果是二维数组，用Arrays.deepToString(arr)。

数组去重最朴素的写法是用LinkedHashSet，它能同时做到去重和保持插入顺序：

Integer[] arr = {1, 2, 2, 3, 3, 4}; LinkedHashSet<Integer> set = new LinkedHashSet<>(Arrays.asList(arr)); Integer[] unique = set.toArray(new Integer[0]);

如果数组是有序的，也可以原地双指针去重，那又是另一套算法思路了。关于二维数组，Java 里其实是“数组的数组”，也就是说int[][]本质上是一个一维数组，每个元素又是一个 int 数组，所以二维数组的每一行长度可以不一样，这一点和 C 语言里规整的二维数组有区别，容易被人忽略。

3. Java 里的链表：灵活背后藏着什么代价

3.1 LinkedList 的底层结构：每个节点都带着两根线

Java 集合里的 LinkedList 是一个双向链表，它的核心结构体现在私有静态内部类 Node 上：

private static class Node<E> { E item; Node<E> next; Node<E> prev; }

每个节点有三个字段：存的数据 item、指向后继的 next、指向前驱的 prev。整个链表还维护着 first 和 last 两个哨兵引用，分别指向头节点和尾节点。正是因为持有 last 引用，LinkedList 在尾部插入节点的效率才是 O(1)，不需要从头遍历到尾部。

理解了 Node 结构，很多链表面试题的解题思路就呼之欲出了：链表反转的本质就是不断把每个节点的 next 和 prev 调换方向；判断链表是否有环就需要用快慢指针；删除某个节点只需要把前驱的 next 直接指向它的后继，让这个节点“从链上摘下来”。

3.2 为什么插入删除确实快：只改引用，不搬数据

链表的插入和删除之所以理论上快，是因为它只做指针操作。比如在节点 A 后面插入新节点 X，只需要四步：把 X 的 prev 设为 A，X 的 next 设为 A 的 next，A.next.prev 设为 X，A.next 设为 X。不管链表里已经有多少个节点，这四步操作不会因为链表长度而变慢。

这跟数组对比非常鲜明。数组往中间插一个元素，需要把插入位置之后的所有元素都往后挪一格，最坏情况下要挪 n 个元素，时间复杂度 O(n)。所以从“操作本身”来看，链表插入确实快。但请注意，我强调的是“找到位置之后”，这个前提在真实使用中非常重要，后面第 4 节会详聊。

3.3 查找的代价：从 O(1) 降到 O(n)

链表最大的短板是没有随机访问能力。就像开头说的珠子，你不知道第 100 颗珠子长什么样，必须从第一颗开始顺着线数过去。在 Java 的 LinkedList 里，如果你想 get(500)，源码会做一个优化：先判断目标位置离头部近还是离尾部近，然后从较近的一端开始遍历。

if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; }

这看起来是个优化，但它改变不了 O(n) 的本质：不管从哪头开始，最坏情况都要遍历一半链表。而数组的 get(500) 就是一次地址计算，直接拿到元素，O(1)。这就是为什么我们常说“链表查询慢”，慢在这里。

3.4 单向、双向、循环：链表家族不止一种

热词里出现了循环单链表、双链表、单链表基本操作，这些概念需要放到一起来区分：

单向链表是最朴素的形式，每个节点只有 next 引用，只能顺着一个方向走，找前驱做不到，所以删除节点时必须知道前驱节点。双向链表在单向基础上加了 prev，可以双向遍历，Java 的 LinkedList 就是这个结构。循环链表是把尾节点的 next 指向头节点，形成一个环，解决的是某些场景下“绕一圈回到起点”的需求。

面试题里经常看到的“链表反转”“合并两个有序链表”“判断是否有环”，前两个用单向链表就能做，最后一个在有环测试中往往用快慢指针。我个人建议，练习这些题的时候先用单向链表写一遍，再想双向链表怎么做，这样能把“指针操作”的肌肉记忆练出来，面试时不慌。

4. 一张表看懂增删改查性能差异，附实测心得

4.1 从复杂度角度对比的核心结论

把前面讲的理论整理成一张对照表，方便面试或复盘时快速扫一眼：

这张表是很多八股答案的原型，但光背这张表不够。我经常遇到候选人反问：既然链表中间插入理论上也是 O(n)，为什么面试题还总说链表插入快？其实题目隐含前提是“已经持有要操作的位置指针”，经典数据结构教材里讲链表插入 O(1) 时，默认你已经有这个节点了。Java 的 LinkedList API 是直接用下标操作的，所以实际使用中常常要先付出遍历成本。

4.2 为什么实测结果经常和理论结论相反

我见过不少人在网上争论“ArrayList 和 LinkedList 到底谁快”，用性能测试一跑，发现 LinkedList 在某些场景下——比如头部插入——确实比 ArrayList 快，但换一个场景又被打回原形。最典型的反直觉场景是：给 LinkedList 做 for 循环 get(i)，性能惨到没法看。

原因很简单：get(0)走一次 O(1)，get(1)又从头走一次 O(1)，依次类推，跑完整个循环的复杂度是 O(n²)，因为每一次 get 都要重新遍历。而 ArrayList 的 for 循环 get 是真正的 O(n)。所以如果代码里写了下面这种循环，请务必改成增强 for 或者迭代器：

// 极其不推荐的写法 for (int i = 0; i < linkedList.size(); i++) { System.out.println(linkedList.get(i)); }

那是不是 LinkedList 就一无是处？也不是。如果场景是“频繁在头部插入”，比如实现一个 undo 栈，LinkedList 的 addFirst 是 O(1)，ArrayList 的 add(0, x) 需要把后面所有元素往后挪，是 O(n)。这个场景下 LinkedList 确实更合适。不过实际开发中，我更推荐 ArrayDeque 来替代 LinkedList 做栈或队列，这个后面第 5 节再说。

4.3 缓存和内存开销：性能差距背后那只“看不见的手”

实测中 ArrayList 遍历速度往往比 LinkedList 快好几倍，除了时间复杂度之外，还有一个容易被忽略的物理层面因素：CPU 缓存。

数组是连续内存，遍历数组时 CPU 会按缓存行批量加载数据，大部分访问都能命中缓存，访问延迟极低。链表节点在内存里是分散的，每次访问一个节点，CPU 都得把这个节点所在的缓存行加载进来，如果两个相邻节点恰好不在同一个缓存行里，那么每走一步都可能发生一次“缓存未命中”，需要到主内存去取，这个延迟比缓存命中高一个数量级。

另一个代价是空间。数组只需要存放真正的数据，而链表每个节点还要额外存 next 和 prev 引用。以 64 位 JVM 默认开启压缩指针的情况来看，一个 Node 对象可能有对象头、数据字段、两个引用字段，还要考虑内存对齐，实际占用的内存可能是数据的倍数。当数据量大到几十万个节点时，LinkedList 的内存开销相当可观。我一直跟团队里的新人强调：理论上分析复杂度是第一步，真做高并发高吞吐的系统，内存布局和缓存友好性往往才是决定性能的关键。

5. 真实场景里怎么选：源码和业务都在给答案

5.1 源码里的答案：HashMap 为什么用“数组 + 链表”

HashMap 是 Java 里使用最频繁的容器之一，它的底层结构恰好同时用到了数组和链表：外层是一个 Node 数组（也叫桶数组），每个桶下面挂着一个链表；当链表太长时，又会转成红黑树。

为什么这么设计？因为数组适合随机访问，通过哈希值可以直接定位到桶下标，O(1) 找到桶；但不同 key 可能哈希冲突，落在同一个桶里，这时候就用链表把冲突的元素串起来。这个混合结构充分发挥了两者的优势：用数组做快速定位，用链表做冲突扩展。

HashMap 的链表设计也给了我们一个重要启发：数组和链表不是互斥的选择，而是可以组合使用的。理解这一点，比单纯背“数组和链表的区别”高一个层次。

5.2 业务场景选型：从消息追加到 LRU 缓存

回到日常开发，到底什么时候用 ArrayList，什么时候用 LinkedList？我总结了几类典型场景。

第一类：读多写少、按下标访问、数据量相对稳定。这种场景闭眼用 ArrayList。比如配置列表、基础数据字典、商品规格列表，基本都是加载后遍历读取，几乎没有中间插入，ArrayList 性能好、内存省、GC 压力小。

第二类：频繁在头部插入或删除，而且数据量确实很大。可以用 LinkedList 或 ArrayDeque，但我的建议是用 ArrayDeque。ArrayDeque 底层是循环数组，头部插入和尾部插入都是 O(1)，而且内存比链表紧凑得多。LinkedList 因为要创建大量 Node 对象，在数据量大的时候 GC 压力会明显上升。

第三类：需要按访问顺序淘汰旧数据，比如 LRU 缓存。Java 里有一个现成的 LinkedHashMap，它本质上是 HashMap 加一条双向链表来维持访问顺序。每次 get 或 put 都会把对应节点移动到链表尾部，当缓存容量超限时，从头节点开始淘汰最久未使用的数据。这种组合设计非常有代表性，理解链表在其中的价值，你就能明白为什么它被叫做“链”表。

5.3 从实用角度给出的选型建议

我自己的经验法则是：默认用 ArrayList，有明确的头部插入、无下标访问需求时才考虑链表结构。对大多数业务系统而言，ArrayList 的“读快写慢”恰好匹配了“读多写少”的真实分布。

另一个建议是代码层面面向接口编程。声明变量时用 List 接口，而不要直接写死ArrayList或LinkedList：

List<String> list = new ArrayList<>();

这样以后需要切换实现，只需要改一行。我在实际重构中无数次受益于这个习惯，因为业务变化后性能瓶颈转移，把 ArrayList 换成 LinkedList 只改一处声明就行。如果不是面向接口编程，调用处用了((ArrayList) list).trimToSize()这类实现特有方法，改起来就痛苦了。

5.4 ArrayList 扩容源码再深入一点

前面提到了 ArrayList 的扩容倍数是 1.5，这里继续看一个细节：扩容之后，数据是怎么“搬”过去的？

elementData = Arrays.copyOf(elementData, newCapacity);

Arrays.copyOf底层调用System.arraycopy，这个方法是 JVM 提供的原生方法，能利用内存拷贝指令快速搬移数据。虽然这是 O(n) 操作，但因为系统级别的拷贝非常快，实际耗时并没有想象中那么可怕。这也是为什么 ArrayList 的 add 均摊后依然被认为是 O(1)。

基于这个源码，我想给一个实操建议：如果一开始就能预估列表大小，尽量使用指定初始容量的构造方法：

List<String> list = new ArrayList<>(1024);

这样可以减少扩容次数、避免无意义的数组拷贝。测试中，创建一个大列表时，指定容量和不指定容量，性能差距可以达到几倍。这个优化成本极低，收益却很直接。

6. 面试官最爱问的变形题：数组和链表的实际操作

6.1 高频题一：链表反转（迭代实现）

链表反转是面试出现频率最高的基础题之一。它的核心思路是：遍历链表，把每个节点的 next 指向前一个节点。因为改了 next 之后，原链表就断了，所以需要一个临时变量保存下一个节点。

public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // 先保存后面要处理的节点 curr.next = prev; // 反转指针 prev = curr; // 前驱后移 curr = next; // 当前节点后移 } return prev; }

这个题值得反复手写，直到闭眼也能写出来。它考的不只是代码，还有对“引用操作”的理解：修改一个节点的 next，不会影响别的节点，你只需要保证在断开之前，把下一步要走的路径记下来。

6.2 高频题二：判断链表是否有环（快慢指针）

判断一个链表里是否存在环，经典解法是快慢指针：慢指针每次走一步，快指针每次走两步，如果链表有环，两者最终会在环里相遇；如果没有环，快指针会先走到 null。

public boolean hasCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }

这个算法的精妙之处在于，它不用额外空间，时间复杂度 O(n)。每次面试官问“能不能不用 HashSet 做”，答案就是快慢指针。它也是后续很多链表题的基础，比如找环入口、找链表中间节点，用的都是同一套思路。

6.3 高频题三：合并两个有序链表

合并两个有序链表也是高频题，递归写法非常简洁：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }

这个递归过程可以理解为：每次比较两个头节点，把小的那个挑出来，再接上“剩下部分合并的结果”。理解递归的关键在于相信函数本身能完成它的职责，不要跳进每一层递归里去抠细节。如果递归理解有困难，也可以用迭代加哨兵节点实现，效果一样。

6.4 高频题四：数组去重的多种姿势

数组去重不一定是链表题，但和数组操作绑定得很紧。我总结了三种常见写法，分别适合不同场景。

最简单的是 Stream 去重：

int[] arr = {1, 2, 2, 3, 3, 4}; int[] result = Arrays.stream(arr).distinct().toArray();

需要保持原顺序，可以直接用 LinkedHashSet。如果数组本身有序，要求原地去重并返回新长度，那就改用双指针：

public int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int slow = 0; for (int fast = 1; fast < nums.length; fast++) { if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }

前两种是工程写法，双指针是算法写法。面试中如果考到原地去重，目的是看你能不能做到 O(n) 时间和 O(1) 空间，这时候用 Stream 虽然能用，但不算通过了考察点。

6.5 我在面试和实操中总结的几个踩坑点

链表题出错率最高的几个点，我列一下，写成代码时多留个心眼。

第一个坑是空指针。操作node.next前没有判断 node 是否为 null。链表相关的题开头永远先处理边界：链表为空、只有一个节点、只有两个节点。

第二个坑是断链。反转链表或者删除节点时，没有先保存后续节点，导致链表丢失。原则是“先处理后路，再改方向”。

第三个坑是数组越界。Java 数组没有动态增长能力，用下标的时候要反复检查是否在 length 范围内，尤其是双指针移动时，循环条件写错很容易越界。

第四个坑和性能相关：不要在 LinkedList 上用 index 循环遍历。前面已经解释过，每次 get 都从头遍历，综合复杂度会退化到 O(n²)，数据量一大直接卡死。

7. 结尾：一些关于这道“基础题”的个人体会

文章写到这儿，核心内容基本都覆盖了。最后分享一点我自己的体会：数组和链表这道题，表面上是两个数据结构的对比，实际上是两种思维方式的对比——连续空间带来的高效与僵化，离散空间带来的灵活与开销。真正的高手不是背答案，而是能在不同场景下迅速判断该付出哪种代价。

我在带新人时常用一个口诀帮他们记忆：数组是“排排坐，吃果果”，链表是“手牵手，串珠子”；数组怕插入删除，链表怕随机访问；ArrayList 适合绝大多数日常场景，LinkedList 更适合频繁头尾操作的场景。但所有口诀都只是辅助记忆的脚手架，真正要建立的是“从内存布局推导操作代价”的能力。

这题还能往深挖的方向不少，比如自定义一个链表类、用数组模拟链表、Redis 的链表实现和 Java 的有什么不同。如果读完这篇文章你产生了“原来我当时背的是结论，现在才算懂原理”的感觉，那这篇分享就没白写。后续想继续深入的话，可以研究下 ConcurrentHashMap 里链表转红黑树的阈值设计、ArrayDeque 为什么比 LinkedList 更快、或者手写一个基于链表的 LRU Cache，这些都是相邻的技术点，一通百通。