数据结构
数据结构研究"数据如何组织"，组织方式直接决定增删改查的效率。举一个具体例子：在一百万个无序数字里查找一个目标值，数组顺序查找平均要比较 50 万次（O(n)）；如果预先建了哈希表，平均一次计算就能定位（O(1)）。同一份数据，不同的组织方式，性能差距可以达到十万倍——这就是数据结构值得单独学习的理由。
提示
选择数据结构的核心思路是"先看操作再看结构"：按位置访问还是按值查找？频繁插入删除还是只读？要保证有序还是只要快？操作模式决定结构选型，而不是先选结构再凑操作。
核心分类
数据结构按逻辑关系分为四类，每一类解决一类特定的组织问题：
| 类别 | 代表结构 | 解决的问题 | 典型场景 |
|---|---|---|---|
| 线性结构 | 数组、链表、栈、队列 | 数据排成一条线，按先后顺序访问 | 列表展示、撤销栈、任务队列 |
| 树形结构 | 二叉树、堆、B+ 树 | 数据有层级关系，按层级组织与查找 | 文件目录、索引、优先队列 |
| 散列结构 | 哈希表 | 用键直接定位值，追求 O(1) 查找 | 缓存、去重、计数器 |
| 图结构 | 有向图、无向图 | 数据之间存在多对多关系 | 社交网络、路由、依赖分析 |
线性结构
线性结构的共同点是"一条线"：每个元素最多有一个前驱和一个后继。四条主流线性结构各回答一个不同的问题：
| 结构 | 访问规则 | 典型用途 |
|---|---|---|
| 数组 | 按下标任意访问 | 需要随机访问的场景，如排序、二分查找的载体 |
| 链表 | 只能从头逐个遍历 | 频繁在中间插入删除、长度不确定的场景 |
| 栈 | 只从一端进出（后进先出） | 函数调用、括号匹配、浏览器后退 |
| 队列 | 一端进一端出（先进先出） | 任务排队、BFS 层级遍历、消息缓冲 |
数组与链表的取舍是理解线性结构的关键。数组分配一块连续内存，按下标访问一次算出地址，是 O(1)；但插入删除需要把后续元素整体搬移，是 O(n)。链表每个节点散落存放、用指针串联，插入删除只改两个指针，是 O(1)；但访问第 k 个元素必须从头走 k 步，是 O(n)。
为什么栈和队列要"限制"操作
栈和队列都是"限制版"的数组/链表——只开放固定位置的读写。限制看似退化，实则带来两个好处：操作模式确定后不可能误用（比如队列不会出现"跳过队首插队"）；同时它们的操作全部是 O(1)，没有中间位置的复杂情况。
树形结构
树解决"层级关系"问题：文件系统、公司组织架构、HTML 的 DOM，本质都是树。树的核心价值是把"比较"变成"二分"：二叉树 把查找变成折半比较，每走一步排除一半可能，查找代价从 O(n) 降到 O(log n)；堆用树形结构保证"根永远是最值"，O(log n) 取最值；B+ 树把树压扁成多叉，让千万级数据的索引树只有 3-4 层高——二叉搜索树、平衡树、堆都是二叉树的变体，数据库索引用的 B+ 树也不例外，详见 索引。
散列结构
哈希表 解决"按键快速找值"：数组按下标访问是 O(1)，但业务里要按"用户名""订单号"这种键找值。哈希表在数组之上套一层哈希函数，把任意键换算成下标，让数组的随机访问能力复用给任意键。代价是不维护顺序，且性能依赖哈希函数质量——冲突怎么解决（链地址法、开放定址法）、满了怎么扩容，是理解它的核心机制。
图结构
图解决"多对多关系"：社交网络的好友关系、地图的道路网络、微服务的调用依赖，都是图。图的核心操作是遍历（DFS/BFS）和路径计算（最短路径），图的存储有邻接矩阵和邻接表两种方式，前者适合稠密图、后者适合稀疏图。
复杂度视角
衡量数据结构的统一标尺是各操作的时间复杂度，选型本质上是在做复杂度权衡：
| 结构 | 查找 | 插入 | 删除 | 额外特性 |
|---|---|---|---|---|
| 数组 | O(1) 按下标 | O(n) | O(n) | 缓存友好、内存连续 |
| 链表 | O(n) | O(1) 已知位置 | O(1) 已知位置 | 无扩容问题、内存分散 |
| 哈希表 | O(1) 平均 | O(1) 平均 | O(1) 平均 | 无序、最坏 O(n) |
| 二叉搜索树 | O(log n) 平衡时 | O(log n) | O(log n) | 有序遍历、范围查询 |
| 堆 | O(1) 看最值 | O(log n) | O(log n) | 只保证最值在根 |
复杂度表中的 O(1) 往往带"平均"二字，这是哈希表和树的本质区别：哈希表的 O(1) 依赖哈希函数均匀分布，最坏退化到 O(n)；平衡树的 O(log n) 是结构保证的，没有退化风险，代价是常数因子更大。
选型决策
面对具体需求，可以按下面的决策流程快速锁定结构（复杂度相近时优先选实现简单的）：
实际工程中很少单用某一种结构：HashMap 解决"快速定位"，值里再挂一个链表解决"有序输出"，就是 Redis 有序集合的思路——组合使用比挑选单一结构更常见。
数据结构按"线性 → 散列 → 树 → 图"组织：线性结构建立"组织方式决定操作成本"的直觉，散列结构核心在冲突解决与扩容，树形结构回答"为什么树要平衡"，图结构解决遍历（DFS/BFS）与最短路径。理解每种结构抓住三个问题——逻辑上怎么组织、物理上怎么存（数组还是指针）、各操作复杂度多少。
与算法配合
数据结构与 算法 是同一枚硬币的两面：算法描述"怎么做"，数据结构决定"用什么装"。滑动窗口维护窗口内元素计数时用哈希表，BFS 的层级遍历用队列，求最值维护动态集合用堆——算法笔记中提到的每种范式，都隐含了对数据结构的选择。算法 中的复杂度分析方法同样适用于数据结构选型。
数据结构的应用远超算法本身：操作系统 的虚拟内存用多级页表组织地址映射，本质是一棵多级树；数据库的 索引 用 B+ 树和哈希结构加速查询；编译原理 的符号表用哈希表存储变量信息——数据结构是这些系统共同的地基。