数据结构

一、介绍

数据结构就是计算机存储、组织数据的方式。主要大致包括：

1. 线性结构：线性表（数组、链表、栈、队列、哈希表）
2. 树：二叉树（AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集）
3. 图形结构：邻接矩阵、邻接表

二、线性表

线性表是具有n个相同类型元素的有限序列（n>=0）

1. 数组：数组是一种顺序存储的线性表，所有元素的内存地址都是连续的。数组无法动态修改容量，即创建了长度为3的数组，无法改动。开辟、销毁内存的次数相对少，但是可能造成内存的浪费。
2. 链表：链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的。开辟、销毁内存的次数相对多，但是不会造成内存的浪费。
3. 栈：栈是一种特殊的线性表，一般只能在一端进行操作。 遵循先进后出的原则
4. 队列：队列是一种特殊的线性表，一般只能在一端进行操作。 。遵循先进先出的原则

三、线性表选择

动态数组（ArrayList）和双向链表(LinkedList)

1. 如果频繁在尾部添加、删除数据操作，动态数组和双向链表均可
2. 如果频繁在头部添加、删除数据操作，选择双向链表
3. 如果频繁在任意位置添加、删除数据，建议选择双向链表（平均复杂度O(N/2)），数组的平均复杂度为（O(n)）

四、树

树的节点有：根节点、父节点、子节点、兄弟节点的概念。

树有子树、左子树、右子树区分，即节点下的节点的树形结构为子树。

一棵树如果没有任何节点称为空树，只有一个节点称为根节点。

• 节点的度：子树的个数
• 树的度：所有节点的度中的最大值。
• 叶子节点：度为0的节点
• 树的层数：根节点在第一层，根节点的子节点在第二层，以此类推。
• 节点的深度：从根节点到当前节点的唯一路径（经历的节点数包括自身）
• 节点的高度：从当前节点到最远叶子节点的路径上的节点总数

五、奇素数

31是一个奇素数，JVM会将31*i 优化成(i << 5) - i 通过位运算计算值

取模公式X % 2^ n = X & (2^ n – 1)