Assignment Objective

Implement and test an ORDERED linked list of integer nodes using references (as opposed to an array).

Implementation Details

Use the following implementation of IntegerNode.javaDownload IntegerNode.java. Make NO changes to IntegerNode.java and do not submit it as part of this assignment.

All of the code for this project will be in IntegerList.java, and it is fully described in this UMLDownload this UML. IntegerList must be in the adt package. This is the only file you should turn in for this project. Be sure that the class is fully Javadoc'd and be sure to include the extra documentation that is mentioned in the UML. Do not include any other fields, methods, or constructors not mentioned in the UML. Good luck and start early!!!

My code has the following statistics:

Constructor: 1 line

add: 18 lines (including documentation)

remove: 21 lines (including documentation)

reverse: 10 lines

toString: 7 lines

main: 64 lines (mostly copied and pasted)

Note: This is not a grading standard! It's only to give you an idea of how long each method should be.

IntegerNode.java

package adt;

public class IntegerNode { private int item; private IntegerNode next;

public IntegerNode(int newItem) { item = newItem; next = null; } // end constructor

public IntegerNode(int newItem, IntegerNode nextNode) { item = newItem; next = nextNode; } // end constructor

public void setItem(int newItem) { item = newItem; } // end setItem

public int getItem() { return item; } // end getItem

public void setNext(IntegerNode nextNode) { next = nextNode; } // end setNext

public IntegerNode getNext() { return next; } // end getNext public String toString() { if (next==null) return ""+item; else return item+" -> "; } // end toString

} // end class IntegerNode

this UML

UML for Project 2

IntegerList

-head: IntegerNode

-HEAD_VALUE:int

+<> IntegerList ()

+add(itemToAdd:int): void

+remove(int itemToRemove): boolean

+reverse(): void

+toString(): String

+main(args: String[]): void

head maintains the one and only link into the list. It references the first item in the list.

Since head is an IntegerNode, it has a value even though all you really need is the reference. HEAD_VALUE is a constant that stores a value for the head of the list. It is equal to -999999

add has the following documentation and algorithm - Find the position, Make a New Node, Insert the node (Head of list case), Insert the node (General case)

Unlike add, remove has a return value to deal with because if itemToRemove is not in the list, it can't be removed. This will return true if and only if the itemToRemove is in the list. remove has the following documentation and algorithm - Find the node to remove, Item not found case (if the list was traversed and the item not found or current is not the item to remove), Remove the Node (Head of list case), Remove the node (General case)

reverse should reverse all the references in the linked list, making it backwards. Note that this WILL cause add and remove to stop working correctly. All implementation should go in a SINGLE LOOP. (Hint: Make and maintain a third IntegerNode reference named 'next' for current to go for the next loop iteration). This method must be simple assignments and method calls. Make sure to reset head to an appropriate value at the end of the loop!

toString should traverse the list, appending to a String as it goes. For each node, if that node is not the head, just append that node's toString.

NONE OF THE ABOVE METHODS DO OUTPUT; ALL OUTPUT BELONGS IN MAIN!!!!

Main must do each of the following to a single list, PRINTING the list at each step (cont):

Add 5 to an empty list //empty list case

Add 7 //add to tail case

Add 3 //add to head case

Add 1

Add 6 //add to middle case

Add 9

Output "REVERSING" and output the reversed list

Output "FIXING" and output the reversed list, reversed again (thus restoring the list)

Remove 11 //item not found, traversed whole list case

Remove 4 //item not found, traversed partial list case

Remove -3 //item not found, traversed none of the list case

Remove 5 //remove from middle case

Remove 6

Remove 6 //remove an item that WAS in the list case

Remove -3

Remove 1 //remove from head case

Remove 3 //remove from head when head was removed case

Remove 9 //remove from the tail case

[End of Output]

Example of what the code for remove looks like:

removeItem = 4;//change this variable for each case

if (!list.remove(removeItem))

System.out.println("Item "+removeItem+" not found");

System.out.println(list);