如果你面前有两种数据结构第一种是一排连在一起的座位座位号从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()结果打出来是一串[I4554617c之类的地址这是因为数组没有重写 Object 的 toString。正确做法是用Arrays.toString(arr)如果是二维数组用Arrays.deepToString(arr)。数组去重最朴素的写法是用LinkedHashSet它能同时做到去重和保持插入顺序Integer[] arr {1, 2, 2, 3, 3, 4}; LinkedHashSetInteger 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 NodeE { E item; NodeE next; NodeE prev; }每个节点有三个字段存的数据 item、指向后继的 next、指向前驱的 prev。整个链表还维护着 first 和 last 两个哨兵引用分别指向头节点和尾节点。正是因为持有 last 引用LinkedList 在尾部插入节点的效率才是 O(1)不需要从头遍历到尾部。理解了 Node 结构很多链表面试题的解题思路就呼之欲出了链表反转的本质就是不断把每个节点的 next 和 prev 调换方向判断链表是否有环就需要用快慢指针删除某个节点只需要把前驱的 next 直接指向它的后继让这个节点“从链上摘下来”。3.2 为什么插入删除确实快只改引用不搬数据链表的插入和删除之所以理论上快是因为它只做指针操作。比如在节点 A 后面插入新节点 X只需要四步把 X 的 prev 设为 AX 的 next 设为 A 的 nextA.next.prev 设为 XA.next 设为 X。不管链表里已经有多少个节点这四步操作不会因为链表长度而变慢。这跟数组对比非常鲜明。数组往中间插一个元素需要把插入位置之后的所有元素都往后挪一格最坏情况下要挪 n 个元素时间复杂度 O(n)。所以从“操作本身”来看链表插入确实快。但请注意我强调的是“找到位置之后”这个前提在真实使用中非常重要后面第 4 节会详聊。3.3 查找的代价从 O(1) 降到 O(n)链表最大的短板是没有随机访问能力。就像开头说的珠子你不知道第 100 颗珠子长什么样必须从第一颗开始顺着线数过去。在 Java 的 LinkedList 里如果你想 get(500)源码会做一个优化先判断目标位置离头部近还是离尾部近然后从较近的一端开始遍历。if (index (size 1)) { NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { NodeE 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 从复杂度角度对比的核心结论把前面讲的理论整理成一张对照表方便面试或复盘时快速扫一眼操作数组 / ArrayList链表 / LinkedList随机访问 get(i)O(1)O(n)头部插入 add(0, x)O(n)需要整体后移O(1)但前提是拿到头节点尾部插入 add(x)均摊 O(1)扩容时 O(n)O(1)LinkedList 持有尾节点中间插入 add(i, x)O(n)搬移元素O(n) 找位置 O(1) 改引用删除 remove(i)O(n)搬移元素O(n) 找位置 O(1) 改引用内存占用连续空间无额外指针开销每个节点额外占用 prev/next 引用这张表是很多八股答案的原型但光背这张表不够。我经常遇到候选人反问既然链表中间插入理论上也是 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或LinkedListListString 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)。基于这个源码我想给一个实操建议如果一开始就能预估列表大小尽量使用指定初始容量的构造方法ListString 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这些都是相邻的技术点一通百通。