数据结构及八种常用数据结构简介

data-structure

数据结构是一种存在某种关系的元素的集合。“数据” 是指元素；“结构” 是指元素之间存在的关系，分为 “逻辑结构” 和 “物理结构（又称存储结构）”。

常用的数据结构有 数组（array）、栈（stack）、队列（queue）、链表（linked list）、树（tree）、图（graph）、堆（heap）、散列表（hash）。

---

开局一张图 内容全靠编！

1、定义

数据结构是一种存在某种关系的元素的集合。“数据” 是指元素；“结构” 是指元素之间存在的关系，分为 “逻辑结构” 和 “物理结构（又称存储结构）”。

常用的数据结构有 数组（array）、栈（stack）、队列（queue）、链表（linked list）、树（tree）、图（graph）、堆（heap）、散列表（hash）。

数据结构与算法常作为一个术语出现，这里的算法用来操作数据结构中的元素的，如检索、插入、删除、更新、排序等。

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。同时，算法的设计取决于数据的逻辑结构，而算法的实现却依赖于指定的存储结构。

2、研究对象

2.1、逻辑结构

逻辑结构是指反映数据元素之间的逻辑关系的数据结构，其中逻辑关系是指数据元素之间的前后间关系，而与它们的存储位置无关。

逻辑关系包括：

• 集合：数据结构中的元素除了 “属于同一集合” 的关系外，别无其它关系。
• 线性关系：数据结构中的元素存在一对一的相互关系。
• 树形结构：数据结构中的元素存在一对多的相互关系。
• 图形结构：数据结构中的元素存在多对多的相互关系。

2.2、物理结构

物理结构是指数据在计算机存储空间的存放形式。

数据物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和逻辑关系的机内表示。

数据元素的机内表示：
用二进制位（bit）的位串表示数据元素，通常称这种位串为节点（node）。当数据元素由若干个数据项组成时，位串中与各数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示。

逻辑关系的机内表示：
逻辑关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构，即顺序存储结构和非顺序存储结构。顺序映像借助数据元素在存储器内的相对位置来表示数据元素之间的逻辑关系，非顺序映像借助指示数据元素存储位置的指针来表示数据元素之间的逻辑关系。

物理结构的实现方法分为顺序存储和非顺序存储。

• 顺序存储：
  • 特点：借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  • 常用的有 顺序存储 等。
• 非顺序存储：
  • 特点：借助指示数据元素存储位置的指针来表示数据元素之间的逻辑关系。
  • 常用的有 链式存储、索引存储、哈希存储 等。

3、分类

数据结构有很多种，一般来说，按照其逻辑结构可以分为 线性结构 和 非线性结构 两大类。

3.1、线性结构

线性结构是指各个数据元素之间具有线性关系。栈、队列 等就属于线性结构。从数据结构的角度来看，其有以下特点：

• 线性结构是非空集。
• 线性结构有且仅有一个开始结点和终端结点。
• 线性结构的所有结点都最多只有一个直接前驱结点和一个直接后继结点。

3.2、非线性结构

非线性结构是指各个数据元素之间有多个对应关系。数组、树、图 等就属于非线性结构。从数据结构的角度来看，其有以下特点：

• 非线性结构是非空集。
• 非线性结构的一个结点可能有多个直接前驱节点和多个直接后继节点。

4、常用数据结构

常用数据结构包括 数组（array）、栈（stack）、队列（queue）、链表（linked list）、树（tree）、图（graph）、堆（heap）、散列表（hash）。

4.1、数组（array）

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序的组织在一起的集合。一个数组可以分解为多个数组元素。按照元素类型，数组可以分为 整型数组、字符型数组、浮点型数组 等。数组元素是通过下标进行访问的，且下标从 0 开始。

// java 定义一个数组
String[] strings = new String[] { "zed", "fizz", "ahri" }

优点：

• 根据下标遍历和检索速度快。

缺点：

• 数组大小固定后无法扩容。
• 数组只能存储同一类型的数据。
• 插入、删除操作慢，因为要移动其他元素。

适用场景：检索多、增删少的情况。

4.2、栈（stack）

栈是一种特殊的线性表，它只能在表的一个固定端进行数据元素的插入和删除。栈按照 先进后出或后进先出 的原则存储数据，即先插入的数据被压入栈底，后插入的元素放在栈顶。读数据时，从栈顶开始读。插入亦称入栈，读取亦称出栈。

适用场景：栈长应用于实现递归功能方面的场景。

注：线性表是一种最简单的数据结构。

4.3、队列（queue）

队列和栈一样，也是一种特殊的线性表。队列按照 先进先出 的原则存储数据。和栈不同的是，队列只允许在一端进行插入操作，在另一端进行读取操作。插入操作的一端称为队尾，取出操作的一端称为队首。

适用场景：由于其先进先出的特点，队列常用在多线程应用中。

4.4、链表（linked list）

链表是一种数据元素按照 链式存储结构 存储的数据结构，这种存储结构具有在物理上非连续的特点。链表由一系列数据结点组成，每个数据结点包含数据域和指针域两部分，其中指针域存放了数据结构中下一个元素的存放地址。链表数据结构中数据元素的逻辑关系是通过链表中指针的链接次序来实现的。根据指针的指向，链表可以形成不同的结构，如单链表、双向链表、循环链表等。

优点：

• 不需要初始化容量，可以任意增删元素。
• 插入和删除操作速度很快，只需要改变前后两个结点的指针域即可。

缺点：

• 因为含有大量指针域，所以占用空间较大。
• 查找元素时需要遍历链表，非常耗时。

适用场景：数据量小、插入删除操作多的情况。

4.5、树（tree）

树是一种典型的非线性数据结构，它是由 n（n >= 1）各有限节点组成的具有层次关系的集合。

其特点是：

• 每个节点有零个或多个子节点。
• 没有父节点的节点称为根节点。
• 每一个非根节点只有一个父节点。
• 除根节点外，每个子节点可以分为多个不相交的子树。

树 数据结构有很多扩展结构，如二叉树、平衡树、 B 树、B+ 树、红黑树等。其中最常用的是二叉树。

二叉树插入、删除元素很快，且在查找方面也有很多优化算法，所以二叉树既有数组的优点，也有链表的好处，是两者的优化方案，在处理大批量动态数据方面非常有用。

树的种类：

• 无序树：树的任意节点的子节点没有顺序关系。
• 有序树：树的任意节点的子节点有顺序关系。
• 二叉树：树的任意节点至多包含两颗子树。
• 满二叉树：叶子节点都在同一层且除叶子节点外的所有结点有且只有两个子节点。
• 完全二叉树：对于一颗二叉树，假设其深度为 d（d > 1），除第 d 层外的所有节点构成满二叉树，且第 d 层所有节点从左向右连续紧密的排列。
• 平衡二叉树：它是一棵空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都为平衡二叉树，同时，平衡二叉树必定为二叉搜索树。
• 二叉搜索树：若任意节点的左子树不为空，则左子树上的所有节点值均小于该节点的值；若任意节点的右子树不为空，则右子树上的所有节点值均大于该节点的值；任意节点的左右子树也为二叉搜索树。
• 哈夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树。
• 红黑树：红黑树是一种特殊的二叉搜索树，除了二叉搜索树的特点外，其还包括一下特性：1、每个节点为黑色或红色；2、根节点时黑色；3、若叶子节点为 null 或 nil，则其为黑色；4、若一个节点为红色，则其子节点必须为黑色；5、从一个节点到该节点的子孙各路径上包含相同数目的黑节点。
• B 树：详见 /database/about mysql.md。
• B + 树：详见 /database/about mysql.md。

4.6、图（graph）

图是另一种非线性数据结构。是由顶点的有穷集合 V 和边的集合 E 组成。数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

按照顶点指向的方向可分为有向图和无向图。

图是一种较复杂的数据结构，在存储数据上有着较复杂和高效的算法，如 邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等存储结构。

4.7、堆（heap）

堆是一种特殊的树数据结构，一般讨论的堆都是二叉堆。堆的特点是根节点的值是所有节点中的最大值或最小值，为最大值时称为最大堆或大根堆；为最小值时称为最小堆或小根堆。且所有子节点也是堆结构。

适用场景：因堆有序的特点，所以常用来做排序。

4.8、散列表（hash）

散列表也叫哈希表，源自于散列函数（hash function），其思想是如果在结构中存在关键字和 T 相等的记录，那么必定在 f(T) 的存储位置可以找到该记录，这样就可以不用比较而直接获取需要查找的记录。

f 即为散列函数，又称哈希函数。则散列表是将 key 通过散列函数转换成一个整型数字，然后将该数字对数组长度进行取余，取余即是数组的下标，最后将 value 存放在该下标所对应的数组空间里。这种存储结构充分利用了数组的查找优势，所以查找速度很快。