常用数据结构

程序=数据结构+算法，数据结构是程序的骨架，而算法则是程序的灵魂

常用的数据结构

1. 数组（Array）：是一种线性数据结构，由相同类型的元素组成，可以通过索引访问元素。
2. 链表（Linked List）：是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。
3. 栈（Stack）：是一种后进先出（LIFO）的数据结构，只允许在一端进行插入和删除操作。
4. 队列（Queue）：是一种先进先出（FIFO）的数据结构，允许在一端插入元素，在另一端删除元素。
5. 树（Tree）：是一种非线性数据结构，由节点和边组成，每个节点可以有零个或多个子节点。
6. 图（Graph）：是一种非线性数据结构，由节点（顶点）和边组成，用于表示多对多的关系。
7. 哈希表（Hash Table）：是一种使用哈希函数来组织数据的数据结构，可以实现快速的插入、删除和查找操作。
8. 堆（Heap）：是一种特殊的树形数据结构，通常用于实现优先队列。
9. 集合（Set）和映射（Map）：是用于存储唯一值的数据结构，集合中的元素没有顺序，而映射由键值对组成。

https://juejin.cn/post/6844904167568310279

数组

1. 线性表：线性表就是所有数据元素排成像一条线一样的结构，线性表上的数据元素都是相同类型，且每个数据元素最多只有前、后两个方向。数组就是一种线性表结构，此外，栈、队列、链表都是线性表结构。
2. 连续的内存空间：线性表有两种存储结构：「顺序存储结构」和「链式存储结构」。其中，「顺序存储结构」是指占用的内存空间是连续的，相邻数据元素之间，物理内存上的存储位置也相邻。数组也是采用了顺序存储结构，并且存储的数据都是相同类型的。

• 优点：随机访问快速，内存连续，易于实现。
• 缺点：插入和删除操作可能需要移动大量元素，固定大小，不易动态扩展。

链表

链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。

• 优点：插入和删除操作快速，不需要连续内存空间，易于动态扩展。
• 缺点：随机访问慢，占用额外空间存储指针。

双向链表（Doubly Linked List）：链表的一种，也叫做双链表。它的每个链节点中有两个指针，分别指向直接后继和直接前驱。

循环链表（Circular linked list）：链表的一种。它的最后一个链节点指向头节点，形成一个环。

栈

栈（Stack）：一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线性表。

• 优点：后进先出的特性适合某些问题，实现简单。
• 缺点：只能在栈顶进行操作，不适合随机访问。

队列

队列（Queue）：一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表

• 优点：先进先出的特性适合某些问题，实现简单。
• 缺点：只能在队列头和尾进行操作，不适合随机访问。

树

• 优点：快速搜索、插入、删除，能够自平衡。
• 缺点：复杂的实现，可能需要维护平衡性。

二叉搜索树（Binary Search Tree）：也叫做二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树：

• 如果任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
• 如果任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
• 任意节点的左子树、右子树均为二叉搜索树。

前序遍历 访问根结点；先序遍历左子树；先序遍历右子树。
中序遍历 中序遍历左子树；访问根结点；中序遍历右子树。
后序遍历 后序遍历左子树；后序遍历右子树；访问根结点。

private void inOrder(BSTNode<T> tree) {
    if(tree != null) {
        inOrder(tree.left);
        System.out.print(tree.key+" ");
        inOrder(tree.right);
    }
}

public void inOrder() {
    inOrder(mRoot);
}

平衡二叉树（Balanced Binary Tree）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量

AVL树：AVL树是高度平衡的二叉树。它的特点是: AVL树中任何节点的两个子树的高度最大差别为1，AVL树的平衡性要求更加严格，因此在插入和删除操作时可能需要进行更多的旋转操作来保持平衡，这可能会导致性能略低于其他平衡二叉树

红黑树（Red Black Tree） 红黑树是一种自平衡的二叉搜索树，它通过引入“颜色”来保持树的大致平衡，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，是平衡二叉树和AVL树的折中

红黑树与AVL树的比较:

• 1.AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异
• 2.红黑树的插入删除比AVL树更便于控制操作
• 3.红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)

B树（B-tree）：多路搜索树，每个节点可以拥有多个子节点。

• 优点：适合大规模数据存储，减少磁盘I/O操作；搜索、插入和删除的时间复杂度稳定在O(log n)。
• 缺点：实现复杂，不适合小规模数据。

B+树（B+ tree） 基于B树的一种树结构，叶节点之间通过指针连接形成有序链表

• 优点：适合大规模数据存储，减少磁盘I/O操作；范围查询效率高。
• 缺点：实现复杂。

Trie树（前缀树） 多叉树，用于存储字符串集合，通常用于字符串检索。

• 优点：适合前缀匹配检索；搜索效率高。
• 缺点：空间消耗较大。

图

图(Graph) 是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

• 优点：能够表示复杂的关系和网络结构。
• 缺点：实现和算法复杂，占用空间较大。

和线性表，树的差异:

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
• 线性表可以没有元素，称为空表；树中可以没有节点，称为空树；但是，在图中不允许没有顶点(有穷非空性)。
• 线性表中的各元素是线性关系，树中的各元素是层次关系，而图中各顶点的关系是用边来表示(边集可以为空)

常用算法

1. 深度优先搜索（Depth-First Search, DFS）：
   • DFS是一种用于遍历或搜索图的算法，它从图中某个顶点开始，沿着一条路径尽可能深地访问图的顶点，直到这条路径上的所有顶点都被访问过，然后回溯并继续搜索其他路径。
   • DFS通常用于检测图中的环路、连通分量、拓扑排序等问题。
2. 广度优先搜索（Breadth-First Search, BFS）：
   • BFS是一种用于遍历或搜索图的算法，它从图中某个顶点开始，依次访问该顶点的所有邻居，然后再依次访问邻居的邻居，依此类推，直到图中所有可达的顶点都被访问。
   • BFS通常用于计算最短路径、最小生成树、网络流等问题。
3. 最短路径算法：
   • 最短路径算法用于计算图中两个顶点之间的最短路径。常用的最短路径算法包括Dijkstra算法和Bellman-Ford算法，它们分别适用于不含负权边的图和含有负权边的图。
4. 最小生成树算法：
   • 最小生成树算法用于找到一个连通图的最小生成树，即包含图中所有顶点的一棵树，并且边的权值之和最小。常用的最小生成树算法包括Prim算法和Kruskal算法。
5. 拓扑排序算法：
   • 拓扑排序算法用于对有向无环图（DAG）中的顶点进行排序，使得图中任意一条有向边上的终点在排序中都排在起点的后面。常用的拓扑排序算法包括深度优先搜索和Kahn算法。
6. 强连通分量算法：
   • 强连通分量算法用于将有向图中的顶点划分成强连通分量，即图中的极大强连通子图。常用的强连通分量算法包括Kosaraju算法和Tarjan算法。

哈希表

哈希表（Hash Table） 散列表也叫哈希表，是一种通过键值对直接访问的数据结构

• 优点：快速的插入、删除、查找操作。
• 缺点：可能存在哈希冲突，不支持顺序访问。

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

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

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

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

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

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

确定好散列函数之后，通过某个key值的确会得到一个唯一的value地址。但是却会出现一些特殊情况。即通过不同的key值可能会访问到同一个地址，这个现象称之为冲突。

冲突在发生之后，当在对不同的key值进行操作时会使得造成相同地址的数据发生覆盖或者丢失，是非常危险的。所以在设计散列表往往还需要采用冲突解决的办法。

常用的冲突处理方式有很多，常用的包括以下几种：

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

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

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

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

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

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

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

堆

堆（Heap）堆通常是一个可以被看做一棵树的数组对象。堆的具体实现一般不通过指针域，而是通过构建一个一维数组与二叉树的父子结点进行对应，因此堆总是一颗完全二叉树

• 优点：能够快速找到最大或最小值。
• 缺点：插入和删除操作相对慢。

堆常用来实现优先队列，比如堆排序、topK问题等。由于堆的根节点是序列中最大或者最小值，因而可以在建堆以及重建堆的过程中，筛选出数据序列中的极值，从而达到排序或者挑选topK值的目的