零基础前置：数据、内存、引用与抽象数据类型

第一次学习数据结构时，我一头扎进了数组、链表、树的实现里。背了一堆API和复杂度，砖头去写链表的时候还是栽在了引用断链的bug里。后来我才想明白：所有数据结构都在做同一件事：把现实里的信息放进计算机能存的格式，约定好怎么读、怎么改、怎么找

这篇是整个专题的零基础前置。不讲具体结构，只搭一条最基础的主线。现实信息会被编码成数据，数据存在内存里，程序靠地址和引用找到它，而数据结构，就是负责组织这些数据和操作的规则。

图：先分清值、内存、引用、数据结构和抽象数据类型，后面的数组、链表与树才不会混在一起

从“信息”到“数据”

姓名、价格、图片和好友关系… 这些都是现实世界里的信息，但计算机最终只能保存二进制位（0和1），因此程序需要先规定用什么规则吧现实信息翻译成二进制，又用什么规则吧二进制还原成信息。

• 整数：用固定字节数的二进制编码，比如 Java 里int占 4 字节
• 字符：按 Unicode 编码映射成数字，再存成二进制
• 图片：拆解成像素矩阵，每个像素存颜色值
• 用户对象：拆成姓名、年龄、ID 等一组字段分别存储
• 好友关系：抽象成点和边，用连接关系表示

所谓数据，从来不只是一个值，还包括这个值的类型、含义以及它与其他数据的关系。数据结构我认为其研究的核心，就是这些数据该怎么排列、怎么连接、怎么操作最高效。

内存可以先想成一排带编号的格子

我入门的时候，老师一上来就讲虚拟内存、分页、段氏存储什么的，什么一些玩意儿，越听越懵哈哈哈。后来自己总结了简化模型：把内存当成一排连续的小格子，每个格子有唯一的门牌号（地址）。

这个模型省略了很多底层细节，不够严谨，但足够帮你搞懂所有数据结构最底层的差异：

• 数组：同类型元素紧挨着放，知道起始地址，就能用下标直接算出目标位置
• 链表：节点不用挨在一起，每个节点额外存一份「下一个节点的地址」
• 树、图：本质都是靠引用（地址）来表达父子、邻接这些关系

连续存储： [A][B][C][D]
           0  1  2  3

链式存储： [A | next] → [B | next] → [C | null]

数组用连续空间换取快速定位；链式结构用额外引用换取灵活连接。这就是后面几乎所有数据结构取舍的起点。

值、变量、地址和引用不要混为一谈

很多人学数据结构学到后面混乱，根源是这四个概念没分清。我们用 Java 代码举例：

int age = 42;
User user = new User("小艾");

这里面：

• 42、"小艾"：是值，是真正存储的数据内容
• age、user：是变量名，是程序里给这块数据起的名字
• new User(...)创建出来的对象：真正存在堆内存里的实体
• user变量里存的：是引用（对象的内存地址），靠它能找到堆里的真实对象

学习数据结构不用一开始就啃透 JVM 内存模型，但这五点一定要先建立认知：

1. 变量只是名字，不是数据本身
2. 基础类型的值直接存在栈里，引用类型的值存在堆里
3. 对象不会直接传递，传递的都是它的引用
4. 多个变量可以指向同一个对象
5. 通过一个引用修改对象，所有引用它的地方都会感知到变化

链表断链、树节点丢失、图遍历重复访问……80% 的低级 bug，都来自没理清楚引用关系。

数据结构不只是“装数据的容器”

很多人觉得数据结构就是 “装数据的盒子”，其实一个完整的数据结构，至少包含三层：

举个最典型的例子：栈和队列。 很多人以为它们是两种不同的数据结构，其实不对。栈和队列首先是操作规则—— 栈是后进先出，队列是先进先出。你可以用数组实现栈，也可以用链表实现栈；规则不变，内部实现不同，性能特性就不一样。

所以学结构，不要先记代码，先记它的「规则约束」。

什么是抽象数据类型

抽象数据类型（Abstract Data Type，ADT）说穿了就是：只描述 “能做什么”，不规定 “内部怎么做”。

这其实就是 Java 里接口的思想。比如列表List，它只定义了一组操作契约：

interface SimpleList<E> {
    E get(int index);       // 按位置查
    void add(E value);      // 尾部加
    void add(int index, E value); // 指定位置加
    E remove(int index);    // 按位置删
    int size();             // 查长度
}

ArrayList可以用动态数组实现这个接口，LinkedList可以用双向链表实现这个接口。对外用起来差不多，但底层的内存布局、各种操作的速度天差地别。

以后遇到任何结构，都先分两层理解：

1. 逻辑层：它承诺哪些操作?遵守什么规则？
2. 实现层：它用什么内存布局与算法兑现了这些承诺？

先搞懂逻辑层，再抠实现层，这是最省力的学习顺序。

为什么总要讨论复杂度

如果只有 10 条数据，怎么写都快；但如果有 1000 万条数据，操作次数就成了决定性成本。复杂度描述的就是：当数据规模越来越大时，时间和空间消耗会怎样增长。

这里先纠正一个新手误区：大 O 不是精确的运行时间，是增长趋势。O (1) 不是说一定比 O (n) 快，是说它的耗时不会随着数据量变大而线性增长。数据量很小的时候，O (n) 可能反而更快。

入门阶段先记住三个最直观的直觉：

• O(1)：数据量变大，操作次数基本不变（比如数组按下标查）
• O(log n)：每一步都能排除掉一大半范围（比如二分查找）
• O(n)：通常需要把数据从头到尾扫一遍（比如链表查找）

专题后面会单独拆解复杂度分析，这里先建立概念即可。

学一个结构时，固定问六个问题

这是我刷了几百道题、踩了无数坑之后，总结出来的「万能六问」。不管学数组还是红黑树，按这六个问题走一遍，基本就吃透了，不会越学越乱：

1. 它最初是为了解决什么问题而出现的？
2. 数据在逻辑上是什么关系？
3. 数据在内存里大致是怎么组织的？
4. 查询、插入、删除分别要走多少步骤？
5. 它必须一直维持什么规则 / 不变量？
6. 哪些真实的系统、框架里用到了它？

先能用自己的话回答这六个问题，再去看完整的实现代码。这样不会一上来就掉进旋转、递归、模板代码里，找不到重点。

接下来怎么读

下一篇我们先看数据结构与算法的历史地图，理解这些方法为什么会随着计算设备和数据规模不断演进。之后进入总览，再按数组、链表、栈、队列、哈希表、树、图的顺序逐个深入。

关于阅读节奏，我自己踩过 “一次想全学会” 的坑，给你的建议是分三轮：

• 第一轮：抓核心概念和直觉，跳过复杂证明和完整源码
• 第二轮：补实现细节，动手写代码
• 第三轮：通过练习题和工程场景复盘巩固

逐层深入，看似慢，其实是最快的方式。

自测问题

如果这五个问题你都能顺着自己的话说出来，那基础概念这关就过了，可以放心进入后面的具体结构学习。

有问题标注出来让Jarvis分析

1. 数组和链表在内存组织方式上，最核心的区别是什么？
2. 在 Java 代码 User u = new User() 中，u 和 new User() 分别是什么？
3. 为什么栈和队列都既可以用数组实现，也可以用链表实现？
4. 抽象数据类型（ADT）和具体的数据结构实现是什么关系？结合 Java 的List举例说明。
5. 学习一个新的数据结构时，为什么要先问 “它解决什么问题”？