首页 > 资讯 > 后端开发 > Python >Java数据结构之实现跳表

864

分享到

Java数据结构之实现跳表

2024-04-02 19:04:59 864人浏览薄情痞子

Python 官方文档：入门教程 => 点击学习

摘要

目录一、跳表的定义二、跳表搜索三、插入元素四、删除元素五、完整代码一、跳表的定义跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log

一、跳表的定义

跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

SkipList(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。SkipList让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

在Java的api中已经有了实现：分别是:

ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap) ；
ConcurrentSkipListSet(在功能上对应HashSet).
确切来说，SkipList更像Java中的TreeMap，TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。

SkipList的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

图示：

在这里插入图片描述

二、跳表搜索

在这里插入图片描述

例子：查找元素 117

(1) 比较 21，比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85，比 85 大，从后面找

(5) 比较 117，等于 117，找到了节点。



    private node findPreNode(int val){
        Node first = head.getFirst();//从最上层的头节点开始搜索
        while (first!=null){
            if(first.data < val && first.next.data > val){
                if(first.down == null){break;}
                first = first.down;//往下搜索
            }else if(first.data < val && first.next.data < val){
                first = first.next;//往右搜索
            }else if(first.data < val && first.next.data == val){
                return first;
            }
        }
        return null;
    }

三、插入元素

先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）然后在 Level 1 … Level K 各个层的链表都插入元素。



    private int getLeavel(){
        int k = 0;
        while(rd.nextInt(2) == 1){
            k ++;
        }
        return k;
    }

例子：插入 119， K = 2

在这里插入图片描述

如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4

在这里插入图片描述

四、删除元素

从上往下删除

在这里插入图片描述



    boolean delete(int val){
        Node lindPre = findPreNode(val);//找到待删除元素的最上层的前一个节点
        if(lindPre == null){
            return false;
        }
        while (true){
            lindPre.next = lindPre.next.next;
            lindPre = lindPre.down;//往下遍历，直到最底下一层
            if(lindPre==null){break;}//跳出循环
            //找到待删除元素所在行的前一个节点
            while (lindPre.next.data != val){
                lindPre = lindPre.next;
            }
        }
        size--;
        return true;
    }

五、完整代码


package com.longstudy.alGorithm;
import java.util.LinkedList;
import java.util.Random;


public class SkipList {

    //使用头插法插入新节点
    LinkedList<Node> head;//每一行的头结点，相当于跳表的第一列， 默认设置为 Integer.MIN_VALUE
    LinkedList<Node> tail;//每一行大最后一个节点，相当与跳表的最后一列  Integer.MAX_VALUE
    Random rd ;//用于生成随机数数
    int hight=-1;//当前跳表的层数，hight从0开始,初始值为-1，
    int size;//所有的节点数

    public SkipList(){
        this.head = new LinkedList<>();
        this.tail = new LinkedList<>();
        this.rd = new Random();
    }

    public static void main(String[] args) {
        SkipList sl = new SkipList();
        int[] arr = new int[500];
        for (int i = 0; i < 500; i++) {
            arr[i] = (int)(Math.random()*600);
        }
        sl.arrayToSkipList(arr);
        sl.showSkipList();
        System.out.println(sl.find(100));
        System.out.println(sl.find(50));
        System.out.println(sl.find(99));
        System.out.println("清空跳表");
        sl.clear();
        sl.showSkipList();

    }
    
    private class Node{
        int data;//存放数据
        Node next;//指向右边节点
        Node down; //指向下面节点
        int level;//当前所在的层
        public Node(){}
        public Node(int data,int level){
            this.data = data;
            this.level = level;
        }
        public Node(int data,int level,Node next,Node down){
            this.data = data;
            this.level = level;
            this.next = next;
            this.down =down;
        }
    }

    
    boolean add(int val){
        int k = getLeavel();//获得层数
        //层数比当前大的时候，增加新的层
        if(k>hight){
            int i = k-hight;
            for (int j = 1; j <=i; j++) {
                //新增头节点和尾节点
                Node h = new Node(Integer.MIN_VALUE,hight+j);
                if(head.size()>0){
                    h.down = head.getFirst();//往下指
                }
                Node t = new Node(Integer.MAX_VALUE,hight+j);//尾
                if(tail.size()>0){
                    t.down = tail.getFirst();
                }
                h.next=t;//头指向尾
                tail.addFirst(t);
                head.addFirst(h);
            }
            hight =k;//修改当前的跳表层数
        }
        return addFromK(val,k);//从第k层添加元素
    }

    
    boolean addFromK(int val,int k){
        Node preNewNode = new Node(val,k);
        Node preLine = head.get(hight-k);//获取新增节点所在层的头节点
        while (preLine != null){
            while (preLine.next.data < val){//往右搜索
                preLine = preLine.next;
            }
            preNewNode.next = preLine.next;
            preLine.next = preNewNode;
            //如果不是第一层，则建立下一层的新节点
            if (preNewNode.level>0){
                Node newNode = new  Node(val,preNewNode.level-1);
                preNewNode.down = newNode;//往下指向新节点
                preNewNode = newNode;
            }
            //往下层建立新节点
            preLine = preLine.down;
        }
        size++;//跳表中的元素数量加一
        return true;
    }


    
    private int getLeavel(){
        int k = 0;
        while(rd.nextInt(2) == 1){
            k ++;
        }
        return k;
    }

    
    boolean delete(int val){
        Node lindPre = findPreNode(val);//找到待删除元素的最上层的前一个节点
        if(lindPre == null){
            return false;
        }
        while (true){
            lindPre.next = lindPre.next.next;
            lindPre = lindPre.down;//往下遍历，直到最底下一层
            if(lindPre==null){break;}//跳出循环
            //找到待删除元素所在行的前一个节点
            while (lindPre.next.data != val){
                lindPre = lindPre.next;
            }
        }
        size--;
        return true;
    }

    
    void clear(){
        this.hight=-1;
        this.size =0;
        this.head = null;
        this.tail = null;

    }

    
    boolean find(int val){
       return findPreNode(val) !=null;
    }

    
    private Node findPreNode(int val){
        Node first = head.getFirst();//从最上层的头节点开始搜索
        while (first!=null){
            if(first.data < val && first.next.data > val){
                if(first.down == null){break;}
                first = first.down;//往下搜索
            }else if(first.data < val && first.next.data < val){
                first = first.next;//往右搜索
            }else if(first.data < val && first.next.data == val){
                return first;
            }
        }
        return null;
    }

    
    void arrayToSkipList(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            add(arr[i]);
        }
    }

    
    void showSkipList(){
        System.out.println("元素个数为："+size);
        //从上往下逐层打印
        for (int i = 0; i <=hight ; i++) {
            Node linFirst = head.get(i);
            System.out.print("第"+linFirst.level+"层:\t"+"head ->\t");
            linFirst = linFirst.next;//跳过第一列的元素
            while (linFirst != null){
                if(linFirst.next != null){
                    System.out.print(""+linFirst.data +'\t'+"->\t");//+ " height:"+linFirst.level
                }else {
                    System.out.println("tail");
                }
                linFirst = linFirst.next;
            }
            System.out.println();
        }
    }

}

到此这篇关于Java数据结构之实现跳表的文章就介绍到这了,更多相关Java跳表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档:

--结束END--

本文标题: Java数据结构之实现跳表

本文链接: https://lsjlt.com/news/126663.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

回答

如何调试操作系统的错误？
操作系统

2023-11-15发布

回答

操作系统中的I/O系统是如何实现的？
操作系统

2023-11-15发布

回答

如何实现操作系统的内存管理？
操作系统

2023-11-15发布

回答

什么是虚拟内存，它对操作系统有什么影响？
操作系统

2023-11-15发布

回答

ASP中的MVC架构和WebForms架构有什么区别和使用场景？
ASP.NET

2023-11-15发布

回答

ASP中的数据验证和数据校验有什么不同？
ASP.NET

2023-11-15发布

回答

ASP中的ADO对象和DAO对象有什么区别和使用方法？
ASP.NET

2023-11-15发布

回答

Node.js中的包管理器NPM是什么？如何使用它进行依赖管理？
node.js

2023-11-15发布

回答

Vue.js中的动态组件是什么？如何使用它来动态渲染组件？
VUE

2023-11-15发布

回答

如何使用Vue.js实现懒加载和预加载？
VUE

2023-11-15发布

Java数据结构之实现跳表

目录

一、跳表的定义

二、跳表搜索

三、插入元素

四、删除元素

五、完整代码

Java数据结构之实现跳表

golang怎么实现跳表数据结构

Java数据结构之顺序表的实现

Java数据结构之LinkedList从链表到实现

Java数据结构之双向链表的实现

Redis数据结构之跳跃表是什么

Java数据结构之ArrayList从顺序表到实现

Java数据结构之双向链表如何实现

用Python实现数据结构之链表

Python数据结构与算法之跳表详解

Java数据结构之链表的概念及结构

Java数据结构之链表详解

Java数据结构之顺序表篇

C++数据结构之单链表的实现

数据结构TypeScript之链表实现详解

C++数据结构之哈希表的实现

Java数据结构之快速幂的实现

Java数据结构之KMP算法的实现

Java数据结构之并查集的实现

数据结构（Java实现）LinkedList与链表（上）

python分析数据的方法是什么

如何使用Python实现抽奖小程序

python copy函数的作用是什么

python ffmpeg模块怎么安装和使用

python进程池创建队列的方法是什么

python无法运行文件的原因有哪些

python can't open file报错怎么解决

python keyerror错误怎么解决

python字符串处理与应用的方法有哪些

python全局变量如何定义