1. 从链表到容器为什么这章是所有算法课的基石如果你翻过《算法第4版》Algorithms_4th大概率会和我一样在第一章就被三种最基础的抽象数据类型ADT卡住过——Bags背包、Queues队列、Stacks栈。表面上它们只是三种装东西的盒子但如果你把整本书往后翻会发现后面所有的高级结构树、图、哈希表、排序算法、最短路径……几乎每一个都在这三种容器之上做文章。这一章不是热身而是整本教材真正的起跑线。这一章解决的核心问题很朴素在Java里写算法时我们怎么存储、怎么访问数据数组可以吗可以但数组的长度固定、插入删除麻烦而且一旦涉及泛型就有各种类型擦除的坑。链表呢链表灵活但手动管理指针容易出错。于是这章给出了三个标准答案——Bag、Queue、Stack用它们各自的访问顺序规则覆盖算法中最常见的几种数据访问模式先进先出、后进先出、只收集不回头。适合谁来读说实话不只是正在啃这本书的学生。哪怕你是工作两三年的开发者如果你发现自己在写代码时经常纠结到底是拿数组还是拿链表、这个队列到底该用LinkedList还是ArrayDeque那你在这章里会找到一套特别清晰的判断依据。我当年是工作后回头补算法基础才读的这章读完之后最大的感受是以前写业务代码靠感觉选容器现在有了一整套理论支撑。这章的原理解释非常教科书但正因为教科书很多细节都是暗线。我会把这章拆成两条线来讲一条是设计思路解释为什么这章要把三种容器放在一起讲另一条是实现细节把教科书里点到为止的链表实现、动态数组扩容、迭代器设计这些坑都给填上。在动手过一遍源码之后你会发现这一章的量其实很足足够你消化一阵子的。2. 三种容器设计思路拆解访问顺序决定一切2.1 为什么是包、队列、栈三兄弟一起讲在讲解实现之前我想先聊聊一个很多人忽略的问题为什么这三种容器要放在同一节里它们的用途差异其实非常大但存在一个共同的数学结构——它们都是集合都支持两个最基本的操作插入insert和删除delete。区别只有一个删除哪一个。Bag只插入不删除或者说不关心删除顺序。Queue删除最先进来的那一个FIFOFirst-In-First-Out。Stack删除最近进来的那一个LIFOLast-In-First-Out。你看仅仅一个删除策略的差异就让三个容器走上了完全不同的道路。这就好比餐厅的出餐口你排队点单先来的先做这是队列你往书包里塞书最后塞进去的反而最容易抽出来这是栈你把一堆物品丢进一个袋子之后想拿哪个拿哪个这是背包。教材把这三种容器放在一起是想让你建立一种抽象思维底层数据结构链表或数组是通用的但通过不同的接口暴露就变成了行为完全不同的容器。这也是面向对象设计里封装和接口隔离最经典的教学案例。后面你写代码时如果需要一个只进不出的缓冲区不该用List而应该用Bag如果需要处理嵌套结构优先想到Stack如果需要处理公平调度优先想到Queue。2.2 数组实现 vs 链表实现的核心取舍教科书在实现这三种容器时用了两种底层物理结构数组Array和链表Linked List。这是算法生涯里第一个重要的二选一我建议你从这章开始就建立一套自己的判断体系。数组实现的优势是内存连续索引访问O(1)CPU缓存友好。劣势是插入和删除非尾部是O(n)且扩容时需要整体搬运。链表实现的优势是插入和删除已知前驱节点时是O(1)无需连续内存扩容零成本。劣势是随机访问O(n)且每个节点要额外存储下一个节点的指针内存占用更高。一个很关键的点教材里没有明说但实现里隐含了用数组实现栈是最优解用链表实现栈和队列是最符合直觉的解用链表实现Bag是最省事的解。为什么因为栈的插入和删除都发生在同一端栈顶数组的尾部操作就是O(1)配合动态扩容均摊成本也很低而队列需要在两端操作数组在头部删除是O(n)除非用环形数组链表则天然适合。这些结论我建议你亲手写一遍实现才会有体感。2.3 泛型和迭代器这章里的隐形主角如果你只是粗读一遍很容易把泛型Generics和迭代器Iterator当成Java的附属语法略过。但实际上这一章是整本书第一次系统性使用泛型和迭代器的地方也是大多数初学者第一次在这里被编译错误劝退的地方。先说泛型。为什么容器必须用泛型因为如果容器只能存Object你取出来就得强转强转就容易ClassCastException而且代码里全是脏兮兮的强制转换。用了泛型容器在编译期就能保证类型安全。但Java的泛型是类型擦除实现的这里有一个特别容易踩的坑你不能直接创建泛型数组。例如T[] items new T[10]是无法编译的。教材里的解法是创建Object数组然后强转T[] items (T[]) new Object[10]。这个写法会有个编译警告但确实是通用解法。你千万别试图用new T[10]那是过不了的。再说迭代器。为什么容器要实现Iterable接口因为Java的for (String s : stack)语法糖本质上调用的就是容器的iterator()方法。这个设计把遍历逻辑从容器中解耦出来你可以为同一个容器实现多个不同的迭代器比如正序遍历、反序遍历。教材里通过内部类实现迭代器并且强调了一个重要的设计原则迭代器应该是一个快照或者说它维护的是当前遍历的状态但容器本身不知道迭代器的存在。有一个细节值得注意迭代器里的remove()方法教材里直接抛了UnsupportedOperationException这是有意为之。因为很多数据结构比如Bag压根不支持删除与其让迭代器提供无用操作不如直接禁用。这个设计思路后来在Java标准库中被广泛采纳。3. 核心实现细节与实操要点3.1 链表的节点设计内部类 vs 静态内部类实现链表容器时第一个要决定的事就是节点类怎么写。教材里用了非静态内部类private class Node我见过不少读者照着敲代码也能跑通但不清楚为什么不用静态内部类。非静态内部类有个隐藏特性每个实例都持有外部类实例的引用。也就是说每个Node节点都认识它所属的容器。这在链表容器里不是必需的反而会带来两个问题一是内存多占一个引用字段二是可能造成外部类无法被GC回收如果Node被错误地泄露出去。但如果改成静态内部类private static class Node就没有这个问题。你可能想问那为什么教材要用非静态的因为教学代码追求的是读起来简单。对一个学习者来说Node直接访问外部类的成员变量是直观的但实际上静态内部类也能做到通过参数传递。我的建议是如果你在写自己的库用静态内部类如果你在照着教材学习可以先用非静态的理解之后改成静态的体会一下差异。这里还有一个细节节点类里存的item和next字段在教材里没有加final。但如果你认真考虑过会意识到next其实在节点生命周期内最多改变一次甚至不改变所以用final修饰next在逻辑上更严谨。有些同学喜欢写防御性代码这个习惯在算法学习中越早养成越好。3.2 动态数组扩容与缩容均摊分析的艺术数组实现栈的核心难点不在压栈和弹栈本身——那就是赋值和指针移动——而在数组的扩容和缩容策略。这里有两个经典问题什么时候扩容什么时候缩容教材给出的答案是插入时如果数组满了扩容为原来的2倍弹出时如果元素个数只有数组长度的1/4缩容为原来的一半。这个2倍扩、四分之一缩的设计很多读者第一次看会觉得很奇怪为什么不满了就加10个为什么弹到一半就缩其实这背后是均摊分析Amortized Analysis的思想。如果我们每次满就加一个固定值比如10那么连续插入n个元素的时间是11...11011...110...最坏情况是O(n^2)因为每次扩容都要把旧数据复制到新数组。但如果按2倍扩容扩容次数只有O(log n)次总复制次数是124...n2n-1均摊到每次插入就是O(1)。为什么缩容选择1/4而不是1/2因为如果满时扩容到2倍而你在容量为2N时弹到N就立刻缩容那紧接着你压入一个元素又会触发扩容到2N这样反复在阈值附近操作会导致频繁扩容/缩容形成所谓的抖动thrashing。把触发线调到1/4留出了一倍的缓冲空间就避免了这个问题。这是一个非常优雅的工程设计你以后写任何动态数组包括Java的ArrayList都可以参考这个思路。3.3 可迭代容器设计内部迭代器与Fail-Fast机制让容器实现IterableT接口需要在内部提供一个IteratorT的匿名类或内部类。这里面有几个实操细节值得展开。第一迭代器应该记录当前节点的引用而不是返回一个数组的副本。很多新手写迭代器时会先把所有元素复制到一个临时数组再遍历数组——这虽然能跑但空间复杂度O(n)就白费了而且违背了惰性求值的初衷。正确的做法是栈的迭代器用一个Node current first队列迭代器用Node current first数组实现的栈则用一个int i N每次调用next()时相应移动。第二迭代器是否需要fail-fast快速失败Java标准库里的ArrayList、HashMap等容器都有fail-fast机制如果在迭代过程中检测到结构性修改比如调用add或remove迭代器会抛出ConcurrentModificationException。教材里的迭代器没有做这个检查因为这是教学代码追求最小实现。但如果你在生产环境写自己的容器我强烈建议加上modCount计数器的检查。这可以帮你尽早发现一边遍历一边修改这种隐蔽的bug否则会出现难以定位的间歇性错误。第三迭代器的hasNext()和next()方法要对边界情况做防御。比如next()在没有更多元素时应该抛NoSuchElementException而不是返回 null 或数组越界。这个细节虽然小但写容器库时接口约定必须明确。3.4 对象游离GC视角下的隐藏内存泄漏这一节我要特别强调一个章节里容易一眼带过的知识点——对象游离Loitering。教材里这样描述在栈的pop()实现中如果不把弹出的数组项设为null那么数组依然持有这个对象的引用即使外部已经不再使用它GC也无法回收它。听起来很简单但实际开发中这个问题极其隐蔽。我给你讲一个真实场景。某次我在写一个简单的事件处理器时用了一个数组实现的栈来暂存事件对象。弹出后我直接用return items[--N]没有把items[N]置为null。功能一切正常但服务跑了一个月后内存曲线稳步上升最终OOM。排查了很久才发现那些已经被弹出的事件对象因为数组中还保留着引用GC永远无法回收它们。这就是游离对象导致的内存泄漏——不是传统意义上无法访问的泄漏而是其实还能访问但永远不再有用的泄漏。所以无论你用链表还是数组实现容器只要元素是从容器中移除的都应该立刻清除引用。链表实现中将first指向下一个节点并置空旧节点的item数组实现中将items[N]置为null。这个习惯养成了你能在未来的开发中避开一个大坑。4. 实操过程与核心环节实现4.1 手写链表实现的栈从节点类到迭代器现在我们把理论落到代码上。教材里用链表实现栈我在这里给出一个完整可运行的版本加了详细的注释并在实现上做了一些生产级优化。import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedStackItem implements IterableItem { private NodeItem first; // 栈顶元素 private int n; // 元素数量 private static class NodeItem { private Item item; private NodeItem next; } public LinkedStack() { first null; n 0; } public boolean isEmpty() { return first null; } public int size() { return n; } public void push(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item first.item; first first.next; n--; return item; } public Item peek() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); return first.item; } public IteratorItem iterator() { return new LinkedIterator(first); } private class LinkedIterator implements IteratorItem { private NodeItem current; public LinkedIterator(NodeItem first) { current first; } public boolean hasNext() { return current ! null; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item current.item; current current.next; return item; } } }几个关键点我再重复强调一遍Node用静态内部类避免持有外部类引用。predicate检查isEmpty()要在pop()和peek()中做不然你会在空栈上解引用空指针。迭代器是单链方向从栈顶往栈底遍历。这个顺序对栈来说是符合直觉的后进先出。push操作里用oldFirst暂存旧节点再新建节点指向它。头插法O(1)。这里pop()我其实没有把first.item置为null因为链表节点会被GC回收如果外部不再引用。但如果你保存了弹出的Node引用请记得置空。这就是我在上一节提到的游离对象问题在链表实现中的变体。4.2 数组实现的栈动态扩容和缩容的完整代码链表实现的栈逻辑简单但每个节点要存一个引用内存开销大。数组实现更紧凑但需要处理扩容。下面是完整的数组栈实现import java.util.Iterator; import java.util.NoSuchElementException; public class ResizingArrayStackItem implements IterableItem { private Item[] items; private int n; public ResizingArrayStack() { items (Item[]) new Object[2]; n 0; } public boolean isEmpty() { return n 0; } public int size() { return n; } private void resize(int capacity) { Item[] temp (Item[]) new Object[capacity]; for (int i 0; i n; i) { temp[i] items[i]; } items temp; } public void push(Item item) { if (n items.length) { resize(2 * items.length); } items[n] item; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item items[n - 1]; items[n - 1] null; // 避免对象游离 n--; if (n 0 n items.length / 4) { resize(items.length / 2); } return item; } public IteratorItem iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements IteratorItem { private int i n; public boolean hasNext() { return i 0; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return items[--i]; } } }这份代码里有几个细节值得你反复琢磨resize方法里创建新数组后要手动拷贝所有旧元素。这里我用了一个循环某些书籍里会建议用System.arraycopy性能更好。但在学习阶段手写循环更能加深理解。push里的扩容条件是n items.length。注意此时数组中所有位置都已被占用再插入就必须扩容。扩容倍率2这是时间与空间的平衡点。扩容后旧数组会被GC回收新的数组长度是原来的2倍。pop里的缩容条件是n 0 n items.length / 4。这里有一个n 0的守卫防止空栈时items.length为0的情况理论上不会发生因为初始容量是2但防御性代码总是好的。迭代器实现的是从栈顶到栈底的遍历。因为栈是LIFO迭代器方向应该从最近的元素开始也就是数组尾部。我记得有一次写迭代器时方向搞反了导致输出顺序完全不对调试了半天才发现。这个方向细节很值得记下来。4.3 队列的链表实现头尾双指针怎么维护队列比栈多一个限制入队在一端出队在另一端。用链表实现时我们需要维护两个指针first指向队头出队端last指向队尾入队端。public class LinkedQueueItem implements IterableItem { private NodeItem first; private NodeItem last; private int n; private static class NodeItem { private Item item; private NodeItem next; } public boolean isEmpty() { return first null; } public int size() { return n; } public void enqueue(Item item) { NodeItem oldLast last; last new NodeItem(); last.item item; last.next null; if (isEmpty()) { first last; } else { oldLast.next last; } n; } public Item dequeue() { if (isEmpty()) throw new NoSuchElementException(Queue underflow); Item item first.item; first first.next; n--; if (isEmpty()) { last null; // 避免游离对象 } return item; } }有个细节我特别想强调在enqueue时如果队列为空first和last必须同时指向新节点。如果不处理这个分支老节点oldLast是null直接oldLast.next last就会空指针。这个边界条件是链表队列最常见的bug来源。在dequeue时删除的是first节点。但要注意如果删除后队列空了last仍然指向旧的队尾节点这个引用是游离的必须把last置为null。这就是对象游离在链表实现中的又一个变体。教科书代码里我见过不处理这个分支的版本功能上不报错但严格来说内存管理有瑕疵。队列的迭代器实现和栈类似只是从first开始遍历。这里不再赘述。4.4 背包的实现最简容器但隐藏了迭代器的强大背包Bag是所有容器里最简单的一种只往里加东西不给删除的方法。但别小看它在后面的图算法和统计计算中背包非常常用——比如你可能需要收集图中所有顶点的邻居然后遍历一遍统计信息但你并不关心访问顺序。public class BagItem implements IterableItem { private NodeItem first; private int n; private static class NodeItem { private Item item; private NodeItem next; } public void add(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public boolean isEmpty() { return first null; } public int size() { return n; } public IteratorItem iterator() { return new LinkedIterator(first); } }背包的add直接采用头插法不需要维护last指针因为访问顺序不重要。你注意到没有它的实现其实和链表栈的push一模一样。唯一的区别是接口层没有pop方法。这正好印证了我前边说的底层物理结构可以复用但通过接口约束出不同的抽象数据类型。背包在算法中的一个典型应用场景是图的邻接表。当你用BagInteger[] adj来存储每个顶点的相邻顶点时你只关心能枚举所有邻居不关心邻居的顺序。这时候用一个只支持添加和遍历的容器从语义上就避免了误用。我在实际项目里见过用ArrayList当只读集合的代码但从接口层面就禁止删除明显是更好的设计。5. 常见问题与排查技巧实录5.1 编译错误泛型数组创建失败现象T[] arr new T[10]编译直接报错。原因Java的泛型通过类型擦除实现运行时并不知道T的具体类型因此无法创建泛型数组。解法可以按下面几种方式来// 方法1创建Object数组后强转教材做法 T[] arr (T[]) new Object[10]; // 方法2使用Array.newInstance反射创建更灵活但更繁琐 T[] arr (T[]) Array.newInstance(clazz, capacity);我建议初学阶段用方法1简洁且够用。要提醒的是强转会有一个unchecked警告这是正常的。但如果你用方法2虽然能拿到精确类型的数组代码复杂度会上升学习时没必要引入。还有一个小技巧如果你在类里声明的是private T[] items在构造函数里可以用items (T[]) new Object[capacity]。这个写法在resize方法里同样适用。5.2 空栈/空队操作NoSuchElementException还是返回null现象在空栈上调用pop()在空队列上调用dequeue()程序崩溃或行为异常。原因实现时没有做空指针检查或者检查了但抛的异常不明确。解法我建议在pop()、peek()、dequeue()的开头都显式检查isEmpty()如果为空则抛出NoSuchElementException。这样做有两个好处一是报错信息明确Stack underflow二是把异常行为统一到标准库接口上——java.util.Stack的pop()在空栈时会抛EmptyStackException而java.util.ArrayDeque会抛NoSuchElementException。如果你在写自己的容器库遵循Java标准库的异常约定是最好的选择。5.3 迭代器中修改容器ConcurrentModificationException还是静默错误现象在遍历一个栈/队列的过程中突然插入或删除了元素程序出现各种诡异行为。原因迭代器已经保存了当前节点的引用但容器结构变了迭代器的状态和容器不一致。解法如果你希望快速失败可以在容器中维护一个modCount计数器每次结构性修改push/pop/enqueue/dequeue都自增。迭代器保存创建时的modCount每次调用next()时检查当前的modCount是否一致不一致就抛ConcurrentModificationException。教材里省略了这个机制但Java标准库ArrayList的做法就是这样。如果你在学习阶段就理解了这个设计以后看JDK源码会轻松很多。5.4 链表 vs 数组的性能选择什么场景选哪个这是我在评论区最常被问的问题。这里给一个比较直接的速查表场景推荐实现理由需要频繁随机访问按下标取元素数组索引访问O(1)频繁在头部插入/删除链表头部操作O(1)数组头部操作O(n)频繁在尾部插入/删除数组均摊O(1)需要频繁扩容且不确定最终大小数组动态扩容均摊O(1)内存敏感且节点数量巨大数组链表每个节点多一个引用字段需要频繁合并两个容器链表只需调整指针有一个经验法则如果你不确定选哪个优先用数组实现。因为数组对CPU缓存友好在现代硬件上通常比链表快一个量级。链表的O(1)插入优势很多时候会被缓存不命中的代价抵消。这一点在后续学习树和图的时候会更明显。5.5 对象游离导致的隐性内存泄漏怎么排查排查内存泄漏最直接的办法就是用内存分析工具比如VisualVM、MAT看堆转储。如果你发现一个数组容器里的对象迟迟不能被回收而代码逻辑上它们已经不再需要那十有八九就是对象游离问题。可以按下面几步快速排查检查所有pop()、dequeue()、remove()方法确认删除元素后是否将数组槽位置为null。检查所有临时引用是否清理干净。比如你保存了Node引用删除后要把node.item置为null。检查容器缩容时扩缩容方法是否完整拷贝有效元素并丢弃旧数组引用。我自己的习惯是写完一个容器之后用-Xmx16m跑一个小堆内存的测试脚本往里压几百万个对象再全弹出来看内存是否回落到初始水平。如果内存不回落说明有游离引用。这个方法简单有效适合你自己写容器的自测。5.6 边写边测的单元测试模板最后分享一个我用来测试这些容器的单元测试模板。别小看测试这些容器虽然代码不长但边界条件非常多。public class StackTest { Test public void testPushPopOrder() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); stack.push(3); assertEquals(3, stack.pop().intValue()); assertEquals(2, stack.pop().intValue()); assertEquals(1, stack.pop().intValue()); assertTrue(stack.isEmpty()); } Test public void testResizingArrayStackManyElements() { ResizingArrayStackInteger stack new ResizingArrayStack(); for (int i 0; i 10000; i) { stack.push(i); } for (int i 9999; i 0; i--) { assertEquals(i, stack.pop().intValue()); } assertTrue(stack.isEmpty()); } Test(expected NoSuchElementException.class) public void testPopEmptyStack() { LinkedStackInteger stack new LinkedStack(); stack.pop(); } Test public void testQueueOrder() { LinkedQueueString queue new LinkedQueue(); queue.enqueue(a); queue.enqueue(b); queue.enqueue(c); assertEquals(a, queue.dequeue()); assertEquals(b, queue.dequeue()); assertEquals(c, queue.dequeue()); assertTrue(queue.isEmpty()); } Test public void testIterator() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); int sum 0; for (int x : stack) { sum x; } assertEquals(3, sum); } }这套模板覆盖了顺序性、扩容场景、空容器操作、迭代器四条基本路径。你可以在这些基础上增加性能测试比如压入100万个元素看耗时来对比链表和数组实现的差距。6. 从这章延伸出去你在为后面的算法铺路讲了这么多具体实现最后我想跳出来谈谈这一章在更大知识图谱中的位置。很多人学《算法第4版》会犯一个错误急着往后翻图算法和字符串算法觉得容器是常识不需要细看。但我可以负责任地说后面所有算法章节都会用到这章的知识而且用的方式往往是组合拳。图算法里深度优先搜索DFS本质上就是用栈或递归递归就是隐式栈实现的广度优先搜索BFS则是用队列实现的。你要是没把栈和队列的实现搞清楚后面理解DFS、BFS会非常吃力。堆排序、优先队列这些本质上是在数组上实现的一棵完全二叉树你在这一章学到的动态数组扩容和对象游离处理全部会复用到优先队列的实现中。符号表那章用链表实现顺序查找其实就是这一章链表实现的直接延伸只是节点里多存了一个键值对。我自己学这章时做过一件小事把这三种容器的链表实现和数组实现各写了一遍然后跑了一组对比测试记录了插入10万、100万、1000万个元素的时间。结果让我印象深刻在1000万规模下数组实现比链表实现快大约一个数量级。这个数据让我以后在选择容器时有了更强的直觉。我建议你也做一次类似的实验这会让你对算法的常数因子有切身体会。这章还有一个价值我很少见人提起但它实际很重要它是对抽象数据类型这个概念最好的入门训练。理解了物理存储结构链表/数组和逻辑访问规则LIFO/FIFO/无序是两回事你就拥有了和数据结构的本质打交道的能力。以后你看任何高级数据结构比如跳表、红黑树、B树本质上都是某种物理结构服务于某种访问规则的产物。有了这个思维模型你会走得更远。