我ConcurrentSkipListSet在 Java Collection Framework 中找到，它由一个跳过列表备份。但是Java中有跳过列表吗？一套在我的用例中不起作用。我需要一个支持重复的可索引列表。
问问题
35170 次
7 回答
19
这个答案晚了 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);
}
}
于 2014-02-18T23:37:53.547 回答
5
修复了@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);
}
}
于 2017-05-08T06:48:45.290 回答
3
由于您提到了一个既可索引的列表（我假设您希望快速检索）并且需要允许重复，所以我建议您选择带有 LinkedList 或 ArrayList 的自定义 Set。
您需要有一个基本集，例如一个 HashSet，并不断向它添加值。如果您遇到重复项，则该 Set 的值应指向一个 List。因此，您将获得快速检索，当然您将以伪收集方式存储您的对象。
这应该为您提供良好的检索效率。理想情况下，如果您的密钥不重复，您将获得 O(1) 作为检索速度。
于 2011-07-28T19:27:45.590 回答
3
创建 aConcurrentSkipListSet时，会将比较器传递给构造函数。
new ConcurrentSkipListSet<>(new ExampleComparator());
public class ExampleComparator implements Comparator<Event> {//your impl }
您可以创建一个比较器，使您的SkipListSet行为与普通列表一样。
于 2016-05-06T13:30:35.283 回答
2
您可以使用以下代码制作自己的基本跳过列表：
1）使开始和结束represent start and end of skip list。
2）Add the nodes然后assign pointers到下一个based on
if(node is even)
then ,assign a fast lane pointer with next pointer
else
assign only pointer to next node
基本跳过列表的Java 代码（如果需要，您可以添加更多功能）：
public class MyClass {
public static void main(String args[]) {
Skiplist skiplist=new Skiplist();
Node n1=new Node();
Node n2=new Node();
Node n3=new Node();
Node n4=new Node();
Node n5=new Node();
Node n6=new Node();
n1.setData(1);
n2.setData(2);
n3.setData(3);
n4.setData(4);
n5.setData(5);
n6.setData(6);
skiplist.insert(n1);
skiplist.insert(n2);
skiplist.insert(n3);
skiplist.insert(n4);
skiplist.insert(n5);
skiplist.insert(n6);
/*print all nodes*/
skiplist.display();
System.out.println();
/* print only fast lane node*/
skiplist.displayFast();
}
}
class Node{
private int data;
private Node one_next; //contain pointer to next node
private Node two_next; //pointer to node after the very next node
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getOne_next() {
return one_next;
}
public void setOne_next(Node one_next) {
this.one_next = one_next;
}
public Node getTwo_next() {
return two_next;
}
public void setTwo_next(Node two_next) {
this.two_next = two_next;
}
}
class Skiplist{
Node start; //start pointer to skip list
Node head;
Node temp_next; //pointer to store last used fast lane node
Node end; //end of skip list
int length;
public Skiplist(){
start=new Node();
end=new Node();
length=0;
temp_next=start;
}
public void insert(Node node){
/*if skip list is empty */
if(length==0){
start.setOne_next(node);
node.setOne_next(end);
temp_next.setTwo_next(end);
head=start;
length++;
}
else{
length++;
Node temp=start.getOne_next();
Node prev=start;
while(temp != end){
prev=temp;
temp=temp.getOne_next();
}
/*add a fast lane pointer for even no of nodes*/
if(length%2==0){
prev.setOne_next(node);
node.setOne_next(end);
temp_next.setTwo_next(node);
temp_next=node;
node.setTwo_next(end);
}
/*odd no of node will not contain fast lane pointer*/
else{
prev.setOne_next(node);
node.setOne_next(end);
}
}
}
public void display(){
System.out.println("--Simple Traversal--");
Node temp=start.getOne_next();
while(temp != end){
System.out.print(temp.getData()+"=>");
temp=temp.getOne_next();
}
}
public void displayFast(){
System.out.println("--Fast Lane Traversal--");
Node temp=start.getTwo_next();
while(temp !=end){
System.out.print(temp.getData()+"==>");
temp=temp.getTwo_next();
}
}
}
输出：
--简单遍历--
1=>2=>3=>4=>5=>6=>
--快车道穿越--
2==>4==>6==>
于 2015-12-30T21:35:22.257 回答
1
我同意使用来自 apache-collections 的 TreeList 并用来自 Happy Java Libraries https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/的 SortedList 装饰它
于 2012-12-31T11:29:39.037 回答
1
我并不是说这是我自己的实现。我只是不记得我在哪里找到它。如果你知道让我知道，我会更新。这对我来说效果很好：
public class SkipList<T extends Comparable<? super T>> implements Iterable<T> {
Node<T> _head = new Node<>(null, 33);
private final Random rand = new Random();
private int _levels = 1;
private AtomicInteger size = new AtomicInteger(0);
/// <summary>
/// Inserts a value into the skip list.
/// </summary>
public void insert(T value) {
// Determine the level of the new node. Generate a random number R. The
// number of
// 1-bits before we encounter the first 0-bit is the level of the node.
// Since R is
// 32-bit, the level can be at most 32.
int level = 0;
size.incrementAndGet();
for (int R = rand.nextInt(); (R & 1) == 1; R >>= 1) {
level++;
if (level == _levels) {
_levels++;
break;
}
}
// Insert this node into the skip list
Node<T> newNode = new Node<>(value, level + 1);
Node<T> cur = _head;
for (int i = _levels - 1; i >= 0; i--) {
for (; cur.next[i] != null; cur = cur.next[i]) {
if (cur.next[i].getValue().compareTo(value) > 0)
break;
}
if (i <= level) {
newNode.next[i] = cur.next[i];
cur.next[i] = newNode;
}
}
}
/// <summary>
/// Returns whether a particular value already exists in the skip list
/// </summary>
public boolean contains(T value) {
Node<T> cur = _head;
for (int i = _levels - 1; i >= 0; i--) {
for (; cur.next[i] != null; cur = cur.next[i]) {
if (cur.next[i].getValue().compareTo(value) > 0)
break;
if (cur.next[i].getValue().compareTo(value) == 0)
return true;
}
}
return false;
}
/// <summary>
/// Attempts to remove one occurence of a particular value from the skip
/// list. Returns
/// whether the value was found in the skip list.
/// </summary>
public boolean remove(T value) {
Node<T> cur = _head;
boolean found = false;
for (int i = _levels - 1; i >= 0; i--) {
for (; cur.next[i] != null; cur = cur.next[i]) {
if (cur.next[i].getValue().compareTo(value) == 0) {
found = true;
cur.next[i] = cur.next[i].next[i];
break;
}
if (cur.next[i].getValue().compareTo(value) > 0)
break;
}
}
if (found)
size.decrementAndGet();
return found;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
@Override
public Iterator<T> iterator() {
return new SkipListIterator(this, 0);
}
public int size() {
return size.get();
}
public Double[] toArray() {
Double[] a = new Double[size.get()];
int i = 0;
for (T t : this) {
a[i] = (Double) t;
i++;
}
return a;
}
}
class Node<N extends Comparable<? super N>> {
public Node<N>[] next;
public N value;
@SuppressWarnings("unchecked")
public Node(N value, int level) {
this.value = value;
next = new Node[level];
}
public N getValue() {
return value;
}
public Node<N>[] getNext() {
return next;
}
public Node<N> getNext(int level) {
return next[level];
}
public void setNext(Node<N>[] next) {
this.next = next;
}
}
class SkipListIterator<E extends Comparable<E>> implements Iterator<E> {
SkipList<E> list;
Node<E> current;
int level;
public SkipListIterator(SkipList<E> list, int level) {
this.list = list;
this.current = list._head;
this.level = level;
}
public boolean hasNext() {
return current.getNext(level) != null;
}
public E next() {
current = current.getNext(level);
return current.getValue();
}
public void remove() throws UnsupportedOperationException {
throw new UnsupportedOperationException();
}
}
于 2017-02-16T17:46:46.803 回答