Skip lists can be rather tricky to implement. The way in which the index nodes a
ID: 3605629 • Letter: S
Question
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.Explanation / Answer
OrderedLinkedList.java
import java.io.*;
import java.util.*;
//class OrderedLinkedList
public class OrderedLinkedList
{
private static final OrderedListNode NOT_FOUND = null;
//ordered list node variables
private int SizeVal;
private OrderedListNode headVal;
private OrderedListNode tailVal;
private int moduleCount;
//constructor for the class
public OrderedLinkedList()
{
clear();
}
//add comparable object
public boolean add(Comparable obj)
{
//object for inner class
OrderedListNode node = new OrderedListNode(obj);
if(headVal.next == tailVal)
{
headVal.next = node;
node.next = tailVal;
tailVal.preVal = node;
return true;
}
if(obj.compareTo(headVal.next.ItemVal) < 0)
{
node.next = headVal.next;
headVal.next = node;
return true;
}
//inner class variables
OrderedListNode current = headVal.next;
OrderedListNode previous = headVal;
while(current != tailVal && (node.ItemVal).compareTo(current.ItemVal) >= 0)
{
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
return true;
}
//remove comparable objects
public boolean remove(Comparable obj)
{
OrderedListNode previous = null;
OrderedListNode current = headVal;
while(current != null &&(obj.compareTo(current.next) > 0))
{
previous = current;
current = current.next;
}
if(current != null &&
(obj.compareTo(current.next) == 0))
{
if(previous == null)
headVal = headVal.next;
else
previous.next = current.next;
SizeVal--;
return true;
}
else
return false;
}
//clear method
public void clear()
{
headVal = new OrderedListNode("HEAD", null, null);
tailVal = new OrderedListNode("TAIL", headVal, null);
headVal.next = tailVal;
SizeVal = 0;
moduleCount++;
}
//method Boolean is empty
public boolean isEmpty()
{
return SizeVal == 0;
}
//method size
public int size()
{
//returns size
return SizeVal;
}
//method to string
public String toString()
{
//string variables
String s = "";
OrderedListNode currentNodeVal = headVal.next;
while(currentNodeVal != tailVal)
{
s += currentNodeVal.ItemVal.toString();
if(currentNodeVal.next != tailVal)
{
s += ", ";
}
currentNodeVal = currentNodeVal.next;
}
return s;
}
//inner class OrderedListNode
public static class OrderedListNode
{
//comparable objects
Comparable ItemVal;
OrderedListNode next;
OrderedListNode preVal;
OrderedListNode(Comparable ItemVal)
{
this(ItemVal, null, null);
}
OrderedListNode(Comparable ItemVal, OrderedListNode preVal,
OrderedListNode next)
{
this.ItemVal = ItemVal;
this.next = next;
this.preVal = preVal;
}
//comparable getdata
Comparable getData()
{
return ItemVal;
}
OrderedListNode getNext()
{
return next;
}
OrderedListNode getPrev()
{
return preVal;
}
}
//creation of main methods
public static void main(String[] args)
{
//object for the class OrderedLinkedList
OrderedLinkedList listObj = new OrderedLinkedList();
listObj.add("3");
listObj.add("5");
listObj.add("2");
listObj.add("4");
listObj.add("1");
System.out.println(listObj);
}
}
Answer:
Note: name of class, inner class and methods are implemented as per the instructions provided.
Part 2:
OrderedLinkedList.java
import java.io.*;
import java.util.*;
//class OrderedLinkedList
public class OrderedLinkedList
{
private static final OrderedListNode NOT_FOUND = null;
//ordered list node variables
private int SizeVal;
private OrderedListNode headVal;
private OrderedListNode tailVal;
private int moduleCount;
//constructor for the class
public OrderedLinkedList()
{
clear();
}
//add comparable object
public boolean add(Comparable obj)
{
//object for inner class
OrderedListNode node = new OrderedListNode(obj);
if(headVal.next == tailVal)
{
headVal.next = node;
node.next = tailVal;
tailVal.preVal = node;
return true;
}
if(obj.compareTo(headVal.next.ItemVal) < 0)
{
node.next = headVal.next;
headVal.next = node;
return true;
}
//inner class variables
OrderedListNode current = headVal.next;
OrderedListNode previous = headVal;
while(current != tailVal && (node.ItemVal).compareTo(current.ItemVal) >= 0)
{
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
return true;
}
//remove comparable objects
public boolean remove(Comparable obj)
{
OrderedListNode previous = null;
OrderedListNode current = headVal;
while(current != null &&(obj.compareTo(current.next) > 0))
{
previous = current;
current = current.next;
}
if(current != null &&
(obj.compareTo(current.next) == 0))
{
if(previous == null)
headVal = headVal.next;
else
previous.next = current.next;
SizeVal--;
return true;
}
else
return false;
}
//clear method
public void clear()
{
headVal = new OrderedListNode("HEAD", null, null);
tailVal = new OrderedListNode("TAIL", headVal, null);
headVal.next = tailVal;
SizeVal = 0;
moduleCount++;
}
//method Boolean is empty
public boolean isEmpty()
{
return SizeVal == 0;
}
//method size
public int size()
{
//returns size
return SizeVal;
}
//method to string
public String toString()
{
//string variables
String s = "";
OrderedListNode currentNodeVal = headVal.next;
while(currentNodeVal != tailVal)
{
s += currentNodeVal.ItemVal.toString();
if(currentNodeVal.next != tailVal)
{
s += ", ";
}
currentNodeVal = currentNodeVal.next;
}
return s;
}
//inner class OrderedListNode
public static class OrderedListNode
{
//comparable objects
Comparable ItemVal;
OrderedListNode next;
OrderedListNode preVal;
OrderedListNode(Comparable ItemVal)
{
this(ItemVal, null, null);
}
OrderedListNode(Comparable ItemVal, OrderedListNode preVal,
OrderedListNode next)
{
this.ItemVal = ItemVal;
this.next = next;
this.preVal = preVal;
}
//comparable getdata
Comparable getData()
{
return ItemVal;
}
OrderedListNode getNext()
{
return next;
}
OrderedListNode getPrev()
{
return preVal;
}
}
//creation of main methods
public static void main(String[] args)
{
//object for the class OrderedLinkedList
OrderedLinkedList listObj = new OrderedLinkedList();
listObj.add("3");
listObj.add("5");
listObj.add("2");
listObj.add("4");
listObj.add("1");
System.out.println(listObj);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.