分类 标签 存档 社区 博客 友链 GitHub 订阅 搜索

Java - 数据结构

371 浏览

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 边界条件,此时无法插入也无法删除。

Java 数据结构之队列(Queue)

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(先进后出)

评论  
留下你的脚步
推荐阅读