Everything works with this program. It takes both Strings and ints, however, I feel like my add method is simply too verbose. Does anyone believe I can implement a shorter version of this, or is it good as is?
Note: Nothing can be changed in any of the method signatures or parameters. The only thing I can change is the code within the add and remove methods, as well as the custom nested OrderedListNode class.
public class OrderedLinkedList {
static Comparable temp; //this will be used to reference an element that was removed
public static void main(String[] args) {
/*
TEST STRINGS
*/
OrderedLinkedList list = new OrderedLinkedList();
modCount = 0;
list.add("Dog");
list.add("Bird");
list.add("dog");
list.add("bird");
list.add("Cat");
System.out.println("Before removal");
System.out.println(list);
list.remove("Dog");
System.out.println("Removed " + temp);
list.remove("bird");
System.out.println("Removed " + temp);
System.out.println("After removal");
System.out.println(list);
System.out.println("Total modifications = " + modCount); //make sure modification count is correct
System.out.println("Size of Ordered List = " + theSize); //make sure size is correct
System.out.println();
/*
TEST INTEGERS
*/
OrderedLinkedList integerList = new OrderedLinkedList();
modCount = 0;
integerList.add(1);
integerList.add(233);
integerList.add(42);
integerList.add(100);
System.out.println("Before removal");
System.out.println(integerList);
integerList.remove(1);
System.out.println("Removed " + temp);
integerList.add(232);
System.out.println("After removal of " + temp + " and addition of another element");
System.out.println(integerList);
System.out.println("Total modifications = " + modCount); //make sure modification count is correct
System.out.println("Size of Ordered List = " + theSize); //make sure size is correct
}
/**************************************************************************
* Constants
*************************************************************************/
/**
* return value for unsuccessful searches
*/
private static final OrderedListNode NOT_FOUND = null;
/**************************************************************************
* Attributes
*************************************************************************/
/**
* current number of items in list
*/
private static 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 static 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)
//FOR REFERENCE - public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {
OrderedListNode newElement = NOT_FOUND;
if(head.next == tail) { //if the list contains only the head and tail (head.next being the tail) place item between the two.
newElement = new OrderedListNode(obj, head, tail);
head.next = newElement; // [HEAD -> newElement -> TAIL]
tail.before = newElement;
modCount++; //
theSize++; //if size is not increased, output will not print correctly
return true;
}
for(OrderedListNode element = head.next; element != tail; element = element.next) { //loop through each node of the list, stopping at the tail
if(element.before == head && obj.compareTo(element.dataItem) < 0) { //if head is before inserted element and less than element at cursor
newElement = new OrderedListNode(obj, head, element);
head.next = newElement; //swap cursors
element.before = newElement;
modCount++; //another modification
theSize++; //increase size by 1
return true;
}
if(obj.compareTo(element.dataItem) > 0 && element.next == tail) { //if inserted element is greater than dataItem and next is tail
newElement = new OrderedListNode(obj, element, tail);
element.next = newElement;
tail.before = newElement;
modCount++; //another modification
theSize++; //increase size by 1
return true;
}
if(obj.compareTo(element.dataItem) > 0 && obj.compareTo(element.next.dataItem) < 0) { //if inserted element is greater than element at cursor, but less than current element
OrderedListNode elementBefore = element;
OrderedListNode elementAfter = element.next;
newElement = new OrderedListNode(obj, element, element.next);
elementBefore.next = newElement;
elementAfter.before = newElement;
modCount++; //another modification
theSize++; //increase size by 1
return true;
}
}
return false;
}
/*
* 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)
for(OrderedListNode element = head.next; element != tail; element = element.next) {
if(obj.equals(element.dataItem)) { //if element being removed is at the cursor
OrderedListNode previousNode = element.before;
OrderedListNode nextNode = element.next;
temp = obj; //temp will be used to access element that was removed
nextNode.before = previousNode; //places next element that's after before to the element after current element [prev -> current -> next]
previousNode.next = nextNode; //places prev of next element to the element before current
element.dataItem = (Comparable)NOT_FOUND; //removed element is now null
modCount++; //another modification
theSize--; //reduce the size by 1
return true; //if remove is successful
}
}
return false; //otherwise, not successful removal
}
/**
* 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.dataItem.toString();
if (currentNode.next != tail) {
s += ", ";
}
currentNode = currentNode.next;
}
return s;
}
/**************************************************************************
* Inner Classes
*************************************************************************/
/**
* Nested class OrderedListNode.
* <p>
* Encapsulates the fundamental building block of an OrderedLinkedList
* contains a data item, and references to both the next and before 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.
public static class OrderedListNode {
/**
* FOR REFERENCE
* <p>
* private static class Node<E> {
* E item;
* Node<E> next;
* Node<E> prev;
* <p>
* Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
* }
* }
*/
Comparable dataItem;
OrderedListNode next;
OrderedListNode before;
public OrderedListNode(Comparable item, OrderedListNode before, OrderedListNode next) {
this.dataItem = item;
this.next = next;
this.before = before;
}
}//end nested class
}
Output:
Before removal
Bird, Cat, Dog, bird, dog
Removed Dog
Removed bird
After removal
Bird, Cat, dog
Total modifications = 7
Size of Ordered List = 3
Before removal
1, 42, 100, 233
Removed 1
After removal of 1 and addition of another element
42, 100, 232, 233
Total modifications = 6
Size of Ordered List = 4
private static int theSize;
was given to you like that and cannot be changed? – janos♦ Mar 13 at 7:23OrderedLinkedList
, and without type parameter, or is that your own writing? As a homework exercise, I would expect something different, something likeSortedLinkedList<T extends Comparable<T>>
– janos♦ Mar 13 at 9:36