package dataStructures; /** * Class OrderedLinkedList. * * This class functions as a linked list, but ensures items are stored in ascending order. * */ public class OrderedLinkedList { /************************************************************************** * Constants *************************************************************************/ /** return value for unsuccessful searches */ private static final OrderedListNode NOT_FOUND = null; /************************************************************************** * Attributes *************************************************************************/ /** current number of items in list */ private int theSize; /** reference to list header node */ private OrderedListNode head; /** reference to list tail node */ private OrderedListNode tail; /** current number of modifications to list */ private int modCount; /************************************************************************** * Constructors *************************************************************************/ /** * Create an instance of OrderedLinkedList. * */ public OrderedLinkedList() { // empty this OrderedLinkedList clear(); } /************************************************************************** * Methods *************************************************************************/ /* * Add the specified item to this OrderedLinkedList. * * @param obj the item to be added */ public boolean add(Comparable obj) { // TODO: Implement this method (8 points) } /* * Remove the first occurrence of the specified item from this OrderedLinkedList. * * @param obj the item to be removed */ public boolean remove(Comparable obj) { // TODO: implement this method (7 points) } /** * Empty this OrderedLinkedList. */ public void clear() { // reset header node head = new OrderedListNode("HEAD", null, null); // reset tail node tail = new OrderedListNode("TAIL", head, null); // header references tail in an empty LinkedList head.next = tail; // reset size to 0 theSize = 0; // emptying list counts as a modification modCount++; } /** * Return true if this OrderedLinkedList contains 0 items. */ public boolean isEmpty() { return theSize == 0; } /** * Return the number of items in this OrderedLinkedList. */ public int size() { return theSize; } /* * Return a String representation of this OrderedLinkedList. * * (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { String s = ""; OrderedListNode currentNode = head.next; while (currentNode != tail) { s += currentNode.theItem.toString(); if (currentNode.next != tail) { s += ", "; } currentNode = currentNode.next; } return s; } /************************************************************************** * Inner Classes *************************************************************************/ /** * Nested class OrderedListNode. * * Encapsulates the fundamental building block of an OrderedLinkedList * contains a data item, and references to both the next and previous nodes * in the list */ // TODO: Implement the nested class OrderedListNode (5 points). This nested class // should be similar to the nested class ListNode of the class LinkedList, but // should store a data item of type Comparable rather than Object. } 

Skip lists can be rather tricky to implement. The way in which the index nodes are updated when items are added or removed can result in poor performance if not done properly. Additionally, it is important to conserve space, which entails minimizing the number of node references each node contains. Because of these problems, all I am asking you to do for the second part of this assignment is to complete the first step in creating a skip list: implement a very basic, ordered linked list. I have provided the framework of the class for you: class OrderedLinkedList. All you need to do is implement three parts of the list: 1. the nested OrderedListNode class 2. the add (Comparable obj) method 3. the remove (Comparable obj) method Please follow these guidelines when implementing your class: 1. Remember that because the items in the list must be stored in sorted order, you will need to use data items of type Comparable rather than type Object. 2. Do not extend any of the data structure classes or interfaces I have provided for this course (doing so will be more trouble than it is worth) 3. You do not need to add any additional methods beyond those listed above. 4. You may store the items in either ascending or descending order, whichever you prefer, but choose only one ordering. 5. The OrderedListNode class must be a nested class (i.e., it must be an inner class declared as static). The implementation should be similar to the nested class ListNode of the LinkedList class, except it should store a data item of type Comparable rather than type object 6. Be sure to test your OrderLinkedList implementation. Remember that you do not need to create your own Comparable items to use as test data; just use String objects or Integer objects