概述
数据的组织方式，用于高效存储和操作数据。
核心是选择合适结构匹配操作需求（如增删查改频率）。
Java常见数据结构及特点
数组（Array）
数组是一种线性数据结构，通过连续内存空间存储元素，每个元素位置由索引直接定位
- 特点：连续内存、索引直接访问速度快、大小固定。
- 适用：频繁随机访问、内存敏感场景。
- 扩容成本高：需创建新数组并复制旧数据
数组是内存效率最高、访问最快的结构，但灵活性差；适合静态数据或已知大小的场景，动态场景优先用ArrayList
队列
队列是先进先出的线性数据结构，核心操作：入队（enqueue）、出队（dequeue）、判空。
- 顺序性：元素按加入顺序排列，先进入的先被移除。
- 两端操作：仅在队首（Head）出队，队尾（Tail）入队。
- 状态检查：需支持判断队列是否为空。
核心原则：队列的核心是顺序控制，选择时需平衡操作频率与性能需求。
链表
链表是一种非连续存储的线性数据结构，通过节点（Node）链接数据，每个节点包含值域和指针域（指向下一个节点）
- 动态大小：无需预分配内存，按需扩展。
- 插入/删除快：只需调整指针（O(1)时间，头尾最优）。
- 随机访问慢：需从头遍历（O(n)时间）。
- 内存碎片：节点分散存储，缓存命中率低。
应用场景
动态数据集：频繁增删但少查询的场景（如LRU缓存淘汰机制）。
内存敏感场景：节点可动态分配，适合大规模数据存储。
队列/栈实现：链表可实现高效的头尾操作（如Java的LinkedList底层是双向链表）。 - 总结
单链表：内存占用小，但尾插和删除需遍历。
双向链表：功能更强大，但指针维护稍复杂。
适用原则：
高频头尾操作 → 双向链表。
仅需单向遍历 → 单链表。
线程安全 → 用ConcurrentLinkedDeque
树
树是一种分层非线性数据结构，由节点构成，每个节点包含值域和子节点引用，形成父子关系。根节点无父节点，叶子节点无子节点
核心特性
层级性：节点按层级组织，根节点在第1层，子节点依次递增。
唯一路径：任意两节点间有且仅有一条路径。
分支性：节点可有多个子节点（如二叉树最多2个子节点）。
常见树类型及特点
二叉树
- 子节点:≤2个
- 特点:左右子节点区分，结构简单
- 使用场景:基础数据结构、表达式解析
二叉搜索树（BST） - 子节点:≤2个
- 特点:左子树值 < 根 < 右子树值，有序
- 使用场景:数据检索、排序
平衡树（如AVL、红黑树） - 子节点:≤2个
- 特点:自动保持左右子树高度平衡，O(log n)操作复杂度
- 使用场景:高效查找、数据库索引、语言标准库（如Java TreeMap）
堆 - 子节点:≥2个
- 特点:完全二叉树结构，父节点值 ≥（最大堆）或 ≤（最小堆）子节点
- 使用场景:优先队列、堆排序
多叉树 - 子节点:≥3个
- 特点:节点可有多个子节点，如B树、B+树
- 使用场景:文件系统索引、数据库存储
应用场景
二叉搜索树（BST）
数据动态排序、范围查询（如时间复杂度分析）。
堆
实现优先队列（如任务调度）、堆排序。
平衡树
高效索引结构（如数据库、语言集合框架）。
Trie树
字符串匹配（如自动补全、路由表）。
总结
二叉树：基础结构，用于理解树的基本概念。
BST：有序数据的高效操作，但需手动平衡。
平衡树：自动平衡，保证高性能（如Java的TreeSet）。
堆：特殊结构的完全二叉树，用于优先级管理。
选型原则：
需要有序检索 → BST/平衡树。
需要高效堆顶操作 → 堆。
字符串匹配 → Trie树。
