Java数据结构详解与实战应用

发表时间: 2024-06-11 21:19

在Java中，数据结构一般可以分为两大类：线性数据结构和非线性数据结构

一、线性数据结构：线性数据结构是指数据元素之间存在一对一的关系，即每个元素都有一个前驱和一个后继元素，形成线性序列。常见的线性数据结构包括：

数组（Array）：一组连续存储的元素，通过索引进行访问。

链表（Linked List）：由一系列节点组成，每个节点包含数据和指向下一个节点的引用。

栈（Stack）：后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

队列（Queue）：先进先出（FIFO）的数据结构，允许在队尾插入元素，在队首删除元素。

数组（Arrays）

数组（Arrays）是一种基本的数据结构，可以存储固定大小的相同类型的元素。

int[] array = new int[5];

特点： 固定大小，存储相同类型的元素。
优点： 随机访问元素效率高。
缺点： 大小固定，插入和删除元素相对较慢。

列表（Lists）

Java 提供了多种列表实现，如 ArrayList 和 LinkedList。

List<String> arrayList = new ArrayList<>();List<Integer> linkedList = new LinkedList<>();

ArrayList:

特点： 动态数组，可变大小。
优点： 高效的随机访问和快速尾部插入。
缺点： 中间插入和删除相对较慢。

LinkedList:

特点： 双向链表，元素之间通过指针连接。
优点： 插入和删除元素高效，迭代器性能好。
缺点： 随机访问相对较慢。

集合（Sets）

集合（Sets）用于存储不重复的元素，常见的实现有 HashSet 和 TreeSet。

Set<String> hashSet = new HashSet<>();Set<Integer> treeSet = new TreeSet<>();

HashSet:

特点： 无序集合，基于HashMap实现。
优点： 高效的查找和插入操作。
缺点： 不保证顺序。

TreeSet:

特点：TreeSet 是有序集合，底层基于红黑树实现，不允许重复元素。
优点： 提供自动排序功能，适用于需要按顺序存储元素的场景。
缺点： 性能相对较差，不允许插入 null 元素。

映射（Maps）

映射（Maps）用于存储键值对，常见的实现有 HashMap 和 TreeMap。

Map<String, Integer> hashMap = new HashMap<>();Map<String, Integer> treeMap = new TreeMap<>();

HashMap:

特点： 基于哈希表实现的键值对存储结构。
优点： 高效的查找、插入和删除操作。
缺点： 无序，不保证顺序。

TreeMap:

特点： 基于红黑树实现的有序键值对存储结构。
优点： 有序，支持按照键的顺序遍历。
缺点： 插入和删除相对较慢。

栈（Stack）

栈（Stack）是一种线性数据结构，它按照后进先出（Last In, First Out，LIFO）的原则管理元素。在栈中，新元素被添加到栈的顶部，而只能从栈的顶部移除元素。这就意味着最后添加的元素是第一个被移除的。

Stack<Integer> stack = new Stack<>();

Stack 类:

特点： 代表一个栈，通常按照后进先出（LIFO）的顺序操作元素。

队列（Queue）

队列（Queue）遵循先进先出（FIFO）原则，常见的实现有 LinkedList 和 PriorityQueue。

Queue<String> queue = new LinkedList<>();

Queue 接口:

特点： 代表一个队列，通常按照先进先出（FIFO）的顺序操作元素。
实现类： LinkedList, PriorityQueue, ArrayDeque。

2、非线性数据结构：非线性数据结构是指数据元素之间存在一对多或多对多的关系，形成非线性结构。常见的非线性数据结构包括：

树（Tree）：由节点组成的层级结构，每个节点可以有零个或多个子节点。

散列表（Hash Table）：使用哈希函数将键映射到存储位置的数据结构，通常用于实现集合和映射。

图（Graph）：由节点（顶点）和边组成的集合，描述对象之间的关系，可以是有向图或无向图。

堆（Heap）：特殊的树形数据结构，通常用于实现优先队列。

堆（Heap）

堆（Heap）优先队列的基础，可以实现最大堆和最小堆。

PriorityQueue<Integer> minHeap = new PriorityQueue<>();PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

树（Trees）

Java 提供了 TreeNode 类型，可以用于构建二叉树等数据结构。

class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int x) { val = x; }}

5.栈：

是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出从栈顶放入元素的操作叫入栈（压栈），取出元素叫出栈（弹栈）

入栈操作：

数据结构	优点	缺点
数组	查找快	增删慢
链表	增删快	查找慢
哈希表	增删、查找都快	数据散列，对存储空间有浪费
栈	顶部元素插入和取出快	除顶部元素外，存取其他元素都很慢
队列	顶部元素取出和尾部元素插入快	存取其他元素都很慢
二叉树	增删、查找都快	删除算法复杂
红黑树	增删、查找都快	算法复杂
位图	节省存储空间	不方便描述复杂的数据关系

二、非线性结构有：堆、树(二叉树、B树、B+树

6.堆：

堆可以看做是一颗用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据“堆属性”来排序，“堆属性”决定了树中节点的位置。

堆的特性：如果一个结点的位置为k，则它的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从arr[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆；

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1)满足前者的表达式的成为小顶堆（小根堆），满足后者表达式的为大顶堆（大根堆），很明显我们上面画的堆数据结构是一个大根堆；

大小根堆数据结构图：

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

7.树：

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

1）每个节点有0个或多个子节点；

2）没有父节点的节点称为根节点；

3）每一个非根节点有且只有一个父节点；

4）除了根节点外，每个子节点可以分为多个不相交的子树；

5）右子树永远比左子树大，读取顺序从左到右；

树的分类有非常多种，平衡二叉树（AVL）、红黑树RBL（R-B Tree）、B树（B-Tree）、B+树（B+Tree）等，但最早都是由二叉树演变过去的；

1.二叉树分类

每个结点最多有两颗子树

　　时间复杂度最好情况是O(logn) ，最坏情况下时间复杂度O(n)

　　1）满二叉树：如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

　　2）完全二叉树：如果一个二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。　　

3）二叉查找树：左子树上的值都比其根节点小，右子树上的值都比其根节点大。

　　　二叉查找树的中序遍历一定是从小到大排序的。

　　4）平衡二叉树（红黑树）：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

　　　平衡二叉树必须是二叉查找树

　　性能：平衡二叉树在添加和删除时需要进行复杂的旋转保持整个树的平衡，最终，插入、查找的时间复杂度都是 O(logn)，性能已经相当好了。

　　5）最优二叉树(哈夫曼树): 树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

　　　　哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。应用：哈夫曼编码。

2.红黑树：是一种自平衡二叉查找树。应用内存排序。

插入和删除的最坏的时间复杂度是O(log N) 。

红黑树左旋和右旋的目的是为了自平衡。

参考：1.红黑树、B+树 2.红黑树在什么时候左旋右旋如何旋转

　　1）每个节点非红即黑；

　　2）根节点是黑的；

　　3）每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；

　　4）如果一个节点是红的,那么它的两儿子都是黑的；

　　5）对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；

　　6）高度始终保持在h = logn

　　7）红黑树的查找、插入、删除的时间复杂度最坏为O(log n)

2.1 变色规则红黑树使用红黑二色进行“着色”,目的是利用颜色值作为二叉树的平衡对称性的检查。

当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：

（1）把父节点设为黑色

（2）把叔叔也设为黑色

（3）把祖父也就是父亲的父亲设为红色（爷爷）

（4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则

这里我们新插入一个值 6 ( 插入的节点都是红色的所以 6 是红色的节点 ) ，变色后的图形。

红黑树的创建：节点的初始颜色为红色。

2.2 左旋：

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

2.3 右旋：

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

2.4 红黑树查找：和二叉平衡树的查找一样

3.B树(多叉树)：

平衡多路查找树（查找路径不只两个），不同于常见的二叉树，它是一种多叉树。O(logN)

4.B+树：

是一种自平衡树数据结构，它保持数据排序；在进行搜索、顺序访问、插入和删除的复杂度是O(log n)且B+树只在叶子节点中存放数据，所以消除了一些B树的缺陷。非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中。O(nlogn)

4.1 B+树查找：树的高度低，支持范围查找

4.2 mysql为什么采用B+树

　　1）磁盘IO的次数更少

　　2）支持范围查找

4.3 B树与B+树的区别

　　1）B+树所有数据都存在叶子节点

　　2）B+树的叶子节点有双向指针,方便范围查找，且叶节点上的数据从小到大顺序连接

三、图(对现实世界建模)

图是一系列顶点（元素）的集合，这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

图分为有向图和无向图：

有向图：边不仅连接两个顶点，并且具有方向；

无向图：边仅仅连接两个顶点，没有其他含义；

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