import java.util.Iterator; public class SkipList> { static final int PossibleLevels = 33; static class Entry { E element; Entry[] next; Entry prev; public Entry(E x, int lev) { element = x; next = new Entry[lev]; // add more code as needed } public E getElement() { return element; } } // Constructor public SkipList() { } // Add x to list. If x already exists, reject it. Returns true if new node is added to list public boolean add(T x) { return true; } // Find smallest element that is greater or equal to x public T ceiling(T x) { return null; } // Does list contain x? public boolean contains(T x) { return false; } // Return first element of list public T first() { return null; } // Find largest element that is less than or equal to x public T floor(T x) { return null; } // Return element at index n of list. First element is at index 0. public T get(int n) { return null; } // Is the list empty? public boolean isEmpty() { return false; } // Iterate through the elements of list in sorted order public Iterator iterator() { return null; } // Return last element of list public T last() { return null; } // Remove x from list. Removed element is returned. Return null if x not in list public T remove(T x) { return null; } // Return the number of elements in the list public int size() { return 0; } }

Driver is Provided:

import java.io.File; import java.io.FileNotFoundException; import java.util.Iterator; import java.util.Scanner; //Driver program for skip list implementation. public class SkipListDriver { public static void main(String[] args) throws FileNotFoundException { Scanner sc; if (args.length > 0) { File file = new File(args[0]); sc = new Scanner(file); } else { sc = new Scanner(System.in); } String operation = ""; long operand = 0; long result = 0; Long returnValue = null; SkipList skipList = new SkipList(); // Initialize the timer Timer timer = new Timer(); while (!((operation = sc.next()).equals("End"))) { returnValue = null; switch (operation) { case "Add": operand = sc.nextLong(); if(skipList.add(operand)) { returnValue = 1L; } break; case "Ceiling": operand = sc.nextLong(); returnValue = skipList.ceiling(operand); break; case "First": returnValue = skipList.first(); break; case "Get": int intOperand = sc.nextInt(); returnValue = skipList.get(intOperand); break; case "Last": returnValue = skipList.last(); break; case "Floor": operand = sc.nextLong(); returnValue = skipList.floor(operand); break; case "Remove": operand = sc.nextLong(); if (skipList.remove(operand) != null) { returnValue = 1L; } break; case "Contains": operand = sc.nextLong(); if (skipList.contains(operand)) { returnValue = 1L; } break; } if (returnValue != null) { result += returnValue; } } // End Time timer.end(); System.out.println(result); System.out.println(timer); } /** Timer class for roughly calculating running time of programs * @author rbk * Usage: Timer timer = new Timer(); * timer.start(); * timer.end(); * System.out.println(timer); // output statistics */ public static class Timer { long startTime, endTime, elapsedTime, memAvailable, memUsed; public Timer() { startTime = System.currentTimeMillis(); } public void start() { startTime = System.currentTimeMillis(); } public Timer end() { endTime = System.currentTimeMillis(); elapsedTime = endTime-startTime; memAvailable = Runtime.getRuntime().totalMemory(); memUsed = memAvailable - Runtime.getRuntime().freeMemory(); return this; } public String toString() { return "Time: " + elapsedTime + " msec. " + "Memory: " + (memUsed/1048576) + " MB / " + (memAvailable/1048576) + " MB."; } } }

Do not change the signatures of methods declared to be public. You can add additional fields, nested classes, and methods as needed. Do not create additional source files. Place all code in skipList.java. add(x): Add a new element x to the list. If x already exists in the skip list, replace it and return false. otherwise, insert x into the skip list and return true. * ceiling(x): Find smallest element that is greater or equal to x. contains (x): Does list contain x? firstO: Return first element of list floor(x): Find largest element that is less than or equal to x get (n): Return element at index n of list. First element is at index e isEmpty(): Is the list empty? *iterator(): Iterator for going through the elements of list in sorted order. *last(): Return last element of list remove(x): Remove x from the list. If successful, removed element is returned. otherwise, return nul size(): Return the number of elements in the list. Do not change the signatures of methods declared to be public. You can add additional fields, nested classes, and methods as needed. Do not create additional source files. Place all code in skipList.java. add(x): Add a new element x to the list. If x already exists in the skip list, replace it and return false. otherwise, insert x into the skip list and return true. * ceiling(x): Find smallest element that is greater or equal to x. contains (x): Does list contain x? firstO: Return first element of list floor(x): Find largest element that is less than or equal to x get (n): Return element at index n of list. First element is at index e isEmpty(): Is the list empty? *iterator(): Iterator for going through the elements of list in sorted order. *last(): Return last element of list remove(x): Remove x from the list. If successful, removed element is returned. otherwise, return nul size(): Return the number of elements in the list