Implementing a Skip list in JAVA 1 Objective Build a skip list data structure to
ID: 3856627 • Letter: I
Question
Implementing a Skip list in JAVA
1 Objective Build a skip list data structure to support the traversal, searching, addition, and deletion of integers from a skip list. This implementation wll support building a skip list to support some number of occurrences of integers in the range of 1 to 1000. The objective of this assignment requires the reading of an input file which contains commands and data to build, search, modify, and print a skip list containing integers. 2 Requirements Read the input file formatted as follows. The input file will contain at least one command per line, either insert, delete, search, or print. (The program will terminate upon successfully reading the last command in the input file.) The commands are defined in detail below. The second parameter, if appropriate, will always be an integer for this assignment. There will be only one parameter per command. For example, there will only be a single integer for the insert, search, or delete commands. In the event that no parameter is specified for these commands, it is acceptable to ignore the command and continue to process the input file. No parameter is required for a print command. The commands are shown in the table below: Command Description Parameter(s) Insert expects a space, followed by a single integer Search expects a s Delete xpects a space, followed by a single integer Print followed by a single integer does not expect any additional data Table 1: Input File Commands 2.1 Design Constraint:s 1. The input file(s) provided will have the following properties (a) Each record in the input file will consist of a command, described above, appro- priately followed by an integer (b) In the event there are multiple insert commands, those insert commands will be for integers where the inserted integers are in any order. There will be one integer per insert command.Explanation / Answer
import java.util.Scanner;
/* Class SkipNode */
class SkipNode
{
int element;
SkipNode right;
SkipNode down;
/* Constructor */
public SkipNode(int x)
{
this(x, null, null);
}
/* Constructor */
public SkipNode(int x, SkipNode rt, SkipNode dt)
{
element = x;
right = rt;
down = dt;
}
}
/* Class SkipList */
class SkipList
{
private SkipNode header;
private int infinity;
private SkipNode bottom = null;
private SkipNode tail = null;
/* Constructor */
public SkipList(int inf)
{
infinity = inf;
bottom = new SkipNode(0);
bottom.right = bottom.down = bottom;
tail = new SkipNode(infinity);
tail.right = tail;
header = new SkipNode(infinity, tail, bottom);
}
/* Function to insert element */
public void insert(int x)
{
SkipNode current = header;
bottom.element = x;
while (current != bottom)
{
while (current.element < x)
current = current.right;
/* If gap size is 3 or at bottom level and must insert, then promote middle element */
if (current.down.right.right.element < current.element)
{
current.right = new SkipNode(current.element, current.right, current.down.right.right);
current.element = current.down.right.element;
}
else
current = current.down;
}
/* Raise height of skiplist if necessary */
if (header.right != tail)
header = new SkipNode(infinity, tail, header);
}
/* Function to clear list */
public void makeEmpty()
{
header.right = tail;
header.down = bottom;
}
/* Function to check if empty */
public boolean isEmpty()
{
return header.right == tail && header.down == bottom;
}
/* Function to get node at a position */
private int elementAt(SkipNode t)
{
return t == bottom ? 0 : t.element;
}
/* Function to print list */
public void printList()
{
System.out.print(" Skiplist = ");
SkipNode current = header;
while( current.down != bottom )
current = current.down;
while (current.right != tail )
{
System.out.print(current.element +" ");
current = current.right;
}
System.out.println();
}
}
/* Class SkipListTest */
public class SkipListTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of SkipList */
SkipList sl = new SkipList(100000000);
System.out.println("SkipList List Test ");
char ch;
/* Perform list operations */
do
{
System.out.println(" SkipList List Operations ");
System.out.println("1. insert");
System.out.println("2. check empty");
System.out.println("3. clear");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
sl.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Empty status = "+ sl.isEmpty());
break;
case 3 :
System.out.println("List cleared ");
sl.makeEmpty();
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display List */
sl.printList();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}