Java - 数据结构
2019-03-23 本文已影响0人
zorkelvll
image
ZERO
持续更新 请关注：https://zorkelvll.cn/blogs/zorkelvll/articles/2019/01/11/1547220014825
背景
本文主要是记录在学习 Java - 数据结构 过程中的一些知识点备忘！
20190114
一、数据结构
1、链表LinkedList
- 链表即是由节点Node组成的线性集合，每个节点可以利用指针指向其他节点。它是一种包含了多个节点的、能够用于表示序列的数据结构
- 单向链表：链表中的节点仅指向下一个节点，并且最后一个节点指向空
- 双向链表：链表中的每个节点均具有两个指针p、n,且p指向前驱节点&n指向后继节点；最后一个节点的n指针指向null
- 循环链表：每个节点指向下一个节点并且最后一个节点指向第一个节点的链表
- ？？时间复杂度？？：
- 索引：
O(n) - 搜索：
O(n) - 插入：
O(1) - 移除：
O(1)
- 索引：
2、栈Stack
- 栈是元素的集合，包含两个基本操作：push操作可用于将元素压入栈，pop操作可将栈顶元素移除
- 符合后入先出原则
- ？？时间复杂度？？：
- 索引：
O(n) - 搜索：
O(n) - 插入：
O(1) - 移除：
O(1)
- 索引：
3、队列Queue
- 队列是元素的集合，包含两个基本操作：enqueue操作可用于将元素插入到队列中，dequeue操作则是将元素从队列中移除
- 符合先入先出原则
- ？？时间复杂度？？：
- 索引：
O(n) - 搜索：
O(n) - 插入：
O(1) - 移除：
O(1)
- 索引：
4、树Tree
- 树是无向、连通的无环图
4.1、二叉树Binary Tree
- 二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构
- 满二叉树：树中的每个节点仅包含0或2个节点
- 完美二叉树：二叉树中的每个叶节点都用于两个子节点，并且具有相同的高度
- 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点
4.2、二叉搜索树Binary Search Tree
- 二叉搜索树BST是一种特殊的二叉树，其任何节点中的值都会大于或等于其左子树中存储的值，并且小于或者等于其右子树中存储的值
- ？？时间复杂度？？：
- 索引：
O(n) - 搜索：
O(n) - 插入：
O(n) - 移除：
O(n)
- 索引：
imagepng
4.3、字典树Trie
- 字典树，又称基数树或前缀树，能够用于存储键为字符串的动态集合或者关联数组的搜索树。树中的节点并没有直接存储关联键值，而是该节点在树中的挂载位置决定了其关联键值。某个节点的所有子节点都拥有相同的前缀，整棵树的根节点则是空字符串
imagepng
4.4、树状数组FenwickTree
- 树状数组，又称Binary Indexed Tree，其表现形式为树；本质上是以数组实现，数组中的下标代表着树中的顶点，每个顶点的父节点或者子节点的下标能够通过位运算获得。数组中的每个元素包含了预计算的区间值之和，在整棵树更新的过程中同样会更新这些预计算的值
- ？？时间复杂度？？：
- 区间求值：
O(log(n)) - 更新：
O(log(n))
- 区间求值：
imagepng
4.5、线段树SegmentTree
- 线段树是用于存放间隔或者线段的树形数据结构，它允许快速地查找某一个节点在若干条线段中出现的次数
- ？？时间复杂度？？：
- 区间查询：
O(log(n)) - 更新：
O(log(n))
- 区间查询：
imagepng
5、堆Heap
- 堆是一种特殊的基于树的满足某些特性的数据结构，整个堆中的所有父子节点的键值都会满足相同的排序条件
- 堆更准确地可以分为最大堆与最小堆：在最大堆中，父节点的键值永远大于或等于子节点的值，并且整个堵中的最大值存储于根节点；在最小堆中，父节点的键值永远小于或者等于其子节点的键值，并且整个堆中的最小值存储于根节点
- ？？时间复杂度？？：
- 访问最大值/最小值：
O(1) - 插入：
O(log(n)) - 移除最大值/最小值：
O(log(n))
- 访问最大值/最小值：
6、哈希Hashing
- 哈希是能够将任意长度的数据映射到固定长度的数据；哈希函数返回的即是哈希值，如果两个不同的键得到相同的哈希值，这种现象称之为碰撞
- Hash Map：是一种能够建立起键与值之间关系的数据结构，Hash Map能够使用哈希函数将键转化为桶或者槽中的下标，从而优化对于目标值的搜索速度
- 碰撞解决：
- 链地址法Separate Chaining：在链地址法中，每个桶是相互独立的，包含了一系列索引的列表。搜索操作的时间复杂度是搜索桶的时间（固定时间）与遍历列表的时间之和
- 开地址法Open Addressing：在开地址法中，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到下一个未被占用的地址。所谓开地址法也是指某个元素的位置并不永远由其哈希值决定
7、图Graph
- 图是一种数据元素间为多对多关系的数据结构，加上一组基本操作构成的抽象数据类型
- 无向图Undirected Graph：无向图具有对称的邻接矩阵，因此如果存在某条从节点u到节点v的边，反之从v到u的边也存在
- 有向图Directed Graph：有向图的邻接矩阵是非对称的，即如果存在从u到v的边并不意味着一定存在从v到u的边
20190113
4、Map
5、树
- 二叉树：每个节点最多只有两个分支的树结构
- 完全二叉树
- 满二叉树
- 堆
- 二叉查找树
- 平衡二叉树
- 红黑树
- B-,B+,B*树
- LSM树
6、图
7、BFS DFS
20190111
1. 队列Queue
一种只允许在一端进行插入，在另一端进行删除的线性表结构。运行插入的一端叫队尾（rear），允许删除的一端叫队头（font）
- 支持FIFO，尾部添加、头部删除（即先进先出）
- 队列分“单队列、循环队列”两种：单队列，即是“每次添加元素时，均是添加到队尾，存在假溢出的问题，也就是明明有位置却不能添加的情况”；循环队列，则是避免了假溢出的问题
假溢出：当尾部插入速度小于头部删除速度时，出现rear==front的现象，但是此时队列并没有满，而且正好相反的是队列此时为空，存储空间最大，但继续插入元素时，rear值已经到达MAXSIZE边界条件，此时无法插入也无法删除。
2. 集合Set
Set继承于Collection接口，是一个不允许出现重复元素且无序的集合，主要有HashSet和TreeSet两大实现类
在判断重复元素的时候，Set集合通过调用hashCode()和equals()方法来实现
-
有序集合：集合里的元素可以根据key或index访问（List、Map）
-
无序集合：集合里的元素只能遍历（Set）
-
HashSet：哈希表结构，主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置
-
TreeSet：红黑树结构，每一个元素都是树中的一个节点，插入的元素都会进行排序
3. 列表List
在List中，可以精确地控制列表中每个元素的插入位置，且可以通过整数索引（列表中的位置）访问元素，搜索列表中的元素！不用于Set,List允许重复元素，且List是有序集合，Set是无序集合
- ArrayList：数组队列，也即动态数组；由数组实现，随机访问效率高，随机插入、随机删除效率低
- LinkedList：双向链表，可以被当做堆栈、队列或双向队列进行操作；LinkedList随机访问效率低，但是随机插入、随机删除效率高
- Vector：矢量队列，也是一个动态数组；由数组实现，但是Vetcor是线程安全的（ArrayList非线程安全）
- Stack：栈，继承于Vector；FILO（先进后出）
