基本数据结构

常见的数据结构，包含有数组、链表、栈、队列、树、散列表、堆、图。

---

数组

• 存储空间是连续。可以通过下表进行快速访问

---

• 优点：
  • 按照索引查询速度较快
  • 按照索引遍历速度较快
• 缺点：
  • 数组固定大小，扩容较麻烦
  • 数组只能存在一种数据结构
  • 增删改查速度较慢

---

• 使用场景：
  • 数据量较大，频繁的遍历的。

---

链表

• 存储空间不连续，通过指针进行访问下一个%%%%存储空间

---

• 优点：
  • 可以随意添加数据，添加数据较简单
  • 增删改查速度较快，只需要修改指针地址即可
• 缺点：
  • 含有大量的指针域，占用较多的空间。
  • 遍历或者查找的速度较慢，需要通过指针进行遍历。

---

• 使用场景：
  • 数据量小，大量进行增删改查。

---

栈

• 是一种特殊的线性表，只能操作其中个的一段，可以入栈和出栈。特点为先入后出（LIFO）。

---

队列

• 队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出（FIFO）。

---

• 使用场景：
  • 因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

---

树

• 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

---

• 具有特点：
  • 每一个节点都有零个或者多个子节点。
  • 没有父节点的节点成为根节点。
  • 每一个非根节点都有一个父节点。
  • 除了根节点以外，每个子节点都可以分为多个不相交的子树。

---

二叉树

• 每个父节点只有两个子节点的树为二叉树。

平衡二叉树

• 当按照某个规则（左子节点小于父节点，右子节点大于父节点构建），如果一些有序的数据存储可能会导致退化为链表，大致查询的速度就变得特别慢，所以提出了平衡二叉树，在插入数据的时候会进行平衡，具有一下特性：
• 一棵空树或它的左右两个子树的高度差的绝对值不超过1
• 右两个子树都是一棵平衡二叉树

---

红黑树

• 也是一种平衡二叉树，但是要去并没有那么严格，但也具有一下性质：
  • 每个节点非红即黑
  • 根节点是黑的;
  • 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
  • 如果一个节点是红的，那么它的两儿子都是黑的;
  • 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;

---

B 树

• 是一种多路搜索树（并不是二叉的），具有一下性质：
  • 定义任意非叶子结点最多只有M个儿子；且M>2；
  • 根结点的儿子数为[2, M]；
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  • 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
  • 非叶子结点的关键字个数=指向儿子的指针个数-1；
  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 所有叶子结点位于同一层；

---

B+树

• 相对于 B 树，B+树所有的叶子结点在同一层，但是每个节点间通过链表相互连接，所以可以进行范围行的查询。

---

散列表

• 散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。如果同一个关键码有多个 value，则会通过链表进行相互连接

---

堆

• 堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有一下性质：
  • 堆中某个节点的值总是不大于或不小于其父节点的值
  • 堆总是一棵完全二叉树

---

图

• 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

---

有向图

• 每个节点之间的线路是有方向，在单向的地方不可逆向导通

---

无向图

• 每个节点之间是无方向，不存在方向，可以相互导通

---