一、8种常见数据结构
1. 数组（Array）
- 简介：数组是有序元素的序列，连续内存块存储相同类型元素，通过下标直接访问。数组会为存储的元素都分配一个下标（索引），此下标是一个自增连续的，数组下标从0开始访问，
- 核心特点：
- 查询速度快；随机访问时间复杂度为 O(1)。
- 增删速度慢；插入/删除元素需移动后续元素，时间复杂度 O(n)。
- 大小固定（静态数组）或可扩展（动态数组）。
- 典型操作：增、删、改、查。
- 应用场景：基础数据批量存储、矩阵运算、缓存实现。
2. 链表（Linked List）
- 简介：链表是由一系列节点Node（也可称元素）组成，数据元素的逻辑顺序是通过链表的指针地址实现，通常情况下，每个节点包含两个部分，一个用于存储元素的数据，名叫数据域，另一个则指向下一个相邻节点地址的指针，名叫指针域。节点通过指针连接，根据节点指针指向，分为单向链表、双向链表和循环链表。
- 核心特点：
- 增删速度块；动态分配内存，插入/删除时间复杂度 (O(1))（已知节点位置时）。
- 查询速度慢；随机访问效率低（需从头遍历，时间复杂度 (O(n))）。
- 典型操作：头插、尾插、节点删除、反转链表。
- 应用场景：实现栈、队列、LRU缓存、哈希表冲突处理。
单向链表新增、删除元素演示：
3. 栈（Stack）
- 简介：后进先出（LIFO）的线性结构，仅允许在栈顶操作。
- 核心特点：
- 插入（
push）和删除（pop）时间复杂度均为 O(1)。 - 空间复杂度 O(n)，需避免栈溢出。
- 插入（
- 典型操作：压栈、弹栈、获取栈顶元素。
- 应用场景：函数调用栈、表达式求值、括号匹配、回溯算法。
4. 队列（Queue）
- 简介：先进先出（FIFO）的线性结构，操作在队尾（入队）和队头（出队）。
- 核心特点：
- 普通队列插入/删除时间复杂度 O(1)。
- 支持变体：双端队列（Deque）、优先队列（Priority Queue）。
- 典型操作：入队、出队、判空、获取队头元素。
- 应用场景：任务调度、BFS算法、消息队列、滑动窗口。
5. 树（Tree）
- 简介：分层数据结构，常见类型包括二叉树、平衡树、B/B+树等。
- 核心特点：
- 二叉树：每个节点最多两个子节点。
- 平衡树（如AVL、红黑树）：通过旋转保持高度平衡，保证查询效率 O(logn)。
- 典型操作：插入、删除、查找、遍历（前/中/后序）。
- 应用场景：数据库索引（B+树）、文件系统、决策树算法。
6. 图（Graph）
- 简介：由顶点（Vertex）和边（Edge）构成，分为有向图与无向图。
- 有向图：边不仅连接两个顶点，并且具有方向；
- 无向图：边仅仅连接两个顶点，没有其他含义；
- 核心特点：
- 邻接矩阵存储（空间 (O(n^2))）或邻接表存储（空间 (O(n+e))）。
- 支持权重图、稀疏图、稠密图等变体。
- 典型操作：遍历（DFS/BFS）、最短路径（Dijkstra）、最小生成树（Prim/Kruskal）。
- 应用场景：社交网络、路径规划、推荐系统、依赖分析。
7. 哈希表（Hash Table）也称为散列表
- 简介：基于键值对（Key-Value）存储，通过哈希函数映射位置。散列表其实是数组的一种扩展，由数组演化而来。
- 核心特点：
- 理想情况下查询/插入/删除时间复杂度 O(1)。
- 需处理哈希冲突（链地址法、开放寻址法）。
- 典型操作：插入、删除、查找、扩容（Rehashing）。
- 应用场景：字典、缓存（Redis）、唯一性检查、分布式一致性哈希。
8. 堆（Heap）
- 简介：堆可以看做是一棵用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。
- 分为大顶堆（父节点值 ≥ 子节点）和小顶堆。
- 核心特点：
- 堆化（Heapify）时间复杂度 O(n)。
- 插入/删除堆顶元素时间复杂度 O(logn)。
- 典型操作：插入元素（上浮）、删除堆顶（下沉）、构建堆。
- 应用场景：优先队列、Top K问题、堆排序、定时任务调度。
总结对比
| 数据结构 | 插入/删除时间复杂度 | 查询时间复杂度 | 典型用途 |
|---|---|---|---|
| 数组 | O(n) | O(1) | 快速随机访问 |
| 链表 | O(1) | O(n) | 动态数据操作 |
| 栈/队列 | O(1) | O(1) | 受限顺序操作 |
| 哈希表 | O(1) | O(1) | 高效键值存储 |
| 堆 | O(logn) | O(1) | 极值优先处理 |
选择建议：根据场景需求选择数据结构：
- 需要快速查询 → 数组、哈希表。
- 高频插入/删除 → 链表、树、堆。
- 分层关系 → 树、图。
- 顺序约束 → 栈、队列。
