Implement a skip list class. Save it in file skipList.java. Use random- ization
ID: 3844575 • Letter: I
Question
Implement a skip list class. Save it in file skipList.java. Use random- ization to promote nodes to higher levels. Implement the following methods: skipIn- sert(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, 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.
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.