1. 为什么 Day 3 必须先啃下数组、链表和栈很多学 Java 的人会有个误区觉得数据结构是算法课的事先学完语法、能做 CRUD 项目就行。但真正开始搞点有深度的事——比如自己实现一个缓存、理解 ArrayList 和 LinkedList 的差异、排查线上 OOM——马上就会发现自己站在一个很空的地基上。Day 3 所以安排这三样是因为它们是最底层的三块砖数组和链表是两种物理存储方式栈是一种基于它们实现的操作受限结构。搞懂这三者的关系后面的队列、树、哈希表、图全都顺理成章。我当天的学习顺序是先看数组为什么查询快、增删慢再看链表为什么增删快、查询慢然后用这两种结构分别手写一个栈。等到代码跑通的那一刻我脑子里数据结构就是一堆抽象概念的印象彻底被粉碎取而代之的是一个个真实存在的内存模型。还有一个没法回避的现实任何一本 Java 面试题集里栈和链表都是高频考点。但面试题的背后是有真实工作场景的——JVM 的方法调用就用栈一个 List 的底层不是数组就是链表你在 Spring 项目里配置的每个 Bean 容器本质上也是某种数据结构的管理器。Day 3 学的东西不是为了面试而是为了以后真能看懂代码。这一天的内容可以用一张表盘一下学习对象本质典型 Java 对应为什么先学它数组连续内存、随机访问int[]、ArrayList最简单的存取模型后面所有容器都基于它链表不连续内存、靠引用串起来LinkedList让你理解引用和地址的真实含义栈后进先出LIFOArrayDeque、调用栈经典应用多可基于数组或链表实现是练习抽象的好素材匿名内部类 / Lambda简化代码的语法机制Comparator、函数式接口数据结构实战中写排序、回调时必然碰到下面我按当天实际推进的顺序展开讲完整过程而不是把教科书目录抄一遍。你会发现每一段都对应一段可以跑的代码以及我踩过之后才理解的细节。2. 数组最容易写对也最容易写出隐患的结构2.1 数组在内存里到底长什么样数组是同一类型数据在内存里连续排列的结构。Java 里写int[] arr new int[5]虚拟机会在堆上找一整块连续的区域每个元素占固定字节数比如 int 占 4 字节。因为连续所以你要取第 3 个元素只需要做一次加法运算首地址 3 * 4字节时间和数组大小无关。这就是所谓O(1) 随机访问——不管数组里有 10 个还是 1 万个元素取任何一个下标都是同样的速度。可以类比电影院的连排座位你知道第一排是从几号开始的要找第 15 号座位按座位编号直接走过去就行。这就是连续 固定宽度带来的优势。但硬币的另一面也是连续造成的如果要在中间插入一个元素后面的所有元素都得整体后移一位删除同理前面说得直白点——数组的增删操作是搬家操作搬家的规模取决于数组长度。这是理解后续所有容器ArrayList 为什么扩容要复制、LinkedList 为什么增删相对快的基础。2.2 Java 数组里最容易踩的三个坑坑一下标越界。Java 的数组下标从 0 开始合法范围是0 到 length-1。初学者最容易犯两类错误一是循环时用了i arr.length二是从 1 开始循环读取。两种情况最终都会抛ArrayIndexOutOfBoundsException。我当天就在写栈代码时踩了一次——top指针当前指向的位置到底代表有元素的最后一个下标还是下一个空位没理清楚多循环了一次直接越界。这类错误最磨人因为报错信息明确但解决它必须靠你想明白索引语义。坑二默认值。声明int[] arr new int[5]后数组元素不是空的int 数组默认全是 0引用类型数组默认全是nullboolean 数组默认全是false。这个特性平时用不上但你要是写栈、写链表时依赖数组被初始化后的默认值就很容易出 bug——比如判断某个下标是否被占过你得显式声明一个标志位。坑三固定长度与扩容。数组一旦创建长度不可变。所以 Java 里ArrayList的底层是数组它为什么能无限 add因为它会在容量不足的时候创建一个更大的新数组把旧数据全部复制过去。Day 3 我特意手写了一遍这个扩容过程代码只有几行但对ArrayList 为什么有时性能糟糕会有非常直观的理解int[] oldArr {1, 2, 3}; int[] newArr Arrays.copyOf(oldArr, oldArr.length * 2); // 扩容一倍Arrays.copyOf底层做的就是这个新开数组 复制的动作。ArrayList 的时序性性能问题本质就是它扩容时把整个数组搬了一次家。2.3 什么时候该直接用数组而不是 ArrayList这个话题我在 Day 3 之前从来没有想过。实际工程里大概有一半的场景用的是List但有些场景真的应该直接用数组长度确定且不需要动态变化的场景比如存储一年 12 个月的每月统计值对性能敏感、循环遍历频繁且一次写入不再修改的场景需要泛型数组之外的基础类型数组时int[]比ListInteger省下大量自动装箱的消耗当然这只是知道有这回事的程度真正学会权衡是后面写算法时慢慢练出来的。Day 3 我的目标很简单用数组这种原生结构手动实现一个栈把数组本身的各种脾性摸一遍。3. 链表引用就是指针画图才能写对3.1 Node 节点链表的最小单元链表和数组最大的区别在于它的内存是不连续的。每个元素是一个节点Node节点里存两部分内容数据本身以及指向下一个节点的引用。public class Node { int data; // 数据域 Node next; // 引用域存下一个节点的地址 }在 Java 里没有指针这个说法指 C 的概念但Node next这个引用本质上就是指针——它保存了下一个节点在堆内存中的位置。所以初学者可以把 Java 的引用直接理解为安全的指针。链表的样子可以想象成一条铁链每一环扣住下一环各个环之间在内存里可能隔得很远但通过引用一个个串起来。学链表最核心的一点是动手画图。我在纸上画了不下二十遍插入节点和删除节点的过程。画多之后你不光是会写代码还能形成一种肌肉记忆——每次写链表操作前先在脑子里过一遍每个引用应该指向谁。3.2 头插法与尾插法写链表的第一道门槛往链表头部插入一个节点是最基础的两种操作之一。代码就两句但顺序绝对不能反// head 是当前头节点newNode 是要插入的新节点 newNode.next head; // 先让新节点指向原来的头 head newNode; // 再把头更新为新节点这句先接旧、再换头的顺序很多初学者第一次会写反。如果先把head newNode那原来的链表就丢了——因为再没有任何变量指向它栈上只有newNode一个引用。在 Java 里这个旧链表会被垃圾回收相当于数据全部丢失。我在本地试过一次日志上打印出来只有一个孤零零的节点瞬间就懂了什么叫先建立连接再移动指针。尾插法就多一个遍历到最后一个节点的过程Node currentNode head; // 找到最后一个节点它的 next 是 null while (currentNode.next ! null) { currentNode currentNode.next; } currentNode.next newNode;这里有个很容易踩的坑如果你维护了一个tail尾节点指针那么插入之后要记得更新否则tail指向的不再是真正的尾节点。我 Day 3 用链表实现栈的时候就因为初始写代码时没更新tail后面打印链表时发现少了一个节点排查了半天。这类问题的共性是你对引用指向谁缺乏实时追踪所以建议每次操作完都自问一遍现在哪个变量还引用着这些节点哪个引用的语义已经变了3.3 链表删除操作里那个最容易被忽略的前驱节点从单链表删除一个节点不能只靠待删节点本身。你必须把它的前一个节点的next指向它的后一个节点。所以在写删除逻辑的时候通常需要保存prev前驱指针。循环遍历的时间复杂度是 O(n)但定位到之后修改引用只需要 O(1)。这个删一个节点需要知道它的前驱的特性是链表的经典考点也是我 Day 3 遇到的第一个卡壳的地方。当时我天真地以为拿到待删节点就能删结果发现它根本没有往回看的能力——因为单链表只有一个方向的引用。如果真的要不知道前驱就删有两个替代方案一是改造成双向链表每个节点多存一个prev二是用值覆盖的技巧把下一个节点的值拷贝到当前节点再把下一个节点跳过去。后一种方法在面试题里偶尔出现但日常工程中还是老老实实维护前驱更清晰。3.4 数组和链表怎么选用一张表说透学完数组和链表的基本操作后我发现很值得把它们放一起系统对比对比维度数组链表内存布局连续内存申请时一次性分配非连续节点动态创建随机访问下标O(1)直接算地址O(n)必须逐个遍历头部插入/删除O(n)需要搬移所有元素O(1)只改引用尾部插入/删除已知尾节点O(1)不需要搬移O(1)但如果单链表需要遍历到最后话说回来如果维护了 tail 也可以 O(1)内存额外开销少只有元素本身每个节点多一个引用以及可能的对齐填充遍历缓存友好性高连续内存更利于缓存预取低节点分布零散这个表格仅供参考因为实际的尾部插入在数组和链表里都要看具体实现。更重要的结论是没有绝对的好结构只有合适不合适。频繁按索引取数据、遍历为主就用数组频繁在头部插入、删除链表优势明显。实际开发中ArrayList 和 LinkedList 的选择也是这个权衡逻辑如果你未来做的是读多写少的场景ArrayList 基本总赢。4. 栈动手实现一次胜过背十遍定义4.1 栈的典型应用场景从编辑器到 JVM栈的定义可以说得非常简单只能在一端进行插入和删除的线性表后进先出LIFO。但真要理解它为什么重要得看应用场景函数调用栈每次方法调用就压入一个栈帧方法返回就弹出。你写 Java 方法时有局部变量、参数方法结束该清理了就按后进先出的规则弹出清理。括号匹配编辑器或编译器的语法检查里遇到左括号压栈遇到右括号弹栈并检查是否配对。浏览器的后退/前进后访问的页面在栈顶点后退时弹出当前页露出上一个页面。撤销操作CtrllZ 的本质就是撤销栈最后做的操作压在栈顶先被撤销。看完这些场景再说它是后进先出就很自然了。栈的主力应用场景基本都要求你能迅速拿到最后存进去的那个东西所以它不适合做随机访问但非常适合做过程回溯。4.2 用数组实现一个栈核心代码与边界处理我用数组手写了一个ArrayStack支持push、pop、peek、isEmpty。public class ArrayStack { private int[] data; private int top; // top 表示栈中元素个数也是下一个元素要放的位置 private int capacity; public ArrayStack(int capacity) { this.capacity capacity; this.data new int[capacity]; this.top 0; // 初始没有元素 } public void push(int value) { if (top capacity) { // 达到容量上限可以选择扩容或抛异常 throw new IllegalStateException(栈已满); } data[top] value; top; } public int pop() { if (isEmpty()) { throw new IllegalStateException(栈已空); } top--; return data[top]; } public int peek() { if (isEmpty()) { throw new IllegalStateException(栈已空); } return data[top - 1]; } public boolean isEmpty() { return top 0; } }这段代码里最有意思的是top的语义。我反复纠结它到底应该是下一个空位下标还是当前元素下标。最终选的是top表示栈中元素个数也代表下一个元素的插入位置。这样初始化时top 0完美表示空栈push先赋值再后移pop先top--再取元素。自己的代码到底哪个语义对没有标准答案但必须前后一致否则必然越界或漏数据。再聊聊pop里的一个细节数组是物理上还存在的你pop之后只是让top缩小了原来那个位置的旧值还在内存里。对基本类型来说无所谓但如果数组存的是对象更好的做法是把对应的数组元素置为null避免内存泄漏隐患——如果你不置空一个已经永不访问的对象还被数组引用垃圾回收器会认为它存活导致内存一直占用。这个点也是面试里偶尔问到的细节Day 3 我在做练习题时顺手把这个范式记住了。4.3 用链表实现一个栈为什么头插法在这里是天然盟友链表实现栈可以有多种做法我选的是单链表头插法。因为栈只在一端操作而链表的头部插入/删除恰好在 O(1) 完成这和数组栈的逻辑完全对应。public class LinkedStack { private Node top; // 栈顶节点 private static class Node { int data; Node next; Node(int data) { this.data data; } } public void push(int value) { Node newNode new Node(value); newNode.next top; top newNode; } public int pop() { if (top null) { throw new IllegalStateException(栈为空); } int value top.data; top top.next; return value; } public int peek() { if (top null) { throw new IllegalStateException(栈为空); } return top.data; } public boolean isEmpty() { return top null; } }这个实现里弹栈操作top top.next非常直观原来的头节点被丢弃下一个节点变成新栈顶。如果非要较真你会注意到我pop时没有显式把旧节点的next置空这是个实际存在但不太要紧的细节——局部变量top更新后旧头节点已经没有任何引用指向它了JVM 的垃圾回收会把它和它曾经引用的整条链都收走。两种实现的对比也很值得写一写对比点数组栈链表栈容量固定除非扩容理论上无上限只受内存限制空栈判断top 0top null内存局部性好差实现复杂度低中需要自己管理节点4.4 一个遗留问题为什么 Java 官方推荐用 ArrayDeque 而不是 Stack学到后面我看源码时发现 Java 里有个现成的Stack类但它继承自Vector而这个继承带来两个问题一是Vector内部是带synchronized同步锁的单线程用它会有点性能开销二是它额外暴露了一批不是栈该有的方法比如get(int index)、insertElementAt打破了栈只能在栈顶操作的抽象纪律。所以现代 Java 代码里官方推荐的栈实现是ArrayDequeArrayDequeInteger stack new ArrayDeque(); stack.push(100); int topValue stack.pop();ArrayDeque的push/pop方法就是栈语义。Day 3 我并没有在项目里立刻用它只是搞清楚了原来官方都不推荐Stack类这个事实这让我对数据结构会决定 API 设计有了具体感受。5. 匿名内部类和 Lambda数据结构旁边最实用的一对语法糖5.1 一个真实需求让自定义对象能排序学完前面三样基础结构后我做了个小练习——用数组存了几个学生对象然后想按年龄排序。Java 里给数组排序的方法是Arrays.sort但排序规则得自己定义。这时候就撞上了标题里说的匿名内部类和 Lambda 表达式。如果用传统写法我得先定义一个有名字的类去实现Comparator接口很麻烦但如果用匿名内部类就能就地概念化这个排序逻辑Arrays.sort(students, new ComparatorStudent() { Override public int compare(Student s1, Student s2) { return Integer.compare(s1.age, s2.age); } });这段代码里没有出现任何类的名字但确实创建了一个继承ComparatorStudent的匿名类的实例。为什么语法长得怪因为new ComparatorStudent() { ... }后面的花括号不是在实例化接口接口不能被实例化而是在定义一个没有名字的类并立即创建它的对象。匿名内部类的核心逻辑就是这个。5.2 简化一段Lambda 到底是怎么省下来的匿名内部类虽然省掉了单独写一个类的麻烦但代码还是有点啰嗦——new ComparatorT()、泛型、四句方法体全写在里。Java 8 之后 Lambda 能把这段压缩成一行Arrays.sort(students, (s1, s2) - Integer.compare(s1.age, s2.age));Lambda 的本质是对只有一个抽象方法的接口函数式接口的一种简化写法。编译器看到ComparatorInteger只有一个需要实现的compare方法就知道(s1, s2) - ...这个表达式是在实现哪个方法。所以补偿原则不是所有匿名内部类都能改成 Lambda只有目标类型是函数式接口只有一个抽象方法时才行Lambda 不能改签名、不能使用默认方法它只负责接口里那个唯一的抽象方法语法结构参数列表在左方法体在右中间用-分隔为了真正搞懂它我把排序代码写了三个版本 第一版完整地定义一个有名字的外部类StudentAgeComparator单独一个文件 第二版匿名内部类就地实现 第三版Lambda三个版本跑出来的结果完全一样但代码从十几行缩减到三行多一点。这个过程对理解匿名内部类和 Lambda 是同一件事的两种写法特别有帮助。5.3 Lambda 的两个限制理解之后再也不用靠死记限制一局部变量必须是 effectively final。Lambda 内部如果引用了方法的局部变量这个变量不能再被修改。原因是 Lambda 引用局部变量时变量其实被复制了一份到 Lambda 内部为了保证复制值和使用值一致只能禁止原始变量在后续代码里发生变化。这和我理解 C 的函数指针时的概念不太一样但配合 Java 的值捕获语义就合理多了。如果确实需要修改可以声明一个单元素数组或者用一个自定义计数器对象来处理但这属于变通策略日常开发尽量避免。限制二Lambda 里的this指向的是外部类对象不指向 Lambda 本身。匿名内部类里this指向自己这个匿名类对象Lambda 里this指向外围类的对象。这个差异在某些回调场景比如在Runnable里访问外部类的字段会体现出来。知道了这一条以后看到Lambda 里能不能用 this之类的讨论心里就有底了。5.4 匿名内部类在数据结构里还有哪些用武之地排序只是其中一个入口匿名内部类在数据结构代码里出现频率最高的地方还包括Iterator迭代器的匿名实现Runnable/Callable作为任务参数各种监听器回调比如按钮点击事件自定义类的比较器用于TreeSet、PriorityQueue排序我学到这里最大的体会是数据结构和 Lambda 其实是一对很好的组合。假定你要用一个PriorityQueue实现一个小顶堆堆的排序规则完全可以通过 Lambda 写在构造参数里不用单独定义类。这样数据结构本身的抽象和 Lambda 的简洁互为补充代码可读性会好很多。可惜 Day 3 当天我还只是在了解阶段没有马上用 Lambda 去重写栈和链表但我已经可以预感到后面学到集合框架时这套匿名内部类 → Lambda的简化会反复出现。所以建议正在学这块的朋友先动手跑一遍 Comparator 排序、匿名内部类版本把自己写熟了再去记 Lambda 语法。6. 学习过程中最值得写进收藏夹的避坑清单和节奏建议6.1 空指针和引用丢失链表新手的第一定律链表代码里最经典的错误就是空指针异常NullPointerException但它其实非常容易预防在while里遍历之前先确认入口不是null删除节点之后旧节点引用你如果不再用就让它自然不可达在push的时候一定记得先解决新节点的next指向谁否则会丢链还有个更隐蔽的引用丢失问题我 Day 3 遇到了用链表栈时我写的是top top.next但在打印栈的所有元素时如果我直接用了top变量去遍历而不是另存一个临时变量等我遍历完栈顶已经被移动了整个栈就空了。所以遍历链表的循环必须用一个临时引用current不能动原来的top引用。这个教训我在当天代码上标注成了醒目的注释遍历用临时变量别用结构本身的入口引用。6.2 边界条件清单每次写完代码都先靠它自查我 Day 3 最骄傲的习惯是写完新结构后立刻跑一遍边界条件测试也就是空结构上执行pop/peek是否抛异常或返回安全默认值只有一个元素时执行pop结构是否能正确变空在数组只剩一个空位时执行push是否触发扩容或异常在栈达到容量上限时继续push是否有明确的错误反馈链表里删除头节点和删除中间节点行为是否一致这些边界条件不一定在正常功能路径里触发但恰恰是它们把看起来能跑的代码变成真正可靠的代码。我 Day 3 手写数组栈时就漏掉了栈满的场景导致最后数据越界写坏了下标附近的其他数据——虽然基本类型数组没有越界检查那么严格但这个问题在真实项目里就是线上故障的种子。6.3 Day 3 的学习节奏给后来者的一份参考我当天的安排大概是这样的供参考但不建议照抄每个人的基础不一样上午花半小时理解数组和链表的为什么用白纸画插入/删除的引用变化过程上午到中午分别手写数组栈和链表栈反复调试边界条件约 2 小时下午用这两个栈解决两道简单题比如括号匹配、逆序输出让结构活起来下午后半段接触Comparator排序场景理解匿名内部类再改写为 Lambda 版本晚上整理笔记把为什么这么写的问题和答案集中记下来一个很有用的感觉是数据结构不要只看不写。哪怕你觉得自己理解了 90%只要一动手那失去的 10% 必然会冒出来。写一次链表你对引用这个概念的理解能顶上读三篇文章。6.4 一个小技巧用 jshell 快速验证数据结构的行为Java 9 之后的 JDK 自带一个jshell交互式命令行工具。我 Day 3 后半段的很多小验证都是在 jshell 里完成的比如jshell然后在提示符下直接敲int[] arr new int[5]; System.out.println(arr[0]); // 0验证默认值甚至可以直接定义一个简易的链表节点类当场测试几个操作。这比反复写public class Main再编译运行快得多尤其适合验证那些不知道结果对不对的小片段。一个建议是把半天学习里的小疑问都放进 jshell 里去试大概试十个你就能明显感觉到自己是对数组、链表、栈的模型理解更深了。Day 3 结束的时候我把当天代码里踩到的每个坑都单独列了出来包括top 的语义定义、链表删除前的 prev 指针、Lambda 外的 this 指向……这些备注后来成了复习时最有价值的部分。学数据结构不追求一次全部理解而追求亲手写过、踩过坑、知道哪里容易错这样后面再遇到类似逻辑你看到代码的第一眼就能知道问题可能藏在哪儿。这个东西没法靠别人灌给你只有自己一遍遍跑代码才能沉淀下来。
