Implement Linked List and Nodes in Java Assignment Solution
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a program to implement linked list and nodes in java language.
Requirements and Specifications
Assignment
In this assignment you will implement a singly linked list very similar to the one described in detail in chapter 16. Your task is to implement your own LinkedList class. Do NOT to use any class from the Java Collections Framework (do not import anything from java.util except exceptions).
The linked list that you will implement is a variation briefly described on page 1013 that uses a dummy head node, as shown in the following figure:
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() + "]";
}
}
Similar Samples
Explore our sample programming homework solutions at ProgrammingHomeworkHelp.com to witness our expertise firsthand. From introductory exercises to advanced projects in Java, Python, C++, and more, our samples exemplify precision and clarity. Each solution is crafted to showcase our commitment to excellence in programming education. Dive in and discover how we can assist you in mastering your programming assignments.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java