什么是数据结构？

数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

1、数据的逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构包括：

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

2、数据的物理结构

指数据的逻辑结构在计算机存储空间的存放形式。

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示 和 关系的机内表示。
由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。

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

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

3、数据存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。
一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等。

数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；
非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

线性结构与非线性结构

一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。

1、线性结构

• 是一个有序数据元素的集合
• 有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。

常用的线性结构有：数组(顺序表)，线性表，栈，队列，双队列，串。

其中静态链表是数组模拟的链式结构，数组存储下表跳转信息，建立链接逻辑。

2、非线性结构

• 非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。

常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

广义表（Lists，又称列表）是线性表的推广，其本质上非线性结构！

常用数据结构

一、数组( Array)

有序排列的同类数据元素的集合称为数组。

若将有限个类型相同的变量的集合命名，那么这个名称为数组名。

组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。

用于区分数组的各个元素的数字编号称为下标。

二、链表( Linked List)

链表是物理存储单元上非连续的、非顺序的存储结构。

数据元素的逻辑顺序是通过链表的指针地址实现。

每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。

根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

1、单链表

2、双链表

3、循环链表

4、静态链表

应用场景：

1. 结合哈希表：LRU 缓存、链地址法解决哈希冲突。
2. 循环链表：约瑟夫问题

数组与链表的区别

数组	链表
数组是一个相似数据类型的数据集合	链表是一个有相同数据类型的有续集，其中每个元素使用指针链接
数组元素可以使用数组索引随机访问	链表不允许随机访问，元素只能被有序或顺序访问
数组的数据元素在内存中连续储存	元素可能存储在内存的任意地方，链表创建一个指针指向相应的数据
插入和删除操作非常耗时，时间为O(n)，因为元素的内存地址是连续和固定的	链表的插入和删除操作非常快，时间为O(1)
数组的内存是静态分配的，在编译期间完成	链表的内存分配是动态的，在运行时动态分配
数组的大小必须在数组的声明或初始化的时候指定	链表的大小随着元素的插入或删除变化

三、栈( Stack)

• 栈（stack）又称为堆栈或堆叠，栈作为一种数据结构，它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶
• java中Stack是Vector的一个子类，只定义了默认构造函数，用来创建一个空栈。
• 栈是元素的集合，其包含了两个基本操作：push 操作可以用于将元素压入栈，pop 操作可以将栈顶元素移除。
• 遵循后进先出（LIFO）原则。

应用场景：

1. 函数调用栈（栈帧），操作数栈等。
2. 单调栈：用于求比当前元素大/小的上/下一个元素（LeetCode 42、496、503、739）。
3. 递归栈：递归调用本身基于栈，也可以转换为迭代化解法（模拟函数调用栈）。
4. 树相关：前中后序遍历、直径、路径等问题。
5. 图相关：深度优先(depth-first)搜索法。
6. 计算表达式（逆波兰式）、符号匹配、浏览器前进后退等问题。

四、队列( Queue)

• 队列是元素的集合，其包含了两个基本操作：enqueue 操作可以用于将元素插入到队列中，而 dequeue 操作则是将元素从队列中移除。
• 遵循先入先出原则 (FIFO)。

1. 队列本身是有序列表，数组或链表实现，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
2. 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
   队列增加数据时候 rear增加；队列消费数据时候 front改变。
   

应用场景：

1. 操作系统管道通信
2. 并发容器：阻塞队列、并发队列。
3. “生产者 - 消费者”、“发布 - 订阅”模型。
4. 优先级队列：最大/小堆方法解决 topK 问题。
5. 树相关：层序遍历、高度。
6. 图相关：广度优先遍历。

五、树( Tree)

树是一种数据结构，它是由 n(n≥1) 个有限节点组成一个具有层次关系的集合。

树的特点：

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

思维导图未完待补充…

六、图( Graph)

数据结构中的一个图是用G = (V, E)集合来表示的， V（vertex）是顶点集合， E(edge)是边集合。
图的相关概念如下图所示。

图的相关概念（附图）：https://blog.csdn.net/shuiyixin/article/details/83692474

1、邻接矩阵

2、邻接表

3、十字链表

4、邻接多重表

七、散列表( Hash)

1、什么是散列表？

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数 f(key)，对任意给定的关键字值 key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数 f(key) 为哈希(Hash) 函数。

2、散列表的存储

记录的存储位置=f(key)

散列表就是把 key 通过一个固定的算法函数（哈希函数），转换成一个整型数字。

然后就将该数字对数组长度进行取余，取余结果就当作数组的下标。

将 value 存储在以该数字为下标的数组空间里。

这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。

3、哈希表在集合里的应用

哈希表在应用中也是比较常见的，就如 Java 中有些集合类就是借鉴了哈希原理构造的，例如 HashMap，HashTable 等，利用 hash表的优势，对于集合的查找元素时非常方便的。

然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。

拉链法是数组结合链表的一种结构，较早前的 HashMap 底层的存储就是采用这种结构，直到 jdk1.8 之后才换成了数组加红黑树的结构，其示例图如下：

从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头。当然这个链表可能为空，也可能元素很多。

我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。

应用场景：

哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。

1. 哈希表和位图的结合——布隆过滤器
   　　可作用于网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等

2. 校验安装文件的完整性
   　　在软件部署的时候，计算软件包当前的哈希值是否与预设值相等，防止软件包被篡改或被替换。Linux提供了基于 sha 算法的命令，用于计算文件的哈希值 sha256sum fileName

3. 存储和校验用户口令
   　　用户口令不能用明文存储，更进一步，如果系统不知道用户口令明文，那就更好了，而哈希算法就可以做到既不知道用户明文，又可以校验用户口令。详见《基于哈希算法的web账户口令存储方法》，http://www.cnblogs.com/todsong/archive/2012/04/22/2465178.html

4. 校验重复提交的消息
   　　用户可能因为误操作重复提交数据，而这些数据会对系统产生影响，若要拒绝这些消息，最好的方法就是在每次提交时，计算消息的哈希值，当发现疑似重复提交的时候，做消息哈希值的对比。这是一个 CPU 密集型的操作，如果系统的 CPU 负载比较低，可以考虑使用。至于如何在代码中使用哈希算法，这里就不描述了，Java、C++都有现成的算法库可用。

5. 作为数据库乐观锁的条件
   　　数据库中，最常用的乐观锁方法是在表中增加额外的一列，用于记录一行数据的版本值，通常是一个计数或是时间戳。但是，一张已经存在大量数据的表需要增加额外的版本列，似乎不太可行，也不太方便，此时可以通过哈希计算出虚拟的版本列，用于乐观锁定控制。Oracle数据库提供了哈希算法的存储过程，输入某几个列数据的字符连接，输出该条记录的哈希值，通过比较该值判断数据是否被修改。下面是摘自《Oracle 9i&10g 编程艺术》的例子

6. 作为数据库表分区的分区条件
   　　如果难以按照某一个列对数据库表做分区，表中的数据又没有太多的业务逻辑，那么通过哈希函数强行分区是个不错的选择。详见《Oracle分区表，哈希分区的新建与增加》，http://www.cnblogs.com/todsong/archive/2012/08/26/2657158.htm

八、堆( Heap)

参考资料

[1] 数据结构：八大数据结构分类：
https://blog.csdn.net/yeyazhishang/article/details/82353846
[2] 数据结构：https://juejin.cn/post/6916804072485945358
[3] 408数据结构：
https://www.processon.com/view/6103b75a0e3e7423a334a3c5?fromnew=1
[4] 数据结构与算法：
https://www.processon.com/view/5cc266d7e4b08b66b9bb9579?fromnew=1
[5] 数据结构：八大数据结构分类：
https://blog.csdn.net/yeyazhishang/article/details/82353846
[6] 散列表原理与应用场景：https://blog.csdn.net/qq_39038793/article/details/103210889

 常用数据结构及其应用场景

 

目录

1，数组

2，链表

3，树

3.1 二叉搜索树

3.2 AVL树

3.3红黑树

补充：关于AVL树和红黑树的左旋与右旋

右旋

左旋

---

思维导图

 

1，数组

这是大家最熟悉的数据结构了；

数组的优势：

1. 随机访问（按下标访问）：时间复杂度O（1）
2. 正常查找一个元素，时间复杂度O（n）
3. 如果数组是有序的，升序或者降序，使用二分查找，时间复杂度O（logN），N为数组长度

劣势：

1. 除去首部和尾部，在中间插入或者删除元素，都要导致大量数据的移动

使用场景：

常查询，少插入或者删除的情况

2，链表

链表的优势：

1. 查询时间复杂度：时间复杂度O（N），N为链表长度
2. 插入或者删除不需要移动大量的元素，因为链表本身就是非连续的存储

劣势：

1. 查询，删除，在给定位置插入元素的时间复杂度都是O（N）这点一直被人诟病
2. 后续提出的双向链表，只是提高的删除结点的时间复杂度，其余都一样，直到跳表的出现，降低了链表查询的时间复杂度

使用场景：

多插入或者删除，少查询的情况

 

对CPU来说，数据更友好一些，因为CPU从内存中读取内容，假设数组是int类型，并不是每次都读取一个数字，4KB，而是读取一个数据块，放入到CPU缓存（cache）中，下次想从CPU的缓存中找，CPU缓存比内存的读写要快，所以对于连续存储的数据来说，连续访问或者遍历时，对CPU是较为友好的。

3，树

从计算机行业的发展可以看出，基本是朝着更快更高并发更便宜的方向狂奔不止的，并发数量要求高，响应速度要求也高，数据量极大，那么像数组，链表这种数据结构，在大数据量面前，基本丧失了所有该有的优势功能。

3.1 二叉搜索树

树很好的解决了这些问题，尤其是 二叉查找/搜索（sort）树

二叉查找树有如下的性质：

1. 左子树不为空，则左子树上所有结点的值均小于它的根结点的值
2. 右子树不为空，所有右子树上所有结点的值均大于根结点的值
3. 根结点的左右子树也是一颗二叉排序树。

看上去就完美的设定，查找时间复杂度O（logN）（log以2为底N的对数，其中N是树的深度）

但是当我们输入一串有顺序的数组后，二叉查找树就会完全退化为一个链表，查找时间复杂度O（N）

3.2 AVL树

为了解决这个问题，现在规定每个结点的左孩子结点都小于该结点，右孩子结点都大于根结点，且左右子树的高度差不大于1

但是平衡二叉树有个致命的问题：

那么为了解决这个问题，提出了AVL数，即完全平衡二叉树，每次插入一个结点，都需要使用左旋、右旋、左旋与右旋的组合来维持平衡，即每个结点的左孩子结点小于根结点，根结点小于右孩子结点，且左右子树的高度差不大于1，为了达到完全平衡，AVL树付出了太多的代价。效率不高。

为了解决这个效率问题和二叉查找树退化链表的问题，提出了红黑树

3.3红黑树

红黑树有以下特点：

1. 每个结点不是红色就是黑色
2. 红色结点不可能有连在一起的
3. 根结点都是黑色：入度为0
4. 每个红色结点的连接子结点都是黑色
5. 叶子结点都是黑色（NULL）：出度为0
6. 每个结点，从该结点到达其可达叶子结点的所有路径，都包含相同数目的黑色结点

 

如果说完全平衡二叉树是通过左旋，右旋，左旋和右旋的组合，保证每个结点的左孩子都小于根结点，右孩子都大于根结点，且左右子树的高度差不大于1

那么红黑树就是通过变色，左旋，右旋，左旋和右旋的组合，保证结点之间红黑间隔，每个结点到叶子结点经过的黑色结点个数都是一样的，以此来保持平衡

红黑树处理插入结点的规则：

插入的点默认是红色

变颜色情况：

当前结点的父亲结点是红色，且叔叔结点也是红色，红色结点不能相连，那么使用变色进行处理：

1. 把父亲结点变为黑色
2. 把叔叔结点变为黑色
3. 把祖父变成红色

把指针定义到祖父结点，查看是否符合红黑树的定义，不符合则进行变色或者左旋或右旋

 

补充：关于AVL树和红黑树的左旋与右旋

（来自大话数据结构）

右旋

左旋

通用数据结构

可以简单的按照速度将通用数据结构划分为：数组和链表（最慢），树（较快），哈希表（最快）。增、删、改、查是四大常见操作，不过其实可以浓缩为两个操作：增和查。删除操作和和修改操作都是建立在查找操作上的，所以完美的数据结构应该是具有较高的插入效率和查找效率。

通用数据结构关系

可以根据下图选择合适的通用数据结构：

数组

使用场景

数组在以下三个情形下很有用：

1）数据量较小。

2）数据规模已知。

3）随机访问，修改元素值。

如果插入速度很重要，选择无序数组。如果查找速度很重要，选择有序数组，并使用二分查找。

缺点

1）需要预先知道数据规模

2）插入效率低，因为需要移动大量元素。

链表

解决的问题

链表的出现解决了数组的两个问题：

1）需要预先知道数据规模

2）插入效率低

使用场景

1）数据量较小

2）不需要预先知道数据规模

3）适应于频繁的插入操作

缺点

1）有序数组可以通过二分查找方法具有很高的查找效率(O(log n))，而链表只能使用顺序查找，效率低下(O(n))。

二叉查找树

解决的问题

1）有序数组具有较高的查找效率(O(log n))，而链表具有较高的插入效率（头插法，O(1)），结合这两种数据结构，创建一种貌似完美的数据结构，也就是二叉查找树。

使用场景

1）数据是随机分布的

2）数据量较大

3）频繁的查找和插入操作（可以提供O(log n)级的查找、插入和删除操作）

缺点

1）如果处理的数据是有序的（升序/降序），那么构造的二叉查找树就会只有左子树（或右子树），也就是退化为链表，查找效率低下(O(log n))。

平衡树

解决的问题

1）针对二叉查找树可能会退化为链表的情况，提出了平衡树，平衡树要求任意节点的左右两个子树的高度差不超过1，避免退化为链表的情况。

使用场景

1）无论数据分布是否随机都可以提供O(log n)级别的查找、插入和删除效率

2）数据量较大

缺点

1）平衡树的实现过于复杂。

哈希表

解决的问题

同平衡树一样，哈希表也不要求数据分布是否随机，不过哈希表的实现比平衡树要简单得多。

使用场景

1）不需要对最大最小值存取。

2）无论数据分布是否随机，理想情况下（无冲突）可以提供O(1)级别的插入、查找和删除效率。

3）数据量较大

缺点

1）由于是基于数组的，数组（哈希表）创建后难以扩展，使用开放地址法的哈希表在基本被填满时，性能下降的非常严重。

2）不能对最大最小值存取。

通用数据存储结构

专用数据结构

栈

顺序栈

优点

1）在输入数据量可预知的情形下，可以使用数组实现栈，并且数组实现的栈效率更高，出栈和入栈操作都在数组末尾完成。

缺点

1)如果对数组大小创建不当，可能会产生栈溢出的情况

链栈

优点

1）不会发生栈溢出的情况

2）输入数据量未知时，使用链栈。通过头插法实现入栈操作，头删法实现出栈操作。出栈和入栈均是O(1)。

缺点

1）由于入栈时，首先要创建插入的节点，要向操作系统申请内存，所以链栈没有顺序栈效率高。

队列

如果数据量已知就使用数组实现队列，未知的话就使用链表实现队列。出队和入队均是O(1)。

 

数据结构	优点	缺点
数组	插入快	查找慢、删除慢、大小固定
有序数组	查找快	插入慢、删除慢、大小固定
栈	后进先出	存取其他项很慢
队列	先进先出	存取其他项很慢
链表	插入、删除快	查找慢
二叉树	查找、插入、删除快	算法复杂（删除算法）
红黑树	查找、插入、删除快	算法复杂
hash表	存取极快（已知关键字）、插入快	删除慢、不知关键字时存取很慢、对存储空间使用不充分
堆	插入快、删除快、对大数据项存取快	对其他数据项存取慢
图	依据现实世界建模	算法有些复杂
AVL树	查找、插入、删除快	算法复杂

--------------------- 本文来自 Flammable_ice 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/z84616995z/article/details/70153460?utm_source=copy