Java常见的8种数据结构「建议收藏」

Java常见的8种数据结构「建议收藏」数据结构是指数据在计算机内存空间中或磁盘中的组织形式算法是完成特定任务的过程二分法查找r=2^ss:查找步数r查找范围幂函数s=log2®已知范围获取需要的次数对数算法复杂度使用O(N)函数进行标示主要是去除常数看运行时间受数据项个数的影响常见排序参考地址https://blog.csdn.net/muranfei/article/details/80923996栈对列优先级对列栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数…

大家好,又见面了,我是你们的朋友全栈君。

第一张
在这里插入图片描述
在这里插入图片描述
数据结构是指数据在计算机内存空间中或磁盘中的组织形式
算法是完成特定任务的过程
数据类型是指一组值和一组对这些值得操作的集合。

数组

顺序存储相同类型的多个数据

二分法查找

r=2^s s:查找步数 r查找范围 幂函数
s=log2® 已知范围获取需要的次数 对数

算法复杂度使用O(N)函数进行标示 主要是去除常数 看运行时间受数据项个数的影响
在这里插入图片描述

二分查找代码实现

针对有序数组

    public static int myBinarySearch(int[] arr,int value) {
        int low=0;
        int high=arr.length-1;
        while(low<=high) {
            int mid=(low+high)/2;
            if(value==arr[mid]) {
                return mid;
            }
            if(value>arr[mid]) {
                low=mid+1;
            }
            if(value<arr[mid]) {
                high=mid-1;
            }

        }
        return -1;//没有找到返回-1
    }
  public static int rank(int key,int[]a){
        //二分法查找递归实现
       return rank(key,a,0,a.length-1);
    }
    
    public static int rank(int key ,int[]a,int lo,int hi){
        if (lo>hi){
            return  -1;
        }
        int mid=lo+(hi-lo)/2;
        if (key<a[mid]){
            return rank(key,a,lo,mid-1);
        }else{
            return rank(key,a,mid+1,hi);
        }
    }

常见排序

参考地址
https://blog.csdn.net/muranfei/article/details/80923996

栈 对列 优先级对列

栈按照“后进先出”、“先进后出”的原则来存储数据,先插入的数据被压入栈底,后插入的数据在栈顶,读出数据的时候,从栈顶开始依次读出 ;实现方式数组或者链表

对列 先进先出 队列会对两端进行定义,一端叫队头,另外一端就叫队尾。队头只允许删除操作(出队),队尾只允许插入操作(入队)实现方式数组或者链表

优先级对列 按照关键字值进行排序 插入到对应的位置;eg:在线程对列中 优先级高的优先处理

链表

链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。
链表是一个线性结构,但是存储的数据可以是非线性的。链表由一个个子节点构成,每个节点有两个部分:数据域和指针域,数据域就是实际存储数据的,指针域可以有一个和两个,单链表就是单个指针域指向后一个节点,双链表就是节点有两个指针域,分别指向前一个和后一个节点。

链表的核心:

链表的核心就是指针域,通过对指针域的操作实现增加节点删除节点,所谓链表就是形象的表示出一环扣一环,这是链表的优点也是缺点,优点是:插入删除不需要移动所有节点,只需要将待插入的节点的指针域一个指向待插入位置的后一个节点,一个指向前一个节点,不需要初始化容量;

缺点就是搜索的时候必须遍历节点;含有大量的引用,占用的内存空间大。

二叉树

解决有序数组插入慢 链表查找慢问题
树是一种典型的非线性结构,它是由 n(n>0)个有限节点组成的一个具有层次关系的集合。
之所以叫“树”,是因为这种数据结构看起来就像是一个倒挂的树,只不过根在上,叶在下。树形数据结构有以下这些特点:

  1. 每个节点都只有有限个子节点或无子节点;
  2. 没有父节点的节点称为根节点;
  3. 每一个非根节点有且只有一个父节点;
  4. 除了根节点外,每个子节点可以分为多个不相交的子树。

常见数为二叉树 :每个节点只有2个以内的子节点

子节点 父节点 叶节点(没有子节点)

二叉搜索树(二叉查找树) :左子节点不为空且小于节点值 ,右子节点不为空且大于等于节点值
二叉树遍历:如果采用顺序结构来保存二叉树,程序遍历二叉树将非常容易,无需进行任何思考,直接遍历底层数组即可。如果采用链表来保存二叉树的节点,则有以下两种遍历方式:

  • 深度优先遍历:这种遍历算法将先访问到树中最深层次的节点。
  • 广度优先遍历:这种遍历算法将逐层访问每层的节点,先访问根节点,然后访问第二层的节点……以此类推。因此广度优先遍历又被称为按层遍历。

对于深度优先遍历算法而言,他可分为以下三种:

  • (1)先序遍历二叉树

  • (2)中序遍历二叉树

  • (3)后序遍历二叉树

  • 如果L、D、R表示左子树、根、右子树,习惯上总是先遍历左子树,后遍历右子树,根据遍历根节点的顺序不同,上面三种方法可以表示如下:

  • DLR:先序遍历

  • LDR:中序遍历

  • LRD:后序遍历

查找 增加 时间复杂度O(logN) 删除算法复杂
二叉搜索树缺点 对于有序数据产生非平衡树 插入 查找 删除效率低

平衡二叉树:当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树
平衡二叉树本质上也是一颗二叉查找树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于 1。

平衡二叉树(avl树)的难点在于,当删除或者增加节点的情况下,如何通过左旋或者右旋的方式来保持左右平衡。

红黑树详细介绍
avl树一定是平衡的 在插入和删除的时候需要扫描两遍树,一次是向下寻找插入点,一次是向上平衡树,效率不如红黑树高,也不如红黑树常用

哈希表

哈希算法:这类算法接受任意长度的二进制输入值,对输入值做换算(切碎),最终给出固定长度的二进制输出值;

哈希表(Hash Table),也叫散列表,是一种可以通过关键码值(key-value)直接访问的数据结构,它最大的特点就是可以快速实现查找、插入和删除。

数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了树的优点。
哈希函数在哈希表中起着⾮常关键的作⽤,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效,通过哈希函数,数据元素能够被很快的进行定位。
在这里插入图片描述

若关键字为 k,则其值存放在 hash(k) 的存储位置上。由此,不需要遍历就可以直接取得 k 对应的值。

对于任意两个不同的数据块,其哈希值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它哈希值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其哈希值的改动也会非常的大——这正是 Hash 存在的价值!

尽管可能性极小,但仍然会发生,如果哈希冲突了,Java 的 HashMap 会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。

hashmap

  1. HashMap是基于数组来实现哈希表的,数组就好比内存储空间,数组的index就好比内存的地址;
  2. HashMap的每个记录就是一个Entry<K, V>对象,数组中存储的就是这些对象;
  3. HashMap的哈希函数 = 计算出hashCode + 计算出数组的index;
  4. HashMap解决冲突:使用链地址法,每个Entry对象都有一个引用next来指向链表的下一个Entry;
  5. HashMap的装填因子:默认为0.75;

堆中某个节点的值总是不大于或不小于其父节点的值;

堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
时间负责度 O(logN)

在这里插入图片描述
图的遍历: 深度优先搜素(DFS) :得到距离起始点最远的顶点,然后在不能前进的时候返回;
可以用栈进行实现:

  1. 访问一个邻接的未访问的顶点,标记他,并把他放入栈中
  2. 当不能执行第一条的时候 如果栈不空,从栈中弹出一个顶点
  3. 重复执行1 2 如果不能执行则结束

广度优先搜素(BFS):访问起始点的所有邻接点,然后在访问较远的区域,用队列实现

  1. 访问下一个未访问的邻接点,这个订点必须是当前顶点的邻接点,标记他,并插入队列中
  2. 如果1执行完事,则从队列中取一个顶点做为当前顶点,重复执行1 2
  3. 队列为空 不能执行2 则结束

无环有向图 的拓扑排序 将有向图中的顶点以线性方式进行排序:把有向图的各个点按照排序输出 可以生成不同的排序;任务执行的先后顺序
在这里插入图片描述

参考文章Java常见的8种数据结构
runoob.com

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/156411.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号