Java实现跳表

2024-01-19 22:38
文章标签 java 实现 跳表

本文主要是介绍Java实现跳表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

简介

链表是一种基本的数据结构,而跳表是一种特殊的链表。跳表的每一个节点都有四个指针,上、下、左、右。当进行数据查询时,可以从最顶层开始查找,并可以向下移动,从而提高查询效率。

基本结构

在这里插入图片描述

查找数的基本步骤

  1. 从最左上角的head开始,假如当前数等于目标数,直接返回;假如当前数右指针的数小于目标数,向右移动;假如当前数右指针的数大于目标数,向下移动。
  2. 当down指针为null时,没有找到。

Java节点结构

private class Node<T> {//score不能为负数long score;T value;Node up, down, left, right;public Node(T value) {this.score = -1;this.value = value;}public Node(long score, T value) {this.score = score;this.value = value;}@Overridepublic String toString() {return "Node{" +"score=" + score +", value=" + value +", up=" + up +", down=" + down +", left=" + left +", right=" + right +'}';}
}

Java实现跳表代码

private class SkipList<T> {// 最上层链表的头指针private Node<T> head;// 最上层聊表的尾指针private Node<T> tail;// 跳表的层数private int level;// 插入链表元素的个数private int size;// 用来生成随机数private Random random;public SkipList() {this.head = new Node(Long.MIN_VALUE, null);this.tail = new Node(Long.MAX_VALUE, null);this.level = 1;this.size = 0;this.random = new Random();this.head.right = this.tail;this.tail.left = this.head;}//判断跳表中是否有指定score的节点public boolean contain(long score) {Node help = head;while (help != null) {if (help.score == score) {return true;} else if (help.right.score > score) {help = help.down;} else if (help.right.score <= score) {help = head.right;}}return false;}//返回指定score的元素public Node find(long score) {Node help = head;while (help != null) {if (help.score == score) {return help;} else if (help.right.score > score) {help = help.down;} else if (help.right.score <= score) {help = head.right;}}return null;}//在最底层,找到指定score节点的前面一个节点,public Node findPreNode(long score) {//拿到最底层的head指针,从头开始判断最底部的链表,效率不行//Node help = headToButtom();Node help = head;//开始查询指定score节点的前面一个节点。如果链表中有指定score的节点,则返回相同节点的前面一个节点while (true) {if (score <= help.right.score) {if (help.down == null) return help;else help = help.down;} else {help = help.right;}}}//返回最底层的head指针private Node headToButtom() {Node help = head;while (help.down != null) {help = help.down;}return help;}//判断跳表是否为空public boolean isEmpty() {return size != 0;}//打印最底层的所有节点public void printAll() {Node help = headToButtom();while (help != null) {System.out.println(help);help = help.right;}}//插入节点public void insert(long score, T value) {//找到目标位置的前一个节点Node pre = findPreNode(score);//判断后面节点是否是和要插入节点一样的scoreif (pre.right.score == score) {pre = pre.right;while (pre != null) {pre.value = value;pre = pre.up;}return;}//插入节点Node target = new Node(score, value);target.left = pre;target.right = pre.right;pre.right.left = target;pre.right = target;//当前所属的层级int currLevel = 1;//随机往上沿升while (random.nextDouble() > 0.5) {currLevel++;if (currLevel <= level) {//不用再最上层生成一个新的链表Node upNode = new Node(score, value);Node right = target.right;while (right.up == null) {right = right.right;}right = right.up;Node left = target.left;while (left.up == null) {left = left.left;}left = left.up;upNode.left = left;left.right = upNode;upNode.right = right;right.left = upNode;target = upNode;} else {//需要在最上方生成一个新的链表this.level++;Node upNode = new Node(score, value);Node upHead = new Node(Long.MIN_VALUE, null);Node upTail = new Node(Long.MAX_VALUE, null);upHead.right = upNode;upNode.left = upHead;upTail.left = upNode;upNode.right = upTail;target = upNode;upHead.down = this.head;this.head.up = upHead;this.head = upHead;upTail.down = this.tail;this.tail.up = upTail;this.tail = upTail;}}}//通过分值移除某一个节点public boolean remove(long score) {//先找到最底层的节点Node target = find(score);if (target == null) {return false;} else {while (target != null) {target.left.right = target.right;target.right.left = target.left;target = target.up;}return true;}}//移除某一个节点public void remove(Node node) {while (node != null) {node.left.right = node.right;node.right.left = node.left;node = node.up;}}//范围删除,包括startScore的节点public void rangeRemove(long startScore) {//找到目标位置的前一个节点Node pre = findPreNode(startScore);while (pre.right.score < Long.MAX_VALUE) {remove(pre.right);}}//范围删除,包括startScore的节点,包括endScore的节点public void rangeRemove(long startScore, long endScore) {//找到目标位置的前一个节点Node pre = findPreNode(startScore);while (pre.right.score <= endScore) {remove(pre.right);}}//包括startScore之后的节点数目public int getNodeCount(long startScore) {int result = 0;//找到目标位置的前一个节点Node pre = findPreNode(startScore);while (pre.right.score < Long.MAX_VALUE) {result++;pre = pre.right;}return result;}//获取包括startScore的节点,包括endScore的节点的节点数目public int getNodeCount(long startScore, long endScore) {int result = 0;//找到目标位置的前一个节点Node pre = findPreNode(startScore);while (pre.right.score <= endScore) {result++;pre = pre.right;}return result;}private class Node<T> {//score不能为负数long score;T value;Node up, down, left, right;public Node(T value) {this.score = -1;this.value = value;}public Node(long score, T value) {this.score = score;this.value = value;}@Overridepublic String toString() {return "Node{" +"score=" + score +", value=" + value +", up=" + up +", down=" + down +", left=" + left +", right=" + right +'}';}}}

这篇关于Java实现跳表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/623922

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断