Implement a skip list class in Java. Use randomization to promote nodes to highe
ID: 3844139 • Letter: I
Question
Implement a skip list class in Java.
Use randomization to promote nodes to higher levels. Implement the following methods: skipInsert(k,v) – to insert in a skip list entry with key k and value v;
skipRemove(k) – to remove position corresponding to key k from all levels in the skipList;
skipSearch(k) – to search for key k in the skip list (returns position corresponding to key k in the bottom list,
1 or null if k is not found). The java file should include the main method that creates a
skip list from the hardcoded sequence of 10 integers and prints out the resulting list to
stdout.
Please do not post an answer if you cannot fully answer the question and the code must compile and run. You must implement the main method so that the code can be executed.
Use the folllowing algorithms to implement the functions
Algorithm SkipSearch(k):
Input: A search key k
Output: Position p in the bottom list S0 with the largest key having key(p) k
p = s {begin at start position}
while below(p) 6= null do
p = below(p) {drop down}
while k key(next(p)) do
p = next(p) {scan forward}
return p
---------------------------------------------------------
Algorithm SkipInsert(k, v):
Input: Key k and value v
Output: Topmost position of the entry inserted in the skip list
p = SkipSearch(k) {position in bottom list with largest key less than k}
q = null {current node of new entry’s tower}
i = 1 {current height of new entry’s tower}
repeat
i = i +1 {increase height of new entry’s tower}
if i h then
h = h +1 {add a new level to the skip list}
t = next(s)
s = insertAfterAbove(null, s, (,null)) {grow leftmost tower}
insertAfterAbove(s, t, (+,null)) {grow rightmost tower}
q = insertAfterAbove(p, q, (k,v)) {add node to new entry’s tower}
while above(p) == null do
p = prev(p) {scan backward}
p = above(p) {jump up to higher level}
until coinFlip( ) == tails
n = n +1
return q {top node of new entry’s tower}
--------------------------------------------------------------
To perform the map operation remove(k), begin by executing method SkipSearch(k). If
the returned position p stores an entry with key different from k, return null.
Otherwise, remove p and all the positions above p, which are easily accessed
by using above operations to climb up the tower of this entry in S starting at position
p. While removing levels of the tower, reestablish links between the horizontal
neighbors of each removed position.
Explanation / Answer
Main.java
________________________________________________________________
public class Main {
public static void main(String[] args) {
// Initialize skip list
SkipList<Integer> skipList = new SkipList<>();
// Insert integer value
skipList.add(10);
// Find index
int index = skipList.indexOf(10);
// Remove item by value
skipList.remove(20);
// Remove item by index
skipList.removeAt(0);
// Find item by index
skipList.findByIndex(0);
// Height of skip list
skipList.getHeight();
// Size of skip list
int size = skipList.getSize();
// Clear skip list
skipList.clear();
}
}
_____________________________________________________________
SkipList.java
public class SkipList<Type extends Comparable<Type>> extends AbstractSortedSet<Type> {
private Node<Type> head;
private int size;
private int maxLevel;
public SkipList() {
// Initialize values
size = 0;
maxLevel = 0;
head = new Node<Type>(null);
head.addNextNode(null);
}
public Node<Type> getHead() {
return head;
}
public int getSize() {
return size;
}
public int getHeight() {
return maxLevel;
}
public boolean add(Type element) {
// Return false if the list already includes this element
if (contains(element)) {
return false;
}
// Increment size
size++;
// Generate random number
int level = 0;
while (Math.random() < 0.5) {
level++;
}
while (level > maxLevel) {
head.addNextNode(null);
maxLevel++;
}
Node newNode = new Node<Type>(element);
Node current = head;
do {
current = findNext(element, current, level);
newNode.getNextNodes().add(0, current.getNextNodeAt(level));
current.getNextNodes().set(level, newNode);
}
while (level-- > 0);
return true;
}
public boolean remove(Type element) {
if (contains(element)) {
int level = maxLevel;
Node current = head;
do {
current.getNextNodes().remove(element);
Node next = current.getNextNodeAt(level);
current = next;
} while (level-- > 0);
return true;
}
return false;
}
public boolean removeAt(int index) {
int level = maxLevel;
Node current = head;
boolean found = false;
do {
if (current.getNextNodes().size() - 1 > index) {
found = true;
current.getNextNodes().remove(index);
}
Node next = current.getNextNodeAt(level);
current = next;
} while (level-- > 0);
return found;
}
public Node findByIndex(int index){
int counter = 0;
int level = maxLevel;
Node current = head;
do {
Node next = current.getNextNodeAt(level);
while (next != null) {
if (counter == index) {
return current;
}
current = next;
next = current.getNextNodeAt(level);
counter++;
}
} while (level-- > 0);
return null;
}
public Node find(Type element) {
Node current = head;
int level = maxLevel;
do {
current = findNext(element, current, level);
} while (level-- > 0);
return current;
}
private Node findNext(Type element, Node current, int level) {
Node next = current.getNextNodeAt(level);
while (next != null) {
Type value = (Type) next.getValue();
if (element.compareTo(value) < 0)
break;
current = next;
next = current.getNextNodeAt(level);
}
return current;
}
public int indexOf(Type element) {
int counter = 0;
int level = maxLevel;
Node current = head;
do {
Node next = current.getNextNodeAt(level);
while (next != null) {
counter++;
Type value = (Type) next.getValue();
if (element.compareTo(value) < 0) {
return counter;
}
current = next;
next = current.getNextNodeAt(level);
}
} while (level-- > 0);
return -1;
}
public int getSize(int index){
int size = 0;
int level = maxLevel;
do {
Node current = head;
Node next = current.getNextNodeAt(level);
while (next != null) {
current = next;
next = current.getNextNodeAt(level);
size++;
}
} while (level-- > 0);
return size;
}
public boolean contains(Object o) {
Type value = (Type) o;
Node node = find(value);
return (node != null && node.getValue() != null && ((Type) node.getValue()).compareTo(value) == 0);
}
}
_________________________________________________________________
Node.java
import java.util.List;
public class Node<Type> {
public Node(Type value) {
this.value = value;
}
private Type value;
private List<Node<Type>> nextNodes;
public void addNextNode(Node<Type> newValue){
nextNodes.add(newValue);
}
public Type getValue() {
return value;
}
public Node<Type> getNextNode(){
return nextNodes.get(0);
}
public Node<Type> getNextNodeAt(int i){
return nextNodes.get(i);
}
public List<Node<Type>> getNextNodes() {
return nextNodes;
}
public int getLevel(){
return nextNodes.size();
}
public String toString() {
return "SLN: " + value;
}
}
___________________________________________________________________
Iterator.java
public class Iterator<Type extends Comparable<Type>> implements java.util.Iterator<Type> {
SkipList<Type> skipList;
Node<Type> currentNode;
public Iterator(SkipList<Type> skipList){
this.skipList = skipList;
// TODO: Replace with head
this.currentNode = new Node<Type>(skipList.getHead().getValue());
}
@Override
public boolean hasNext() {
return (currentNode.getNextNode() != null);
}
@Override
public Type next() {
currentNode = currentNode.getNextNode();
return currentNode.getValue();
}
@Override
public void remove() {
// Implemented in SkipList
}
}
____________________________________________________________________________
AbstractSortedSet.java
import java.util.*;
import java.util.Iterator;
public class AbstractSortedSet<Type> extends AbstractSet<Type> implements SortedSet<Type> {
@Override
public Iterator<Type> iterator() {
return null;
}
@Override
public int size() {
return 0;
}
@Override
public Comparator<? super Type> comparator() {
return null;
}
@Override
public SortedSet<Type> subSet(Type fromElement, Type toElement) {
return null;
}
@Override
public SortedSet<Type> headSet(Type toElement) {
return null;
}
@Override
public SortedSet<Type> tailSet(Type fromElement) {
return null;
}
@Override
public Type first() {
return null;
}
@Override
public Type last() {
return null;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.