Instructions
Requirements and Specifications
Figure 1: Linked List with a dummy head node
Notes about the Node class:
Complete the java assignment implementation of the following Node class:
public class Node {
// fields
private E item;
private Node next;
// methods
public Node(E obj)
public void setItem(E obj)
public void setNext (Node temp)
public E getItem()
public Node getNext()
@Override public String toString()
}
where, item is a private field of generic type E,
and next is a private field reference to the next Node in the list.
Source Code
A5 TESTS
/**
A5Tests.java
Provides some tests of methods of the Node and LinkedList classes.
@author TCSS 143 instructors
@version 1.2
*/
public class A5Tests {
/** The pass/fail status of the tests. */
private boolean allTestsPassed = true;
/** To get verbose test output, set this to true. */
private boolean verbose = true;
/** The List used to test the outcomes. */
private LinkedList movieList;
/**
The starting point for the test program.
@param args command line arguments - ignored in this program
*/
public static void main(String[] args) {
new A5Tests().runTests();
}
/**
Runs the tests of the various LinkedList methods.
*/
private void runTests() {
// Create the empty movie list
movieList = new LinkedList();
// Display the empty list
System.out.println("The empty list before adding any movies:\n" + movieList);
testPrintEmptyList();
addListItems();
// Display the original list
System.out.println("Original movieList:\n" + movieList + "\n");
// Test all methods
testInsert(); // test various add methods
testDuplicate(); // test the duplicate()
testReverse(); // test the duplicateReversed() method
testRemove(); // test different remove options
if (allTestsPassed) {
System.out.println("\nAll tests passed!");
}
}
/**
Initializes the LinkedList that will be used in the tests.
*/
private void addListItems() {
// Add few movies to the LinkedList
movieList.add("Frozen");
movieList.add("The Lion King");
movieList.add("Moana");
movieList.add("Onward");
movieList.add("Toy Story");
movieList.add("Aladdin");
movieList.add("Your Name");
}
/**
Test toString on an empty list.
*/
public void testPrintEmptyList() {
String expected = "Size:0 []";
String actual = movieList.toString();
if (!actual.equals(expected)) {
allTestsPassed = false;
System.out.println("toString() failed on an empty list!");
}
if (verbose) {
System.out.println("expected toString() output for an empty list : "
+ expected);
System.out.println("actual toString() output for an empty list : "
+ actual + "\n");
}
}
/**
Test various add methods.
*/
public void testInsert() {
// Add at the begining of the list
movieList.add(0, "Spider-man");
if (!movieList.get(0).equals("Spider-man")) {
allTestsPassed = false;
System.out.println("Test add at index 0 failed!");
}
if (verbose) {
System.out.println("After add(0, \"Spider-man\"):\n" + movieList + "\n");
}
if (!(movieList.getSize() == 8)) {
allTestsPassed = false;
System.out.println("The list size is not correct after add()");
}
// Add movie at the end of the list
movieList.add("Zootopia");
if (!movieList.get(movieList.getSize() - 1).equals("Zootopia")) {
allTestsPassed = false;
System.out.println("Test add at end of list failed!");
}
if (verbose) {
System.out.println("After add(\"Zootopia\"):\n" + movieList + "\n");
}
if (!(movieList.getSize() == 9)) {
allTestsPassed = false;
System.out.println("The list size is not correct after add()");
}
// Add a movie at the k index
movieList.add(4, "Inside Out");
if (!movieList.get(4).equals("Inside Out")) {
allTestsPassed = false;
System.out.println("Test add at index k failed!");
}
if (verbose) {
System.out.println("After add(4, \"Inside Out\"):\n" + movieList + "\n");
}
if (!(movieList.getSize() == 10)) {
allTestsPassed = false;
System.out.println("The list size is not correct after add()");
}
// test IndexOutOfBoundsException
try {
movieList.add(-1, "Bad Index");
allTestsPassed = false;
System.out.println("add() failed to throw IndexOutOfBoundsException!");
} catch (IndexOutOfBoundsException e) {
// test passed!
}
}
/**
Test duplicate() method.
*/
public void testDuplicate() {
// Create a duplicate of the original list
List copy = movieList.duplicate();
// Loop to check if copy is correct
for (int i = 0; i < movieList.getSize(); i++) {
if (!movieList.get(i).equals(copy.get(i))) {
allTestsPassed = false;
System.out.println("Test of the duplicate() method failed!");
}
}
if (verbose) {
System.out.println("After duplicate():\n" + copy + "\n");
}
if (!(copy.getSize() == 10)) {
allTestsPassed = false;
System.out.println("The copy size is not correct after calling duplicate()");
}
// test duplicate() on an empty list
List empty = new LinkedList<>();
copy = empty.duplicate();
if (!(copy.getSize() == 0)) {
allTestsPassed = false;
System.out.println("The copy size is not correct after calling duplicate() "
+ "on an empty list!");
}
// test duplicate() on a list containing a single item
List oneItem = new LinkedList<>();
oneItem.add("Test");
copy = oneItem.duplicate();
if (!(copy.getSize() == 1)) {
allTestsPassed = false;
System.out.println("The copy size is not correct after calling duplicate() "
+ "on a list containing one item!");
}
}
/**
Test duplicateReversed() method.
*/
public void testReverse() {
// Create a reverse of the original list
List reverseList = movieList.duplicateReversed();
// Loop to check if reverse is correct
for (int i = 0; i < movieList.getSize(); i++) {
if (!movieList.get(i).equals(
reverseList.get(reverseList.getSize() - (i + 1)))) {
allTestsPassed = false;
System.out.println("Test of the duplicateReversed() method failed!");
}
}
if (verbose) {
System.out.println("The copy after calling duplicateReversed():\n"
+ reverseList + "\n");
System.out.println("The original after calling duplicateReversed():\n"
+ movieList + "\n");
}
if (!(reverseList.getSize() == 10)) {
allTestsPassed = false;
System.out.println("The copy size is not correct "
+ "after calling duplicateReversed()");
}
// test duplicateReversed() on an empty list
List empty = new LinkedList<>();
reverseList = empty.duplicateReversed();
if (!(reverseList.getSize() == 0)) {
allTestsPassed = false;
System.out.println("The copy size is not correct after calling "
+ "duplicateReversed() on an empty list!");
}
// test duplicate() on a list containing a single item
List oneItem = new LinkedList<>();
oneItem.add("Test");
reverseList = oneItem.duplicateReversed();
if (!(reverseList.getSize() == 1)) {
allTestsPassed = false;
System.out.println("The copy size is not correct after calling "
+ "duplicateReversed() on a list containing one item!");
}
}
/**
Test remove methods.
*/
public void testRemove() {
// Create a duplicate list
List duplicateList = movieList.duplicate();
// Remove from the begining of the list
duplicateList.remove(0);
if (!duplicateList.get(0).equals(movieList.get(1))) {
allTestsPassed = false;
System.out.println("Test remove at index 0 failed!");
}
if (verbose) {
System.out.println("After remove(0):\n" + duplicateList + "\n");
}
if (!(duplicateList.getSize() == 9)) {
allTestsPassed = false;
System.out.println("The list size is not correct after calling remove(0)!");
}
// Remove movie at the end of the list
duplicateList.remove(duplicateList.getSize() - 1);
if (!duplicateList.get(duplicateList.getSize() - 1).equals(
movieList.get(movieList.getSize() - 2))) {
allTestsPassed = false;
System.out.println("Test remove at end of the list failed!");
}
if (verbose) {
System.out.println("After remove(duplicateList.getSize() - 1):\n"
+ duplicateList + "\n");
}
if (!(duplicateList.getSize() == 8)) {
allTestsPassed = false;
System.out.println("The list size is not correct after calling "
+ "remove() on the last element of the list!");
}
// Remove movie based on movie title
int sizeBefore = duplicateList.getSize();
duplicateList.remove("Inside Out");
boolean pass = duplicateList.getSize() == sizeBefore - 1;
pass = pass && duplicateList.indexOf("Inside Out") == -1;
if (!pass) {
allTestsPassed = false;
System.out.println("Test remove based on title failed!");
}
if (verbose) {
System.out.println("After remove(\"Inside Out\"):\n" + duplicateList + "\n");
}
if (!(duplicateList.getSize() == 7)) {
allTestsPassed = false;
System.out.println("The list size is not correct after calling "
+ "remove(\"Title\")!");
}
// Remove movie based on movie title at end of list
duplicateList.remove("Your Name");
if (duplicateList.indexOf("Your Name") != -1) {
allTestsPassed = false;
System.out.println("Test remove based on title at end of list failed!");
}
if (verbose) {
System.out.println("After remove(\"Your Name\"):\n" + duplicateList + "\n");
}
if (!(duplicateList.getSize() == 6)) {
allTestsPassed = false;
System.out.println("The list size is not correct after calling "
+ "remove(\"Title\") on the last movie in the list!");
}
}
}
LINKED LIST
public class LinkedList implements List {
/**
* Head node of the list
*/
private Node head;
/**
* Number of elements in the list
*/
private int size;
/**
* No-args constructor. Creates an empty list
*/
public LinkedList() {
head = new Node<>(null);
size = 0;
}
/**
* Return true if the list is empty; false otherwise.
*
* @return true if the list is empty; false otherwise
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Returns the number of items in the list.
*
* @return the number of items in the list
*/
@Override
public int getSize() {
return size;
}
/**
* Adds an item to the end of the list.
*
* precondition: none
* postcondition: item is added at the end of the list
*
* @param item the element to add to the end of the list
*/
@Override
public void add(E item) {
add(size, item);
}
/**
* Adds an item to the list at the given index.
*
* precondition: none
* postcondition: item is added at the given index
*
* @param index the position at which to add the item
* @param item the element to add to the list
* @throws IndexOutOfBoundsException if index is out of bounds
*/
@Override
public void add(int index, E item) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node curr = head;
for (int i = 0; i
curr = curr.getNext();
}
Node newNode = new Node<>(item);
newNode.setNext(curr.getNext());
curr.setNext(newNode);
size++;
}
/**
* Removes the item from the list at the given index.
*
* precondition: none
* postcondition: removes the item from the list at the given index
*
* @param index the position from which to remove an element
* @throws IndexOutOfBoundsException if index is out of bounds
*/
@Override
public void remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node curr = head;
for (int i = 0; i
curr = curr.getNext();
}
curr.setNext(curr.getNext().getNext());
size--;
}
/**
* Removes the first occurrence of an item from the list.
* If the item is not found in the list then the list remains unchanged.
*
* precondition: none
* postcondition: removes the first element in the list whose equals() method
* matches that of the given item
*
* @param item the element to remove
*/
@Override
public void remove(E item) {
Node curr = head;
while (curr.getNext() != null) {
E nextElem = curr.getNext().getItem();
if (nextElem.equals(item)) {
curr.setNext(curr.getNext().getNext());
size--;
return;
}
curr = curr.getNext();
}
}
/**
* Returns the item at the specified index.
*
* precondition: none
* postcondition: returns the element at specified index
*
* @param index the position from which to return an element
* @return the item at the specified index
* @throws IndexOutOfBoundsException if index is out of bounds
*/
@Override
public E get(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
Node curr = head.getNext();
for (int i = 0; i
curr = curr.getNext();
}
return curr.getItem();
}
/**
* Returns the index of the first item in the list whose equal method
* matches that of the given item, or -1 if no match is found.
*
* precondition: none
* postcondition: returns the index of specified item
*
* @param item the element to search for
* @return the index of the first item that matches given item
* or -1 if no match is found
*/
@Override
public int indexOf(E item) {
int counter = 0;
Node curr = head.getNext();
while (curr != null) {
E elem = curr.getItem();
if (elem.equals(item)) {
return counter;
}
counter++;
curr = curr.getNext();
}
return -1;
}
/**
* Creates a duplicate of the list.
*
* precondition: none
* postcondition: returns a copy of the linked list
*
* @return a copy of the linked list
*/
@Override
public List duplicate() {
List copy = new LinkedList<>();
Node curr = head.getNext();
while(curr != null) {
copy.add(curr.getItem());
curr = curr.getNext();
}
return copy;
}
/**
* Creates a duplicate of the list with the nodes in reverse order.
*
* precondition: none
* postcondition: returns a copy of the linked list with the nodes in
* reverse order
*
* @return a copy of the linked list in reverse order
*/
@Override
public List duplicateReversed() {
List copy = new LinkedList<>();
Node curr = head.getNext();
while(curr != null) {
copy.add(0, curr.getItem());
curr = curr.getNext();
}
return copy;
}
/**
* Overridden toString method.
* @return string representation of the list
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder("Size:" + size + " [");
Node curr = head.getNext();
boolean isFirst = true;
while(curr != null) {
E elem = curr.getItem();
if (isFirst) {
isFirst = false;
}
else {
result.append(", ");
}
result.append(elem.toString());
curr = curr.getNext();
}
return result + "]";
}
}
NODE
public class Node {
/**
* Node data.
*/
private E item;
/**
* Reference to next node in the list.
*/
private Node next;
/**
* Constructor, creating node with given data inside and null next reference.
* @param obj node data
*/
public Node(E obj) {
this.item = obj;
next = null;
}
/**
* Setter for item field.
* @param obj data to set
*/
public void setItem(E obj) {
this.item = obj;
}
/**
* Setter for next field.
* @param temp next reference to set
*/
public void setNext (Node temp) {
this.next = temp;
}
/**
* Getter for item data.
* @return item field value
*/
public E getItem() {
return item;
}
/**
* Getter for next field.
* @return next field value
*/
public Node getNext() {
return next;
}
/**
* Overridden toString method.
* @return string representation of the node
*/
@Override
public String toString() {
return "[Item: " + item.toString() + "]";
}
}