Java ont une benne de la mise en œuvre de la liste

Cette réponse est 3 ans de retard mais j'espère que ce sera utile pour ceux qui veulent un Java sauter de la liste à partir de ce moment 🙂

Cette solution permet de doublons que vous avez demandé. J'ai suivi à peu près le guide ici http://igoro.com/archive/skip-lists-are-fascinating, de sorte que les difficultés sont de semblable à cela, sauf supprimer coûts O(nlogn) - que je n'ai pas pris la peine à l'aide de double liaison nœuds, j'imagine que cela permettrait de ramener supprimer en bas à O(logn).

Code se compose de: une interface, le saut de la liste de la mise en œuvre de l'interface et la classe de nœud. Il est également au générique.

Vous pouvez régler le paramètre NIVEAUX pour la performance, mais n'oubliez pas l'espace-temps de compromis.

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);
}
}

OriginalL'auteur PoweredByRice

J'approuve à utiliser la liste arborescente de apache-collections et de la décorer avec SortedList de Heureux Bibliothèques Java
https://sourceforge.net/p/happy-guys/wiki/Sorted%20List/

OriginalL'auteur thinker

Je ne prétends pas que c'est ma propre mise en œuvre. J'ai juste ne me souviens pas où je l'ai trouvé. Si vous connaissez faites le moi savoir et je vais mettre à jour. Ce travail a été très bien pour moi:

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();
}
}

OriginalL'auteur idipous