常见数据结构

1. 数组
2. 链表
3. 栈
4. 队列
5. 树
6. 堆
7. 散列表

1.数组

数组是可以在内存中连续存储多个单元的结构，在内存中的分配也是连续的，数组中的元素通过下标进行访问，数组下标从零开始。

//定义一个名为arr的数组，给数组的第一个元素赋值为1
int arr = new int[100];
data[0]=1;

优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便

缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。

适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。

2.链表

链表是物理存储单元上非连续的，非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包括两个结点，一个是存储元素的数据域（内存空间），另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如：单链表，双向链表，循环链表。

链表的优点：

链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；

缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。

适用场景：
数据量较小，需要频繁增加，删除操作的场景

数组和链表的对比

 3.栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不能操作，

入栈：从栈顶放入元素的操作           出栈：从栈顶取出元素的操作

特点：先进后出

 适用场景：常用于实现递归功能，例如斐波那契数列

4.队列

队列是一种特殊的线性表，队列可以在一段添加元素，在另一端取出元素。

入队：从一端放入元素的操作       出队：从另一端取出元素的操作

特点：先进先出

 适用场景：在多线程阻塞队列管理中非常适用。

5.树

是由n（n>=1）个有限节点组成的一个具有层次关系的集合。它具有一下特征：

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

我们常用的树是二叉树，二叉树的特征：

• 每个结点最多有两颗子树，结点的度最大为2
• 左子树和右子树是有顺序的，次序不能颠倒
• 即使某结点只有一个子树，也要区分左右子树

特点：它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案

 适用场景：

在处理大批量的动态数据方面非常有用。

mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树

6.堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

 适用场景：一般用来做数组中的排序，称为堆排序。

7.散列表

也叫哈希表，是一种通过键值对直接访问数据的机构。通过设定的一个关键字和一个映射函数，就可以直接获得访问数据的地址，实现O(1)的数据访问效率。在映射的过程中，事先设定的函数就是一个映射表，也可以称作散列函数或者哈希函数。

散列表的实现最关键的就是散列函数的定义和选择。一般常用的有以下几种散列函数：

直接寻址法：取关键字或关键字的某个线性函数值为散列地址。

数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。

平方取中****法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。

取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。

除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

确定好散列函数之后，通过某个key值的确会得到一个唯一的value地址。

但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址，这个现象称之为冲突。会造成相同地址的数据发生覆盖或者丢失

冲突解决的办法：

开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。

再哈希法：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。

链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。

公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。

目前比较常用的冲突解决方法是链地址法，一般可以通过数组和链表的结合达到冲突数据缓存的目的。

 左侧数组的每个成员包括一个指针，指向一个链表的头。每发生一个冲突的数据，就将该数据作为链表的节点链接到链表尾部。这样一来，就可以保证冲突的数据能够区分并顺利访问。

考虑到链表过长造成的问题，还可以使用红黑树替换链表进行冲突数据的处理操作，来提高散列表的查询稳定性。

原文：https://blog.csdn.net/qq_43207916/article/details/106968159

原文：https://www.cnblogs.com/pupilheart/p/8921164.html

常见数据结构

原文：https://www.cnblogs.com/enjoyC/p/15152400.html