• 元素之间关系：
  • 集合：无关系
  • 线性结构：一对一关系
  • 树形结构：一对多关系
  • 图形结构：多对多关系

---

常用数据结构：

• 数组（Array）：
  • 优点：依赖索引查询速度快。
  • 缺点：添加、删除慢（要移动其它元素）。
• 栈（Stack）：
  • 一种特殊线性表。栈在线性表顶端添加或取出元素，先进后出。添加元素为入栈，取出元素为出栈。
• 队列（Queue）：
  • 一种特殊线性表。队列在线性表顶端添加元素，在线性表底端取出元素。先进先出，添加元素为入队，取出元素为出队。
  • 使用场景：多线程阻塞队列。
• 链表（Linked List）：
  • 物理存储单元非连续存储结构。单项链表每个元素包含两个属性，一个存储数据，另一个指向下个结点地址。
  • 优点：不需要初始化容量。添加，删除快，改变前后两个元素结点指向地址即可。
  • 缺点：占用空间较大。含有大量指针域，查找慢，需要遍历链表来查找。
• 树（Tree）：
  • 由 n（n >= 1） 个节点组成具有层次关系的集合。每个节点有零个或多个子节点，没有父节点的节点称为根节点，
    每个非根节点有且只有一个父节点。常见树如：二叉树。
• 散列表（Hash）：
  • 把 key 通过哈希函数转换成一个整型数字，将该数字对数组长度进行取余，取余结果作为当作数组下标。
    JDK 8 前使用拉链法，JDK 8 后使用数组加红黑树。
  • 优点：查找快。
  • 缺点：添加、删除慢。
• 堆（Heap）：
  • 可看做一棵树的数组对象。堆中某个节点的值总是不大于或不小于其父节点的值。堆总是一棵完全二叉树。
    将根节点最大的堆叫做最大堆或大根堆。根节点最小的堆叫做最小堆或小根堆。常见堆如：二叉堆、斐波那契堆。
• 图（Graph）：
  • 一些节点（vertex），在某些节点之间，由边（edge）相连。边表示两个节点之间的存在关系。
    在树中，用边来表示子节点和父节点的归属关系。树是一种特殊的图，但限制性更强。