Java是否有跳过列表实现
2022-09-03 00:09:19
我在Java Collection Framework中找到了ConcurrentSkipListSet，它备份了一个跳过列表。但是Java中有跳过列表吗？一个集合在我的用例中不起作用。我需要一个支持重复项的可索引列表。
答案 1
这个答案已经晚了3年，但我希望它能对那些想要从这一刻起的Java跳过列表的人有用:)
此解决方案允许重复，如您所愿。我大致遵循这里的指南 http://igoro.com/archive/skip-lists-are-fascinating，所以复杂性与此相似，除了删除成本O（nlogn） - 因为我没有打扰使用双链接节点，我想这样做会将删除降低到O（logn）。
代码包括：接口、实现接口的跳过列表和节点类。它也是通用的。
您可以调整参数 LEVELS 以提高性能，但请记住时空权衡。
import java.util.Random;
interface SkippableList<T extends Comparable<? super T>> {
int LEVELS = 5;
boolean delete(T target);
void print();
void insert(T data);
SkipNode<T> search(T data);
}
public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {
public static void main(String[] args) {
SkipList<Integer> sl = new SkipList<>();
int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
for (int i : data) {
sl.insert(i);
}
sl.print();
sl.search(4);
sl.delete(9);
sl.print();
sl.insert(69);
sl.print();
sl.search(69);
}
private final SkipNode<T> head = new SkipNode<>(null);
private final Random rand = new Random();
@Override
public void insert(T data) {
SkipNode<T> SkipNode = new SkipNode<>(data);
for (int i = 0; i < LEVELS; i++) {
if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i)
insert(SkipNode, i);
}
}
}
@Override
public boolean delete(T target) {
System.out.println("Deleting " + target.toString());
SkipNode<T> victim = search(target, false);
if (victim == null) return false;
victim.data = null;
for (int i = 0; i < LEVELS; i++) {
head.refreshAfterDelete(i);
}
System.out.println();
return true;
}
@Override
public SkipNode<T> search(T data) {
return search(data, true);
}
@Override
public void print() {
for (int i = 0; i < LEVELS; i++) {
head.print(i);
}
System.out.println();
}
private void insert(SkipNode<T> SkipNode, int level) {
head.insert(SkipNode, level);
}
private SkipNode<T> search(T data, boolean print) {
SkipNode<T> result = null;
for (int i = LEVELS-1; i >= 0; i--) {
if ((result = head.search(data, i, print)) != null) {
if (print) {
System.out.println("Found " + data.toString() + " at level " + i + ", so stoppped" );
System.out.println();
}
break;
}
}
return result;
}
}
class SkipNode<N extends Comparable<? super N>> {
N data;
@SuppressWarnings("unchecked")
SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];
SkipNode(N data) {
this.data = data;
}
void refreshAfterDelete(int level) {
SkipNode<N> current = this.getNext(level);
while (current != null && current.getNext(level) != null) {
if (current.getNext(level).data == null) {
SkipNode<N> successor = current.getNext(level).getNext(level);
current.setNext(successor, level);
return;
}
current = current.getNext(level);
}
}
void setNext(SkipNode<N> next, int level) {
this.next[level] = next;
}
SkipNode<N> getNext(int level) {
return this.next[level];
}
SkipNode<N> search(N data, int level, boolean print) {
if (print) {
System.out.print("Searching for: " + data + " at ");
print(level);
}
SkipNode<N> result = null;
SkipNode<N> current = this.getNext(level);
while (current != null && current.data.compareTo(data) < 1) {
if (current.data.equals(data)) {
result = current;
break;
}
current = current.getNext(level);
}
return result;
}
void insert(SkipNode<N> SkipNode, int level) {
SkipNode<N> current = this.getNext(level);
if (current == null) {
this.setNext(SkipNode, level);
return;
}
if (SkipNode.data.compareTo(current.data) < 1) {
this.setNext(SkipNode, level);
SkipNode.setNext(current, level);
return;
}
while (current.getNext(level) != null && current.data.compareTo(SkipNode.data) < 1 &&
current.getNext(level).data.compareTo(SkipNode.data) < 1) {
current = current.getNext(level);
}
SkipNode<N> successor = current.getNext(level);
current.setNext(SkipNode, level);
SkipNode.setNext(successor, level);
}
void print(int level) {
System.out.print("level " + level + ": [");
int length = 0;
SkipNode<N> current = this.getNext(level);
while (current != null) {
length++;
System.out.print(current.data.toString() + " ");
current = current.getNext(level);
}
System.out.println("], length: " + length);
}
}
答案 2
修复了@PoweredByRice提供的实现中的错误。它为删除的节点是第一个节点的情况抛出 NPE。其他更新包括重命名的变量名称和反向打印跳过列表的顺序。
import java.util.Random;
interface SkippableList<T extends Comparable<? super T>> {
int LEVELS = 5;
boolean delete(T target);
void print();
void insert(T data);
SkipNode<T> search(T data);
}
class SkipNode<N extends Comparable<? super N>> {
N data;
@SuppressWarnings("unchecked")
SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];
SkipNode(N data) {
this.data = data;
}
void refreshAfterDelete(int level) {
SkipNode<N> current = this;
while (current != null && current.getNext(level) != null) {
if (current.getNext(level).data == null) {
SkipNode<N> successor = current.getNext(level).getNext(level);
current.setNext(successor, level);
return;
}
current = current.getNext(level);
}
}
void setNext(SkipNode<N> next, int level) {
this.next[level] = next;
}
SkipNode<N> getNext(int level) {
return this.next[level];
}
SkipNode<N> search(N data, int level, boolean print) {
if (print) {
System.out.print("Searching for: " + data + " at ");
print(level);
}
SkipNode<N> result = null;
SkipNode<N> current = this.getNext(level);
while (current != null && current.data.compareTo(data) < 1) {
if (current.data.equals(data)) {
result = current;
break;
}
current = current.getNext(level);
}
return result;
}
void insert(SkipNode<N> skipNode, int level) {
SkipNode<N> current = this.getNext(level);
if (current == null) {
this.setNext(skipNode, level);
return;
}
if (skipNode.data.compareTo(current.data) < 1) {
this.setNext(skipNode, level);
skipNode.setNext(current, level);
return;
}
while (current.getNext(level) != null && current.data.compareTo(skipNode.data) < 1 &&
current.getNext(level).data.compareTo(skipNode.data) < 1) {
current = current.getNext(level);
}
SkipNode<N> successor = current.getNext(level);
current.setNext(skipNode, level);
skipNode.setNext(successor, level);
}
void print(int level) {
System.out.print("level " + level + ": [ ");
int length = 0;
SkipNode<N> current = this.getNext(level);
while (current != null) {
length++;
System.out.print(current.data + " ");
current = current.getNext(level);
}
System.out.println("], length: " + length);
}
}
public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {
private final SkipNode<T> head = new SkipNode<>(null);
private final Random rand = new Random();
@Override
public void insert(T data) {
SkipNode<T> skipNode = new SkipNode<>(data);
for (int i = 0; i < LEVELS; i++) {
if (rand.nextInt((int) Math.pow(2, i)) == 0) {
//insert with prob = 1/(2^i)
insert(skipNode, i);
}
}
}
@Override
public boolean delete(T target) {
System.out.println("Deleting " + target);
SkipNode<T> victim = search(target, true);
if (victim == null) return false;
victim.data = null;
for (int i = 0; i < LEVELS; i++) {
head.refreshAfterDelete(i);
}
System.out.println("deleted...");
return true;
}
@Override
public SkipNode<T> search(T data) {
return search(data, true);
}
@Override
public void print() {
for (int i = LEVELS-1; i >= 0 ; i--) {
head.print(i);
}
System.out.println();
}
private void insert(SkipNode<T> SkipNode, int level) {
head.insert(SkipNode, level);
}
private SkipNode<T> search(T data, boolean print) {
SkipNode<T> result = null;
for (int i = LEVELS-1; i >= 0; i--) {
if ((result = head.search(data, i, print)) != null) {
if (print) {
System.out.println("Found " + data.toString() + " at level " + i + ", so stopped" );
System.out.println();
}
break;
}
}
return result;
}
public static void main(String[] args) {
SkipList<Integer> sl = new SkipList<>();
int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
for (int i : data) {
sl.insert(i);
}
sl.print();
sl.search(4);
sl.delete(4);
System.out.println("Inserting 10");
sl.insert(10);
sl.print();
sl.search(10);
}
}
推荐
-
如何使用树找到最长的公共子字符串？ 根据wiki，最长的常见子字符串问题可以使用后缀树来解决。来自： 一组字符串的最长公共子字符串可以通过为字符串构建一个广义的后缀树，然后从其下方子树中的所有字符串中找到具有叶
-
在没有数据库的情况下查询 Java 对象 注意：小问题很长。我要给一个赏金，以获得最好的答案。 我试图做的是在对象上查询。以下是详细信息。我有一个名为 .所以我解析了它并保留在列表中 感谢您的任何帮助。赏金将在2天后
-
我应该使用什么数据结构来创建自己的“BigInteger”类？ 作为可选作业，我正在考虑编写自己的BigInteger类的实现，在那里我将提供自己的加法，减法，乘法等方法。 这将适用于任意长的整数，甚至数百位数字。 在对这些数字进行数学运算时，逐位
-
Java Collections Framework中常用方法（大小）的意外复杂性？ 最近，我对一些Java集合没有方法size（）的恒定时间操作这一事实感到惊讶。 虽然我了解到集合的并发实现做出了一些妥协，作为并发收益的权衡（在ConcurrentLinkedQueue，ConcurrentSkipListSet，LinkedTra
-
性能方面，番石榴图书馆有多好？[已关闭] 库，并在其中发现了许多好的，可用的数据结构。 如果还有其他人使用它，那么您能否提供有关它在与大型数据集一起使用时的性能的反馈？基本上，我正在寻找BigO表示法用于其操作
