Skip to content

Instantly share code, notes, and snippets.

@infynyxx
Created April 13, 2017 15:38
Show Gist options
  • Save infynyxx/32c5149a7e29fa0024de21cbcfa509c2 to your computer and use it in GitHub Desktop.
Save infynyxx/32c5149a7e29fa0024de21cbcfa509c2 to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class SkipList {
private static class SkipListNode {
private final int value;
private final SkipListNode[] next;
public SkipListNode(int value, int level) {
this.value = value;
this.next = new SkipListNode[level];
}
}
private final Random random = new Random();
private SkipListNode head = new SkipListNode(0, 33);
private int levels = 1;
void insert(int value) {
if (contains(value)) {
return;
}
int level = 0;
for (int r = random.nextInt(); (r & 1) == 1; r >>= 1) {
level++;
if (level == levels) {
levels++;
break;
}
}
SkipListNode current = head;
SkipListNode newNode = new SkipListNode(value, level + 1);
for (int i = levels - 1; i >= 0; i--) {
while (current.next[i] != null) {
if (current.next[i].value > value) {
break;
}
current = current.next[i];
}
if (i <= level) {
newNode.next[i] = current.next[i];
current.next[i] = newNode;
}
}
}
boolean contains(int value) {
SkipListNode current = head;
for (int i = levels - 1; i >= 0; i--) {
while (current.next[i] != null) {
if (current.next[i].value == value) {
return true;
}
current = current.next[i];
}
}
return false;
}
boolean remove(int value) {
SkipListNode current = head;
boolean found = false;
for (int i = levels - 1; i >= 0; i--) {
while (current.next[i] != null) {
if (current.next[i].value == value) {
current.next[i] = current.next[i].next[i];
found = true;
break;
}
current = current.next[i];
}
}
return found;
}
List<Integer> list() {
SkipListNode current = head.next[0];
List<Integer> items = new ArrayList<>();
while (current != null) {
items.add(current.value);
current = current.next[0];
}
return items;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment