1. 为什么 Day 3 必须先啃下数组、链表和栈
很多学 Java 的人会有个误区：觉得数据结构是"算法课"的事，先学完语法、能做 CRUD 项目就行。但真正开始搞点有深度的事——比如自己实现一个缓存、理解 ArrayList 和 LinkedList 的差异、排查线上 OOM——马上就会发现自己站在一个很空的地基上。Day 3 所以安排这三样，是因为它们是最底层的"三块砖"：数组和链表是两种物理存储方式，栈是一种基于它们实现的操作受限结构。搞懂这三者的关系，后面的队列、树、哈希表、图全都顺理成章。
我当天的学习顺序是：先看数组为什么"查询快、增删慢"，再看链表为什么"增删快、查询慢"，然后用这两种结构分别手写一个栈。等到代码跑通的那一刻，我脑子里"数据结构就是一堆抽象概念"的印象彻底被粉碎，取而代之的是一个个真实存在的内存模型。
还有一个没法回避的现实：任何一本 Java 面试题集里，栈和链表都是高频考点。但面试题的背后是有真实工作场景的——JVM 的方法调用就用栈，一个 List 的底层不是数组就是链表，你在 Spring 项目里配置的每个 Bean 容器，本质上也是某种数据结构的管理器。Day 3 学的东西不是"为了面试"，而是"为了以后真能看懂代码"。
这一天的内容可以用一张表盘一下：
| 学习对象 | 本质 | 典型 Java 对应 | 为什么先学它 |
|---|---|---|---|
| 数组 | 连续内存、随机访问 | int[]、ArrayList | 最简单的"存取"模型，后面所有容器都基于它 |
| 链表 | 不连续内存、靠引用串起来 | LinkedList | 让你理解"引用"和"地址"的真实含义 |
| 栈 | 后进先出（LIFO） | ArrayDeque、调用栈 | 经典应用多，可基于数组或链表实现，是练习抽象的好素材 |
| 匿名内部类 / 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，引用类型数组默认全是null，boolean 数组默认全是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[]比List<Integer>省下大量自动装箱的消耗
当然这只是"知道有这回事"的程度，真正学会权衡是后面写算法时慢慢练出来的。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 方法时有局部变量、参数，方法结束该清理了，就按后进先出的规则弹出清理。
- 括号匹配：编辑器或编译器的语法检查里，遇到左括号压栈，遇到右括号弹栈并检查是否配对。
- 浏览器的后退/前进：后访问的页面在栈顶，点后退时弹出当前页，露出上一个页面。
- 撤销操作：Ctrll+Z 的本质就是撤销栈，最后做的操作压在栈顶，先被撤销。
看完这些场景再说它是"后进先出"，就很自然了。栈的主力应用场景，基本都要求你能迅速拿到"最后存进去的那个东西"，所以它不适合做随机访问，但非常适合做"过程回溯"。
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 == 0 | top == null |
| 内存局部性 | 好 | 差 |
| 实现复杂度 | 低 | 中（需要自己管理节点） |
4.4 一个遗留问题：为什么 Java 官方推荐用 ArrayDeque 而不是 Stack
学到后面，我看源码时发现 Java 里有个现成的Stack类，但它继承自Vector，而这个继承带来两个问题：一是Vector内部是带synchronized同步锁的，单线程用它会有点性能开销；二是它额外暴露了一批不是栈该有的方法（比如get(int index)、insertElementAt），打破了"栈只能在栈顶操作"的抽象纪律。
所以现代 Java 代码里，官方推荐的栈实现是ArrayDeque：
ArrayDeque<Integer> 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 Comparator<Student>() { @Override public int compare(Student s1, Student s2) { return Integer.compare(s1.age, s2.age); } });这段代码里没有出现任何类的名字，但确实创建了一个继承Comparator<Student>的匿名类的实例。为什么语法长得怪？因为new Comparator<Student>() { ... }后面的花括号不是在实例化接口（接口不能被实例化），而是在定义一个没有名字的类并立即创建它的对象。匿名内部类的核心逻辑就是这个。
5.2 简化一段：Lambda 到底是怎么省下来的
匿名内部类虽然省掉了"单独写一个类"的麻烦，但代码还是有点啰嗦——new Comparator<T>()、泛型、四句方法体全写在里。Java 8 之后 Lambda 能把这段压缩成一行：
Arrays.sort(students, (s1, s2) -> Integer.compare(s1.age, s2.age));Lambda 的本质，是对"只有一个抽象方法的接口（函数式接口）"的一种简化写法。编译器看到Comparator<Integer>只有一个需要实现的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 指向……这些备注后来成了复习时最有价值的部分。学数据结构不追求一次全部理解，而追求亲手写过、踩过坑、知道哪里容易错，这样后面再遇到类似逻辑，你看到代码的第一眼就能知道问题可能藏在哪儿。这个东西没法靠别人灌给你，只有自己一遍遍跑代码才能沉淀下来。
