Java手写ArrayList与LinkedList：从扩容到哨兵节点全解析

最近帮一位朋友梳理 Java 基础时，他随口说了句："ArrayList 和 LinkedList 我天天用，但你要我现在手写一个，我估计得想半天。" 这话我太熟悉了，几乎每个靠背 API 活着的开发者都会有这个症状。能调用现成容器类很方便，但一旦涉及到底层机制，比如扩容、缩容、节点怎么串、删除时怎么不断链，很多人就开始恍惚了。

这篇文章就围绕 "用 Java 手写动态数组和链表" 这件事展开，把这两个最基础的数据结构从设计思想到完整实现、再到踩坑点全部拆开讲透。你不需要任何比 "朴素 Java" 更高级的工具，也不需要提前背任何面试题，跟着走一遍，你会发现自己对 ArrayList 和 LinkedList 的理解会彻底从"会用"变成"会用也会修"。

1. 为什么手写容器比调用 API 更有价值

1.1 面试总考手写容器的真实原因

先聊一个很多人想不通的问题：明明有现成的 ArrayList，面试官为什么非要你手写一个？

我自己的切身体会是，考察手写容器的过程，其实是在模拟一个很小但真实的工程推导，面试官真正想看的不是你记不记得 API，而是你在面对"一个可以动态增长的数据结构"时，会不会主动去思考三个问题：

1. 容量不够了怎么办——涉及扩容策略，要分析均摊复杂度。
2. 删除之后空间要不要回收——涉及缩容策略，要权衡内存与时间的取舍。
3. 索引边界谁来保证——涉及异常处理，要区分"数组越界"和"结构非法"。

这三个问题，正好是 ArrayList 源码的核心。工作中你没必要重写一份，但排查性能瓶颈、分析堆内存占用、处理大数据量插入时，你确实会遇到一模一样的工程决策。所以面试官考的不是代码量，而是你的边界意识。

1.2 数据结构的意义：数组与链表的本质差异

动态数组和链表，从名字上看都是"可变的线性序列"，但它们底层用的物理存储完全不同。

数组是连续内存块，下标访问一步到位；链表是离散节点，靠引用串起来。这个区别带来一个核心矛盾：数组优在随机访问，链表优在任意位置的插入删除（前提是已经定位到那个节点）。

如果你只停留在"用 API"的层面，这个矛盾只是个概念。但当你亲手写过一遍之后，你会发现"随机访问与插入删除不可兼得"这句话变得极其具体——因为你在扩容时做过数组拷贝，在链表删除时亲手处理过节点断开，这些操作背后的代价你算是真正踩过一遍了。

2. 动态数组：从字段定义到扩容机制的完整实现

2.1 字段与构造器：泛型数组的经典坑

我先写一个最朴素版本的动态数组骨架，底层存储用对象数组，配合泛型转换。

public class DynamicArray<E> { private Object[] data; private int size; public DynamicArray() { this(10); } public DynamicArray(int capacity) { if (capacity < 0) { throw new IllegalArgumentException("容量不能为负数"); } data = new Object[capacity]; size = 0; } }

很多人第一次写这里会卡住：为什么不能直接写new E[capacity]？

原因是泛型在 Java 里是编译期概念，运行时被擦除，JVM 根本不知道 E 是什么类型。用new Object[capacity]然后配合强制转换，是最常见也最稳妥的做法。具体来说，每次从数组中拿出来时都用(E)强转，返回给调用者，外层类型检查仍然由编译器完成。这里有个小技巧：可以给 get 方法加上@SuppressWarnings("unchecked")注解，把内部强转的警告压掉，但千万不要压掉调用方的类型检查，那样你的泛型安全就形同虚设了。

2.2 尾插与扩容：1.5 倍背后的数学逻辑

动态数组最关键的是 add，核心在于"容量不足时自动扩容"。

public void add(E element) { ensureCapacity(size + 1); data[size++] = element; } private void ensureCapacity(int minCapacity) { if (minCapacity > data.length) { grow(minCapacity); } } private void grow(int minCapacity) { int oldCapacity = data.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity < minCapacity) { newCapacity = minCapacity; } if (newCapacity > Integer.MAX_VALUE - 8) { newCapacity = Integer.MAX_VALUE - 8; } data = Arrays.copyOf(data, newCapacity); }

关键的扩容系数是 1.5 倍，是oldCapacity + (oldCapacity >> 1)的位运算写法。你可能第一反应是"为什么不用 2 倍"？

我结合自己的实测经验算过一比账：如果每次扩容翻倍，从容量 10 到能装下 100 万个元素，需要约 17 次扩容；如果按 1.5 倍走，大约需要 28 次。扩容次数多了，总拷贝量确实变大了，但每次扩容后上次扩容浪费的空间也更少，整体内存占用更克制。

用极端情况来说更直观：

• 容量 10 扩容翻倍到 1.6 万时，中间闲置空间很大；用 1.5 倍则每个阶段浪费率更低。
• 大数组对象在堆里占连续空间，分配过大容易触发 GC 压力，1.5 倍比 2 倍温和得多。

所以官方 ArrayList 也选 1.5 倍，这是时间与空间之间的一个折中解。你自己实现时也可以选 2 倍，但要意识到"更快"的背后付出了内存代价，没有免费的午餐。

2.3 中间插入与删除：System.arraycopy 的灵活使用

尾插是最简单的场景，但如果你要add(int index, E element)，就必须处理元素整体右移。这里我直接调用了System.arraycopy，因为这是 JVM 层面的内存拷贝，原生方法，比手动 for 循环快不少。

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); System.arraycopy(data, index, data, index + 1, size - index); data[index] = element; size++; } @SuppressWarnings("unchecked") public E remove(int index) { rangeCheck(index); E oldValue = (E) data[index]; int numMoved = size - index - 1; if (numMoved > 0) { System.arraycopy(data, index + 1, data, index, numMoved); } data[--size] = null; shrinkIfNeeded(); return oldValue; }

这里有一个重要细节值得多说两句：删除时data[--size] = null不能省。

有人会想，size 已经减一了，数组里残留的那个引用反正访问不到了，留着有什么问题？问题很大。这个引用会让对象无法被 GC 回收，这就是所谓的内存泄漏隐患。尤其是你的数组里存了大对象、连接对象或监听器时，一直保留这个引用，堆内存会越来越高，最终引发 OutOfMemoryError。写数据结构的正确习惯就是：清除多余引用，让 GC 可以正常工作。

另一个细节是搜索顺序的查错重点：System.arraycopy的五个参数分别是"源数组、源起点、目标数组、目标起点、长度"，中间两个新旧位置别写反了。我见过不少人在模拟 ArrayList 时把目标起点和源起点搞混，结果数据要么全变成 null，要么原地没动。

2.4 缩容策略：什么时候缩、缩多少

扩容好理解，但很多手写实现漏了缩容。缩容的理由很朴素：数组一旦扩到很大，即使你删到只剩几个元素，那块大空间也不会自动还回去。如果这是个长期运行的容器，内存就白白被占着。

private void shrinkIfNeeded() { int capacity = data.length; if (capacity > DEFAULT_CAPACITY && size < capacity / 4) { data = Arrays.copyOf(data, capacity / 2); } }

这里的触发阈值是"有效元素小于容量的四分之一"，然后缩到一半。为什么用 1/4 而不是空了就缩？

因为缩容本身也要拷贝数据，频繁缩容会造成抖动。如果设定"删一个元素就缩"，你在容量边界反复增删时，扩容和缩容会互相打架，性能反而更差。留出 1/4 的缓冲区间，我实测过在"周期性大批量删除"的场景下，内存回落明显，性能损失却几乎感知不到。这个策略属于典型的不对称设计：扩容要激进，避免频繁触发；缩容要保守，避免抖动。

3. 链表：哨兵节点与双向链表的完整实现

3.1 哨兵节点：让边界条件自然消失

如果说动态数组的核心是"内存拷贝和索引"，那链表的核心就是"引用操作的顺序问题"。删除一个节点时，如果忘了先把前驱的 next 指向后继，链表就"断链"了。

我第一次实现无哨兵版本的单链表时，被头节点的插入删除折磨得够呛。每次都要单独判断"当前是不是头节点"，很烦，还容易漏。后来实践了哨兵节点方案，才算彻底清爽。

所谓的哨兵，就是永远存在的、不存业务数据的假节点。它在最前面和最后面各放一个，业务节点都夹在它们中间。头节点永远有前驱（哨兵）、尾节点永远有后继（哨兵），任何位置插入删除统一处理，再也不用特判边界。这个思路不止链表适用，很多算法题里"dummy node"就是它的同款用法，专门用来消除边界特判。

3.2 双向链表类框架：初始化时就把环扣好

我直接实现双向链表版本，工程上更实用，逻辑也对称、更优雅。

public class LinkedList<E> { private Node<E> head; private Node<E> tail; private int size; private static class Node<E> { E item; Node<E> prev; Node<E> next; Node(E item, Node<E> prev, Node<E> next) { this.item = item; this.prev = prev; this.next = next; } } public LinkedList() { head = new Node<>(null, null, null); tail = new Node<>(null, head, null); head.next = tail; } }

初始化时，head 的 next 指向 tail，tail 的 prev 指向 head，形成"空链表"。此时 head 和 tail 之间没有任何业务节点。你可能会问：既然引入了 tail 哨兵，为什么不直接用尾节点变量，省一个哨兵？

用一个真正的尾指针确实也能省一个节点，但代价是所有尾部操作都要判断"链表是否为空"。比如在空链表上删除尾节点，尾指针是 null，你得单独处理。一旦用了两个哨兵，空链表的"空"也完全正常，所有操作代码对空与非空是一模一样的逻辑，不需要 if 分支。这个简洁性在复杂操作里非常值钱。

3.3 统一插入与统一删除：addBefore 和 unlink 的对称之美

双向链表最核心的两个私有操作，一个是addBefore，另一个是unlink。它们几乎包办了一切插入和删除场景。

public void addFirst(E element) { addBefore(element, head.next); } public void addLast(E element) { addBefore(element, tail); } public void add(int index, E element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException(); } Node<E> succ = (index == size) ? tail : nodeAt(index); addBefore(element, succ); } private void addBefore(E element, Node<E> succ) { Node<E> pred = succ.prev; Node<E> newNode = new Node<>(element, pred, succ); pred.next = newNode; succ.prev = newNode; size++; }

addBefore的逻辑是"在 succ 节点前面插入新节点"。你传头哨兵的下一个节点进来就是头插，传尾哨兵进来就是尾插，传指定索引对应的节点进来就是中间插入。三种场景全部收敛成一个操作。

删除对称地收敛成unlink：

public E removeFirst() { if (head.next == tail) { throw new NoSuchElementException("链表为空"); } return unlink(head.next); } public E removeLast() { if (tail.prev == head) { throw new NoSuchElementException("链表为空"); } return unlink(tail.prev); } public E remove(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException(); } return unlink(nodeAt(index)); } private E unlink(Node<E> node) { E item = node.item; Node<E> pred = node.prev; Node<E> next = node.next; pred.next = next; next.prev = pred; node.item = null; node.prev = null; node.next = null; size--; return item; }

写这段代码时最值得注意的就是顺序。pred.next = next和next.prev = pred这两行必须都在 node 还在链表中的时候完成。如果你先把 node 的 next 置空了，再想拿到后继节点，你得提前用局部变量保存。这其实就是unlink开头的Node<E> next = node.next为什么非要先取出来存着的原因。我见过不少初学版本在这个顺序上栽跟头，导致删除一个节点之后，后面整个链表都丢了。

删除之后，把 node 的 item、prev、next 全部置空，这个动作同样有内存回收的作用，让节点对象本身可以被 GC 直接回收，而不是随链表残留持有引用。

3.4 节点定位优化：从两端向中间搜索

链表的随机访问效率天然不如数组，但也不是只能傻傻从头走到尾。当双向链表结构完整时，我可以根据插入位置判断离哪头更近，然后从近的那头开始找。

private Node<E> nodeAt(int index) { if (index < size / 2) { Node<E> cur = head.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur; } else { Node<E> cur = tail; for (int i = size; i > index; i--) { cur = cur.prev; } return cur; } }

这是一个很小的优化，但非常贴合双向链表的特性：既然有 prev 指针，搜索时就可以双向并行。实际使用时，如果你经常按下标取中间某个元素，这个实现比纯头到尾走快近一半。也就是说，最好的复杂度依然是 O(n)，但常数系数减半。

这整个双向链表实现，和 JDK 内部 LinkedList 的结构几乎同构。你想想看，读源码时觉得"这不就是些指针操作吗"，但自己动手写一遍，才能真正体会为什么每个 field 都要手动置空，为什么插入时代码里的"prenode 的 next 先指向 newnode"的顺序绝不能变。这属于从"看着懂"到"自己会分毫不差地实现"的跨越。

4. 复杂度对比：什么时候该用哪个

4.1 复杂度对照表

把数组和链表的核心操作复杂度一键拉平，你会发现一个规律：没有谁全面优于谁，一切取决于你的操作位置。

这张表背后真正重要的是：当你说"LinkedList 插入快"时，前提必须是你同时满足"已经拿到了那个位置的节点引用"且"插入的是中间位置"两个条件。如果你只给一个下标，它照样要 O(n) 先走到那个位置，最后整体依然是 O(n)。很多人背了这个结论却不理解前因后果，实战选型时就会踩坑。

4.2 实测数据：链表在尾插上为什么会输给数组

从复杂度表看，尾插一个 O(1) 均摊、一个 O(1) 严格，似乎是差不多的。但真实运行时差异非常明显。我写了个小 Demo，分别向 ArrayList、LinkedList 和自己手写的 DynamicArray 尾插 100 万次，再测随机访问 1 万次。

实测结果大致如下（不同机器有波动，趋势一致）：

为什么尾插理论上都是 O(1)，链表却慢好几倍？因为链表每次插入都new一个节点对象，还附带两个引用赋值的开销。每个 Node 对象在堆里是离散分布的，遍历时 CPU 缓存完全不连续，缓存局部性极差。数组则是连续内存，顺序访问时 CPU 预取机制能发挥威力。可以说，现代 CPU 高度"偏爱"连续内存结构，这告诉我们对复杂度的判断不能脱离硬件现实。

如果再加上内存占用，链表的 Node 还要存 prev 和 next 两个引用，64 位 JVM 上每个节点额外多占据约 16 字节。这个开销在 100 万个节点时就是 16MB 级别的额外负担，多为这些容器做内存取舍是必要的意识。

4.3 项目选型的两个真实场景

基于这些观察，我一般给出一刀切但实用的选型建议：

• 如果主要操作是"按索引读"或"尾部写入"，比如日志列表、用户会话列表，无脑选动态数组。
• 如果主要操作是"头部频繁增删"，比如任务队列、消息缓冲区、撤销栈，链表优势明显。

实践中还有一个很少被人提到的点：如果元素是小对象或值类型，动态数组由于连续内存和更少对象头，GC 压力更小；而链表因为大量小对象导致频繁 GC，所以内存敏感场景下我更倾向数组。

5. 常见问题与排查技巧实录

5.1 边界条件：头插、尾插、空链表删除

我在帮 A 同学 review 他的链表代码时，发现他最常出的 bug 都集中在边界：

• 删除头节点，前驱是 null，直接node.prev.next = node.next抛 NullPointerException。正确玩法是用哨兵，或单独判 null。
• 插入到 index == size 的位置，也就是尾部追加，如果代码里直接调nodeAt(size)就会越界，得专门判断"等于 size 时走 tail 哨兵"。
• 空链表删元素，正确行为是抛出 NoSuchElementException 或返回 null，而不是先解引用再说。

排查这类问题最有效的方法是画节点图。纸上画四个节点，模拟一次删除，把三根箭头画出来，再把代码里的每一行赋值和箭头对应起来。很多刷题这么干的人，写链表比直接凭感觉敲要稳定得多。

5.2 迭代器：快速失败机制不是玄学

完整的数据结构实现里，迭代器是个绕不开的话题。JDK 里的 ArrayList、LinkedList 都给迭代器加了"快速失败"机制：遍历过程中如果有结构性修改（加或删，但不包括改值），迭代器会立刻抛 ConcurrentModificationException。

实现思路是在容器里维护一个modCount字段，每次增删都自增。迭代器初始化时记住expectedModCount = modCount，每次 next 时检查二者是否一致，不一致就抛异常。

public Iterator<E> iterator() { return new Iterator<E>() { private int cursor = 0; private final int expectedModCount = modCount; @Override public boolean hasNext() { return cursor < size; } @SuppressWarnings("unchecked") @Override public E next() { checkForComodification(); if (!hasNext()) { throw new NoSuchElementException(); } return (E) data[cursor++]; } private void checkForComodification() { if (expectedModCount != modCount) { throw new ConcurrentModificationException("遍历过程中容器被修改了"); } } }; }

这个机制的底层思想就是"宁可快速暴露并发问题，也不要多线程访问时静默出错"。你要是自己在写容器时也留了这个字段，面试时讲出来，能很直接地证明你不仅会写数据结构，还考虑过它的行为契约。

5.3 内存泄漏：数组引用与节点引用

前面在动态数组删除时已经提到了置空引用，链表这边也一样。删节点后要把 item、prev、next 都设为 null。别忘了链条上的帮手：如果一个链表对象本身被外部长期引用，但内部节点全部删光了，哨兵节点总是后被 GC，这个几乎无影响；但如果你删的是中间一个节点，它的 item 会一直撑着业务对象不释放，这个隐患必须重视。

可以顺手在 remove 方法里执行"手动置空"三步曲之后，测试一下：从链表里删除一个大字符串，然后用 jmap 或 MAT 看堆，确认字符串对象没有被强引用残留。这属于能写 bug、也能查 bug 的完整闭环。

5.4 增删交替时的抖动问题

如果你手写了缩容逻辑，有可能出现一个经典现象：容量临界时频繁插入删除，扩容和缩容反复触发，性能断崖式下降。排查这个问题的思路很简单——在 grow 和 shrinkIfNeeded 中各加一行日志输出，打印当前容量和 size，然后跑一段增删交替循环。你会看到容量在某个阈值附近反复震荡。

解决的常见做法正是前面提到的"不对称阈值"：扩容触发线是 100%，缩容触发线是 25% 且缩到 50%，中间留足缓冲区间，让抖动不会发生。这也是我在实现里特意采用不一致参数的原因，不是疏忽，而是刻意设计。

6. 基于经验的体会收尾

如果让我只挑一句话总结这次实现过程的体会，我会说：数据结构不是背出来的，是画着节点图和边界条件调出来的。动态数组和链表这两兄弟，一个玩的是"连续空间的搬运和变换"，一个玩的是"离散节点的引用编排"，亲手把他们从零写一遍之后，你再回去看 ArrayList 和 LinkedList 源码，会觉得每一个字段、每一个判断都顺理成章，而不是天书。

我把这两个完整实现放在一起对比着写，不是因为多高深，而是因为它们最适合作为入门阶段最直接的"逻辑训练场"。如果你也打算动手写一遍，我的建议是别抄我的代码，先自己设计字段和边界规则，遇到 bug 时再对照本文的踩坑清单排查。写坏了不丢人，反正在我见过的所有"手写容器"经历里，都是先把边界炸个几遍、再改出肌肉记忆才真正娴熟的。

以后再面试、再排查线上容器性能问题，你心里就有底了。希望这篇文章能让你的"代码肌肉记忆"更厚一层。