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

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

第一张

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

数组

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

二分法查找

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）个有限节点组成的一个具有层次关系的集合。
之所以叫“树”，是因为这种数据结构看起来就像是一个倒挂的树，只不过根在上，叶在下。树形数据结构有以下这些特点：

每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树。

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

子节点父节点叶节点（没有子节点）

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

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

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

(1)先序遍历二叉树
(2)中序遍历二叉树
(3)后序遍历二叉树
如果L、D、R表示左子树、根、右子树，习惯上总是先遍历左子树，后遍历右子树，根据遍历根节点的顺序不同，上面三种方法可以表示如下：
DLR:先序遍历
LDR:中序遍历
LRD:后序遍历

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

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

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

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

哈希表

哈希算法：这类算法接受任意长度的二进制输入值，对输入值做换算（切碎），最终给出固定长度的二进制输出值；

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

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