数据结构介绍
数据结构是组织和存储数据的方式。选择时先确定需要频繁执行的操作，例如按位置读取、在两端增删、按键查询或查找相邻节点。
一、介绍
- 线性结构按顺序组织元素，常见的有数组、链表、栈与队列。
- 树组织具有层级关系的节点，常见形式有二叉搜索树、AVL 树、红黑树、B 树、堆、Trie 和哈夫曼树。并查集可以用父节点数组表示一片森林。
- 散列表通过散列函数定位键所在的桶，需要处理多个键映射到同一位置的冲突。
- 图由顶点和边组成，可用邻接矩阵或邻接表存储。
二、线性表
线性表是由零个或多个元素组成的有限序列。
- 数组支持按下标直接访问。固定长度的数组在创建时确定容量，动态数组通过分配更大的数组并复制元素来扩容。
- 链表通过节点间的引用维持顺序。节点可以分散存放，每个节点需要额外空间保存链接。
- 栈在同一端压入和弹出元素，遵循后进先出。
- 队列通常在队尾入队、在队头出队，遵循先进先出。
三、线性表选择
| 常见操作 | Java ArrayList | Java LinkedList |
|---|---|---|
| 按下标读取 | O(1) | 最坏 O(n)，从较近的一端遍历 |
| 在尾部添加 | 摊销 O(1) | O(1) |
| 在头部添加或删除 | O(n)，需要移动元素 | O(1) |
| 在中间添加或删除 | O(n)，需要移动后续元素 | 已用迭代器定位时为 O(1)，按下标先查找时最坏为 O(n) |
在选择前把定位成本也算进操作成本。若主要需求是从两端入队和出队，可以用 Java 的 Deque 表达接口。ArrayList、LinkedList
四、树
树可以为空。有节点时，根节点是起点，节点之间可以形成父子、兄弟和子树关系。二叉树的两个子树分别称为左子树和右子树。
- 节点的度是子节点数，树的度是所有节点度数的最大值。
- 没有子节点的节点称为叶子。本文按边数计算深度和高度，根节点深度为 0，叶子高度为 0。
- 节点深度是根到该节点的路径长度。节点高度是该节点到最远叶子的路径长度。按层数表示时，根节点是第一层。
五、散列中的位运算
31 * x 在整数运算中可写成 (x << 5) - x。当 x 非负且 m 是 2 的幂时，x % m 等于 x & (m - 1)。后一个等式可用于计算容量为 2 的幂的桶下标。