数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映了数据的内部构成，即数据由哪些成分数据构成，以及这些成分数据之间呈现的结构关系。
数据结构的逻辑结构示意：
数据结构分类
├── 线性结构
│ ├── 数组 (Array) → 连续存储，顺序访问
│ ├── 链表 (Linked) → 离散存储，指针连接
│ ├── 栈 (Stack) → LIFO，一端操作
│ └── 队列 (Queue) → FIFO，两端操作
│
├── 树形结构
│ ├── 二叉树 (Binary Tree) → 最多两个子节点
│ ├── 平衡树 (Balanced Tree) → AVL、红黑树
│ ├── 堆 (Heap) → 完全二叉树，优先队列
│ └── B/B+树 → 多路搜索树，数据库索引
│
├── 图形结构
│ ├── 有向图 (Directed) → 边有方向
│ └── 无向图 (Undirected) → 边无方向
│
└── 哈希结构
├── 哈希表 (Hash Table) → 键值映射
├── 集合 (Set) → 去重元素
└── 映射 (Map) → 键值对存储
- 逻辑结构：数据元素之间的逻辑关系（线性、树形、图形、集合）
- 存储结构（物理结构）：数据在内存中的实际存储方式（顺序、链式、索引、散列）
- 数据运算：对数据进行的操作（增、删、查、改、遍历、排序）
┌────────────────────────────────────────────────────────────────┐
│ 存储方式 │ 结构示意 │ 特点 │
├───────────┼──────────┼────────────────────────────────────────┤
│ 顺序存储 │ [1][2][3]│ 物理位置连续，随机访问O(1) │
│ │ ↑↑↑ │ 插入删除需移动元素，空间利用率低 │
├───────────┼──────────┼────────────────────────────────────────┤
│ 链式存储 │ [1]→[2]→ │ 物理位置离散，指针连接 │
│ │ │ 插入删除O(1)，访问需遍历O(n) │
├───────────┼──────────┼────────────────────────────────────────┤
│ 索引存储 │ 索引表 │ 建立附加索引表，提高查找效率 │
│ │ ↓↓↓ │ 需要额外空间存储索引 │
│ │ 数据区 │ │
├───────────┼──────────┼────────────────────────────────────────┤
│ 散列存储 │ hash(k)→ │ 通过哈希函数直接定位 │
│ │ 地址 │ 理想情况O(1)，存在冲突处理问题 │
└───────────┴──────────┴────────────────────────────────────────┘
优点：
- 高效访问：合适的数据结构可将操作复杂度降至O(1)
- 优化存储：紧凑存储，减少内存开销
- 算法基础：算法建立在数据结构之上，相辅相成
- 问题建模：帮助将现实问题抽象为计算问题
缺点：
- 选择复杂：需根据场景选择合适结构，选择不当效率降低
- 空间换时间：某些结构需要额外空间换取时间效率
- 实现复杂：高级数据结构实现难度大，易出错
概述：
- 最基础的线性数据结构，元素在内存中连续存储
- 支持通过索引O(1)随机访问
结构示意：
索引: 0 1 2 3 4
┌─────┬─────┬─────┬─────┬─────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└─────┴─────┴─────┴─────┴─────┘
↑ ↑
基地址 基地址+4×size
核心操作：
- 访问：O(1)
- 插入/删除：O(n)
- 搜索：O(n)，有序数组O(log n)
实现目录：array/
概述：
- 节点离散存储，通过指针连接
- 支持动态扩容，插入删除高效
结构示意：
单向链表:
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│data │ │data │ │data │ │data │
│ 10 │───→│ 20 │───→│ 30 │───→│ 40 │───→ NULL
│next │ │next │ │next │ │next │
└─────┘ └─────┘ └─────┘ └─────┘
↑
head
双向链表:
┌─────┐ ┌─────┐ ┌─────┐
│prev │←───│prev │←───│prev │
│data │ │data │ │data │
│ 10 │───→│ 20 │───→│ 30 │
│next │───→│next │───→│next │
└─────┘ └─────┘ └─────┘
核心操作：
- 访问：O(n)
- 插入/删除：O(1)（已知位置）
- 搜索：O(n)
实现目录：linked/（单向、双向、循环、双向循环）
概述：
- 后进先出（LIFO）的线性结构
- 只允许在一端（栈顶）进行插入和删除
结构示意：
栈的操作过程:
初始: 空栈
┌─────┐
│ │ ← 栈顶 (top = -1)
└─────┘
压栈 10:
┌─────┐
│ 10 │ ← 栈顶
└─────┘
压栈 20:
┌─────┐
│ 20 │ ← 栈顶
├─────┤
│ 10 │
└─────┘
压栈 30:
┌─────┐
│ 30 │ ← 栈顶
├─────┤
│ 20 │
├─────┤
│ 10 │
└─────┘
出栈 (pop 30):
┌─────┐
│ 20 │ ← 栈顶 (30被移除)
├─────┤
│ 10 │
└─────┘
核心操作：
- 压栈/出栈：O(1)
- 访问栈顶：O(1)
应用场景：
- 函数调用栈
- 表达式求值（中缀转后缀）
- 括号匹配
- 浏览器前进后退
- DFS遍历
实现目录：stack/
概述：
- 先进先出（FIFO）的线性结构
- 在队尾插入，在队头删除
结构示意：
队列的操作过程:
初始: 空队列
队头 ↑ ↑ 队尾
┌─────┬─────┬─────┐
│ │ │ │
└─────┴─────┴─────┘
入队 10:
队头 ↑ ↑ 队尾
┌─────┬─────┬─────┐
│ 10 │ │ │
└─────┴─────┴─────┘
入队 20:
队头 ↑ ↑ 队尾
┌─────┬─────┬─────┐
│ 10 │ 20 │ │
└─────┴─────┴─────┘
入队 30:
队头 ↑ ↑ 队尾
┌─────┬─────┬─────┐
│ 10 │ 20 │ 30 │
└─────┴─────┴─────┘
出队 (移除 10):
队头 ↑ ↑ 队尾
┌─────┬─────┬─────┐
│ │ 20 │ 30 │
└─────┴─────┴─────┘
(10已出队)
核心操作：
- 入队/出队：O(1)
- 访问队头/队尾：O(1)
应用场景：
- 任务调度
- 消息队列
- BFS遍历
- 缓存实现（LRU）
实现目录：queue/
概述：
- 通过哈希函数将键映射到存储位置
- 理想情况下实现O(1)的增删查改
结构示意：
哈希表结构 (链地址法处理冲突):
索引: 0 1 2 3 4 5 6
┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
│● │ │ │ │● │ │ │ │● │ │● │ │ │
└┬┘ └──┘ └┬┘ └──┘ └┬┘ └┬┘ └──┘
│ │ │ │
↓ ↓ ↓ ↓
┌───┐ ┌───┐ ┌───┐ ┌───┐
│John│ │Kate│ │Tom│ │Amy│
│23 │ │35 │ │18 │ │25 │
└───┘ └───┘ └───┘ └───┘
│
↓
┌───┐
│Bob│
│30 │
└───┘
键值对: ("John",23), ("Bob",30), ("Kate",35), ("Tom",18), ("Amy",25)
哈希函数: hash(key) = key.length % 7
查找过程:
查找 "John" → hash("John")=4 → 索引4 → 找到 (O(1))
查找 "Bob" → hash("Bob")=3 → 索引3 → 链表中查找
冲突处理方法：
- 链地址法：冲突元素组成链表
- 开放寻址法：线性探测、二次探测、双哈希
核心操作：
- 插入/删除/查找：平均O(1)，最坏O(n)
- 负载因子 α = n/m（n元素数，m槽位数），通常保持α < 0.75
实现目录：hash/
概述：
- 每个节点最多有两个子节点的树形结构
- 包括二叉搜索树、平衡树、堆等变体
结构示意：
二叉树结构:
┌─────┐
│ 1 │ ← 根节点 (Root)
└──┬──┘
│
┌────┴────┐
│ │
┌──┴──┐ ┌──┴──┐
│ 2 │ │ 3 │
└──┬──┘ └─────┘
│
┌───┴───┐
│ │
┌─┴─┐ ┌─┴─┐
│ 4 │ │ 5 │
└───┘ └───┘
术语:
- 根节点: 1
- 内部节点: 1, 2
- 叶子节点: 3, 4, 5
- 节点2的子节点: 4, 5
- 节点4的父节点: 2
- 树的高度: 3 (从根到最远叶子的距离)
遍历方式:
前序: 1→2→4→5→3 (根→左→右)
中序: 4→2→5→1→3 (左→根→右)
后序: 4→5→2→3→1 (左→右→根)
层序: 1→2→3→4→5 (按层从上到下)
核心操作：
- 插入/删除/查找：BST平均O(log n)，最坏O(n)
- 遍历：O(n)
应用场景：
- 文件系统
- 表达式解析
- 决策树
- 数据库索引
实现目录：tree/
概述：
- 完全二叉树，满足堆性质
- 大顶堆：父节点 ≥ 子节点
- 小顶堆：父节点 ≤ 子节点
结构示意：
大顶堆结构:
┌─────┐
│ 50 │ ← 最大值
└──┬──┘
│
┌────┴────┐
│ │
┌──┴──┐ ┌──┴──┐
│ 30 │ │ 20 │
└──┬──┘ └──┬──┘
│ │
┌───┴───┐ ┌──┴──┐
│ │ │ │
┌─┴─┐ ┌─┴─┐ ┌─┴─┐
│15 │ │10 │ │8 │
└───┘ └───┘ └───┘
数组存储 (层序遍历):
┌────┬────┬────┬────┬────┬────┐
│ 50 │ 30 │ 20 │ 15 │ 10 │ 8 │
└────┴────┴────┴────┴────┴────┘
0 1 2 3 4 5
父节点索引i的:
- 左子节点: 2i + 1
- 右子节点: 2i + 2
- 父节点: (i-1) / 2
核心操作：
- 插入：O(log n)
- 删除最大/最小：O(log n)
- 获取最大/最小：O(1)
应用场景：
- 优先队列
- 堆排序
- Top K问题
- 合并K个有序数组
实现目录：heap/
概述：
- 由顶点集合和边集合组成的数据结构
- 表示多对多的关系
结构示意：
无向图示例:
┌───┐ ┌───┐
│ A │───────│ B │
└─┬─┘ └─┬─┘
│ │
│ ┌───┐ │
└────│ C │──┘
└─┬─┘
│
┌──────┴──────┐
│ │
┌──┴──┐ ┌──┴──┐
│ D │───────│ E │
└─────┘ └─────┘
邻接表表示:
A → [B, C]
B → [A, C]
C → [A, B, D, E]
D → [C, E]
E → [C, D]
邻接矩阵表示:
A B C D E
A [0, 1, 1, 0, 0]
B [1, 0, 1, 0, 0]
C [1, 1, 0, 1, 1]
D [0, 0, 1, 0, 1]
E [0, 0, 1, 1, 0]
核心操作：
- DFS/BFS遍历：O(V+E)
- 最短路径：Dijkstra O((V+E)log V)
- 最小生成树：Kruskal/Prim O(E log V)
应用场景：
- 社交网络
- 地图导航
- 网络路由
- 任务调度
实现目录：graph/
| 数据结构 | 访问 | 搜索 | 插入 | 删除 |
|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) |
| 链表 | O(n) | O(n) | O(1)* | O(1)* |
| 栈 | O(n) | O(n) | O(1) | O(1) |
| 队列 | O(n) | O(n) | O(1) | O(1) |
| 哈希表 | N/A | O(1)** | O(1)** | O(1)** |
| 二叉搜索树 | O(log n) | O(log n) | O(log n) | O(log n) |
| 堆 | O(n) | O(n) | O(log n) | O(log n) |
| 图(邻接表) | O(1) | O(V+E) | O(1) | O(V+E) |
*已知位置 **平均情况，最坏O(n)
| 数据结构 | 空间复杂度 | 说明 |
|---|---|---|
| 数组 | O(n) | 连续存储，可能有未使用空间 |
| 链表 | O(n) | 需额外空间存储指针 |
| 栈/队列 | O(n) | 实现方式决定 |
| 哈希表 | O(n) | 负载因子影响 |
| 二叉树 | O(n) | 每个节点需两个指针 |
| 图 | O(V+E) | 邻接表存储 |
高频访问 → 数组、哈希表
高频插入删除 → 链表
LIFO访问模式 → 栈
FIFO访问模式 → 队列
需要排序 → 平衡二叉树、堆
关系建模 → 图
场景1：需要快速查找
- 选择：哈希表
- 理由：平均O(1)查找时间
场景2：需要保持有序并快速查找
- 选择：平衡二叉搜索树
- 理由：O(log n)查找+有序遍历
场景3：需要实现LRU缓存
- 选择：哈希表 + 双向链表
- 理由：哈希表提供O(1)查找，链表提供O(1)移动
场景4：需要Top K元素
- 选择：堆
- 理由：O(log n)维护，O(1)获取最值
场景5：社交网络好友关系
- 选择：图
- 理由：自然表示多对多关系
每种数据结构都提供了多语言实现：
- C：底层实现，手动内存管理，理解原理
- Java：面向对象实现，标准库封装
- Go：简洁高效，内置切片和映射
- JavaScript：动态类型，数组和对象灵活运用
- Python：简洁语法，丰富的内置数据结构
- Rust：内存安全，所有权系统
- 数组：理解连续内存、索引访问
- 链表：理解指针、动态内存
- 栈和队列：理解受限访问的应用场景
- 哈希表：理解哈希函数、冲突处理
- 二叉树：理解递归、树遍历
- 堆：理解完全二叉树、堆化操作
- 平衡树：AVL树、红黑树
- 图：邻接表/矩阵、图算法
- 高级结构：并查集、线段树、Trie树
- 手写实现每个数据结构的基本操作
- 分析每个操作的时间/空间复杂度
- 解决实际问题时灵活选择和组合数据结构
- 阅读标准库源码，学习工业级实现