算法抽象化：从数组、链表到遍历思想
今天学到的内容，可以先压缩成一句话：
很多算法问题，本质上都可以拆成两件事：数据如何存，以及数据如何被访问。
如果继续抽象，数据的存储结构可以先从两个底层模型理解：数组和链表。而数据结构上的操作，也可以先从两个核心动作理解：访问和遍历。再进一步，很多算法技巧，比如双指针、滑动窗口、回溯、动态规划，其实都是在回答一个问题：如何更有效地访问、遍历、穷举和选择。
这篇文章是今天学习后的阶段性整理，部分观点后面还需要继续补全和修正。
一、算法的存储抽象：数组和链表
我今天先形成了一个比较粗的判断：很多数据结构都可以从数组和链表这两个底层结构出发理解。
这句话不是说世界上所有结构在工程实现里都只能用数组和链表，而是说：当我们学习算法时，数组和链表是两个最基础的存储模型。
- 数组强调连续空间、下标访问、位置关系。
- 链表强调节点连接、指针指向、动态增删。
很多更复杂的数据结构，都可以看成是在这两种模型上叠加规则。
二、用数组和链表佐证这个观点
1. 栈可以用数组模拟
栈的规则是：后进先出，也就是最后放进去的元素最先出来。
用数组模拟栈时，核心不是数组本身，而是维护一个指针 top。这个指针表示当前栈顶位置。
当 top = -1 时，说明栈为空。当压入一个元素时，top 向后移动一格；当弹出一个元素时，top 向前移动一格。
class ArrayStack {
private int[] data = new int[100];
private int top = -1;
public void push(int value) {
data[++top] = value;
}
public int pop() {
return data[top--];
}
public boolean isEmpty() {
return top == -1;
}
}这里有一个很重要的理解：数组里的元素可能还在原来的位置上，但只要 top 移动了，算法就认为它已经不属于当前栈了。
所以，栈的关键不是“物理删除”，而是通过指针控制可访问范围。
2. 队列可以用链表模拟
队列的规则是：先进先出，也就是先进入队列的元素先出来。
用链表模拟队列时，可以维护两个指针：
head指向队头，用来出队。tail指向队尾，用来入队。
每次插入新节点时，把原来的尾节点指向新节点，再把 tail 移动到新节点上。
class LinkedQueue {
static class Node {
int value;
Node next;
Node(int value) {
this.value = value;
}
}
private Node head;
private Node tail;
public void offer(int value) {
Node node = new Node(value);
if (tail == null) {
head = node;
tail = node;
return;
}
tail.next = node;
tail = node;
}
public int poll() {
int value = head.value;
head = head.next;
if (head == null) {
tail = null;
}
return value;
}
}链表的重点是“指向关系”。插入和删除很多时候不是搬动所有元素，而是改变节点之间的连接。
3. 二叉树可以用数组表示
完全二叉树也可以用数组表示。
假设数组下标从 0 开始：
- 当前节点下标是
i。 - 左孩子下标是
2 * i + 1。 - 右孩子下标是
2 * i + 2。 - 父节点下标是
(i - 1) / 2。
int[] tree = {1, 2, 3, 4, 5, 6, 7};
int i = 0;
int left = 2 * i + 1;
int right = 2 * i + 2;
System.out.println(tree[left]); // 2
System.out.println(tree[right]); // 3这说明，树虽然看起来是分叉结构，但在某些规则清晰的情况下，也可以用数组存储。
4. 图可以用矩阵或链表表示
图也能继续佐证这个观点。
如果图比较稠密，可以用邻接矩阵表示，本质上是一个二维数组。
int[][] graph = {
{0, 1, 1},
{1, 0, 0},
{1, 0, 0}
};如果图比较稀疏，可以用邻接表表示，本质上是数组加链表，或者数组加列表。
List<Integer>[] graph = new ArrayList[3];
for (int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>();
}
graph[0].add(1);
graph[0].add(2);所以，栈、队列、树、图这些结构，虽然表面形态不同，但底层都能找到数组或链表的影子。
TODO：后续可以继续补全哈希表、堆、并查集、跳表等结构与数组/链表之间的关系。
三、算法的操作抽象：访问、遍历和穷举
理解完存储之后，第二个关键问题是：数据存好了，接下来怎么操作？
我今天的理解是，很多算法操作都可以先抽象成：
- 访问：拿到某一个元素。
- 遍历：按某种顺序访问一批元素。
- 穷举：把可能情况尽量列出来，再筛选答案。
其中，遍历又可以拆成几种常见形式：顺序遍历、递归、迭代。
四、三种基础遍历方式
1. 顺序遍历
顺序遍历最典型的场景是数组。
它的特点是：通过下标从前往后访问元素。
int[] nums = {1, 2, 3, 4};
int i = 0;
while (i < nums.length) {
System.out.println(nums[i]);
i++;
}这种方式很直接：下标每次加一，访问下一个位置。
2. 递归
递归的核心是：函数调用自己。
递归不是简单的循环，它背后依赖函数调用栈。每一次调用都会产生一个新的函数执行现场；当递归到终止条件后，再一层一层返回。
public void print(int n) {
if (n == 0) {
return;
}
System.out.println(n);
print(n - 1);
}可以把递归理解成：当前问题把一个更小的同类问题交给下一层函数处理。下一层处理完之后，再回到当前这一层。
递归经常用在树、回溯、分治等问题里。
3. 迭代
迭代和顺序遍历有点像，但它不一定依赖数组下标。链表里最典型的迭代方式，就是维护一个当前节点 current，每次访问当前节点，然后移动到下一个节点。
class Node {
int value;
Node next;
}
Node current = head;
while (current != null) {
System.out.println(current.value);
current = current.next;
}数组靠下标移动，链表靠指针移动。它们都是“访问当前元素，然后走到下一个元素”。
五、从基础操作升级到算法思想
如果说访问和遍历是最基础的操作，那么很多算法技巧就是在这个基础上继续升级。
1. 双指针
双指针可以理解为：同时维护两个访问位置。
比如一个指针从左边走，一个指针从右边走；或者一个快指针、一个慢指针。它的本质仍然是访问，只是访问位置从一个变成了两个。
2. 滑动窗口
滑动窗口可以理解为：维护一段连续范围。
它一般用于数组、字符串等连续结构。窗口左边界和右边界不断移动，本质上是在控制“当前要访问和统计的范围”。
3. 回溯
回溯的目标更接近“全部访问”。
它会尝试所有可能路径，走不通就退回来，再换另一条路径。回溯很像一种带撤销动作的穷举。
void backtrack(List<Integer> path, int[] nums, boolean[] used) {
if (path.size() == nums.length) {
System.out.println(path);
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtrack(path, nums, used);
path.remove(path.size() - 1);
used[i] = false;
}
}回溯的关键是：先选择，再递归，再撤销选择。
4. 动态规划
动态规划和回溯都可能涉及“很多可能性”，但它们的思路不同。
回溯更像是把所有路径试一遍，然后筛选答案。动态规划更像是先定义状态，再利用已经计算过的结果，逐步推出更大的结果。
比如斐波那契数列：
public int fib(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}动态规划的核心不是“全部试一遍”，而是把问题拆成状态，并保存中间结果，避免重复计算。
六、今天形成的两个主线
今天的内容可以收束成两个主线。
第一条主线是存储结构：
很多数据结构都可以从数组和链表这两个底层模型出发理解。
栈、队列、二叉树、图，都可以用数组或链表的方式进行模拟或表示。这说明学习数据结构时，不能只记表面规则，还要往下追问：它到底是怎么存的？
第二条主线是操作方式：
很多算法都可以从访问、遍历和穷举这些基础动作出发理解。
顺序遍历、递归、迭代，是最基础的访问方式。双指针、滑动窗口、回溯、动态规划，则是在这些基础动作之上的效率优化和思想升级。
七、待补全
这篇笔记还只是一个初版，后面可以继续补全：
- 哈希表如何从数组和链表发展出来。
- 堆为什么通常用数组表示。
- 树的递归遍历和迭代遍历有什么区别。
- 图的 DFS、BFS 如何对应递归、栈和队列。
- 回溯和动态规划的边界如何区分。
- 双指针、滑动窗口分别适合解决什么类型的问题。
今天先把这个框架搭起来。后面再学新的算法题时，就可以不断往这个框架里放例子：先看它怎么存，再看它怎么访问，最后看它怎么优化。