江苏龙网

  1. 主页 > 生活百科 > >

跳表在Java中的实现

跳表

跳表是一种数据结构，用于借助连接到元素子序列的链表层次结构来存储元素的排序列表 。跳表允许以有效的方式处理项目查找 。跳表是一种概率数据结构，这意味着它跳过整个列表中的几个元素，因此称为跳表 。我们可以将跳表作为链表的扩展版本 。与链表允许插入、删除和搜索元素的方式类似，跳表也允许搜索元素、从列表中删除元素和插入元素 。它将包含一个基本列表，其中包含一组元素，这些元素将维护后续元素的链接层次结构 。
语法：跳表没有特定的语法，但它有一个算法 。在研究算法之前，我们需要检查基本跳表操作的类型 。

  1. 插入操作：在跳表中，用于在特定情况下向特定位置添加新节点
  2. 搜索操作：在跳表中，用于搜索特定节点
  3. 删除操作：在跳表中，用于删除特定情况下的节点
让我们看看跳表是如何以算法的方式工作的 。
插入算法：步骤1：确定节点级别，因为列表中的每个元素都有节点表示，并且在插入列表时随机选择节点的级别
步骤2：根据以下步骤确定节点的级别
步骤3：找到最大级别是跳表中级别计数的上限，该上限由 L（N）=logp/2N 确定 。这确保了随机级别将大于最大级别
步骤4：插入从最高级别开始，并比较当前节点的下一个节点
【跳表在Java中的实现】步骤5：如果“下一个节点关键点”小于“插入的关键点”，则可以使用相同级别继续前进
步骤6：如果next node key大于inserted key，那么我们需要存储一个指向当前节点I的指针，并向下移动一级继续搜索 。
搜索算法：步骤1：因为搜索元素非常类似于搜索一个点以在跳表中插入元素 。
步骤2：如果下一个节点键小于搜索键，那么我们可以在同一级别上前进
步骤3：如果next node key大于inserted key，那么我们需要存储一个指向当前节点I的指针，并向下移动一级继续搜索 。
步骤4：在最低级别，如果最右侧元素的下一个元素具有与搜索键相等的键，那么我们已经找到了键，否则这是一个失败 。
删除算法：步骤1：要删除任何元素，比如k，首先我们需要使用搜索算法在跳表中定位该元素 。
第2步：一旦我们使用搜索算法找到了元素，指针重新排列将从列表中删除该元素，就像我们在单个链接列表中所做的那样 。
步骤3：我们需要从跳过列表的最低级别开始，重新排列I not元素k旁边的元素 。
步骤4：删除元素后，可能会出现没有元素的级别的情况，因此我们需要通过减少跳表级别来删除这些级别 。
示例：JAVA中的跳表
import java.util.Iterator;import java.util.Random;import java.util.NoSuchElementException;public class SkipListJava<K extends Comparable<K>, V> implements Iterable<K> {private int listsize;private double pb;protected static final Random randomGen = new Random();protected static final double DEFAULT_PB = 0.5;private NodeKeyValue<K, V> head;public SkipListJava() {this(DEFAULT_PB);}public SkipListJava(double pb) {this.head = new NodeKeyValue<K, V>(null, null, 0);this.pb = pb;this.listsize = 0;}public V get(K key) {checkKeyValid(key);NodeKeyValue<K, V> listnode = findNode(key);if (listnode.getKey().compareTo(key) == 0)return listnode.getValue();elsereturn null;}public void add(K key, V value) {checkKeyValid(key);NodeKeyValue<K, V> listnode = findNode(key);if (listnode.getKey() != null && listnode.getKey().compareTo(key) == 0) {listnode.setValue(value);return;}NodeKeyValue<K, V> newlistNode = new NodeKeyValue<K, V>(key, value, listnode.getLevel());horizontalInsertList(listnode, newlistNode);int curLevel = listnode.getLevel();int headlistLevel = head.getLevel();while (isBuildLevel()) {if (curLevel >= headlistLevel) {NodeKeyValue<K, V> newHeadEle = new NodeKeyValue<K, V>(null, null, headlistLevel + 1);verticalLink(newHeadEle, head);head = newHeadEle;headlistLevel = head.getLevel();}while (listnode.getUp() == null) {listnode = listnode.getPrevious();}listnode = listnode.getUp();NodeKeyValue<K, V> tmp = new NodeKeyValue<K, V>(key, value, listnode.getLevel());horizontalInsertList(listnode, tmp);verticalLink(tmp, newlistNode);newlistNode = tmp;curLevel++;}listsize++;}public void remove(K key) {checkKeyValid(key);NodeKeyValue<K, V> listnode = findNode(key);if (listnode == null || listnode.getKey().compareTo(key) != 0)throw new NoSuchElementException("Key does not exist!");while (listnode.getDownList() != null)listnode = listnode.getDownList();NodeKeyValue<K, V> previous = null;NodeKeyValue<K, V> next = null;for (; listnode != null; listnode = listnode.getUp()) {previous = listnode.getPrevious();next = listnode.getNext();if (previous != null)previous.setNext(next);if (next != null)next.setPreviousVal(previous);}while (head.getNext() == null && head.getDownList() != null) {head = head.getDownList();head.setUp(null);}listsize--;}public boolean contains(K key) {return get(key) != null;}public int listsize() {return listsize;}public boolean empty() {return listsize == 0;}protected NodeKeyValue<K, V> findNode(K key) {NodeKeyValue<K, V> listnode = head;NodeKeyValue<K, V> next = null;NodeKeyValue<K, V> down = null;K nodeKey = null;while (true) {next = listnode.getNext();while (next != null && lessThanEqual(next.getKey(), key)) {listnode = next;next = listnode.getNext();}nodeKey = listnode.getKey();if (nodeKey != null && nodeKey.compareTo(key) == 0)break;down = listnode.getDownList();if (down != null) {listnode = down;} else {break;}}return listnode;}protected void checkKeyValid(K key) {if (key == null)throw new IllegalArgumentException("Key must be not null!");}protected boolean lessThanEqual(K a, K b) {return a.compareTo(b) <= 0;}protected boolean isBuildLevel() {return randomGen.nextDouble() < pb;}protected void horizontalInsertList(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {b.setPreviousVal(a);b.setNext(a.getNext());if (a.getNext() != null)a.getNext().setPreviousVal(b);a.setNext(b);}protected void verticalLink(NodeKeyValue<K, V> a, NodeKeyValue<K, V> b) {a.setDown(b);b.setUp(a);}@Overridepublic String toString() {StringBuilder stringbuild = new StringBuilder();NodeKeyValue<K, V> listnode = head;while (listnode.getDownList() != null)listnode = listnode.getDownList();while (listnode.getPrevious() != null)listnode = listnode.getPrevious();if (listnode.getNext() != null)listnode = listnode.getNext();while (listnode != null) {stringbuild.Append(listnode.toString()).append("n");listnode = listnode.getNext();}return stringbuild.toString();}@Overridepublic Iterator<K> iterator() {return new SkipListIterator<K, V>(head);}protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {private NodeKeyValue<K, V> listnode;public SkipListIterator(NodeKeyValue<K, V> listnode) {while (listnode.getDownList() != null)listnode = listnode.getDownList();while (listnode.getPrevious() != null)listnode = listnode.getPrevious();if (listnode.getNext() != null)listnode = listnode.getNext();this.listnode = listnode;}@Overridepublic boolean hasNext() {return this.listnode != null;}@Overridepublic K next() {K result = listnode.getKey();listnode = listnode.getNext();return result;}@Overridepublic void remove() {throw new UnsupportedOperationException();}}protected static class NodeKeyValue<K extends Comparable<K>, V> {private K key;private V value;private int skiplevel;private NodeKeyValue<K, V> up, down, next, previous;public NodeKeyValue(K key, V value, int skiplevel) {this.key = key;this.value = https://www.isolves.com/it/cxkf/yy/JAVA/2022-07-08/value;this.skiplevel = skiplevel;}@Overridepublic String toString() {StringBuilder stringbuild = new StringBuilder();stringbuild.append("Node[").append("key:");if (this.key == null)stringbuild.append("None");elsestringbuild.append(this.key.toString());stringbuild.append(", value:");if (this.value == null)stringbuild.append("None");elsestringbuild.append(this.value.toString());stringbuild.append("]");return stringbuild.toString();}public K getKey() {return key;}public void setKey(K key) {this.key = key;}public V getValue() {return value;}public void setValue(V value) {this.value = value;}public int getLevel() {return skiplevel;}public void setLevel(int skiplevel) {this.skiplevel = skiplevel;}public NodeKeyValue


推荐阅读


上一篇：分享一个日常使用的一段shell脚本

下一篇：巧用批处理工具分析monkey日志