×
Samples Blogs Make Payment About Us Reviews 4.9/5 Order Now

Implement Linked List and Nodes in Java Assignment Solution

June 25, 2024
Jessica Miller
Jessica Miller
🇺🇸 United States
Java
Jessica Miller is a seasoned programmer with a master's degree in software engineering from Stanford University. Having completed over 700 Java assignments, Jessica excels in implementing sorting algorithms, multi-dimensional arrays, and efficient array operations. Her deep understanding of complex programming concepts and hands-on experience make her a valuable resource for students seeking high-quality homework help.
Key Topics
  • Instructions
    • Objective
  • Requirements and Specifications
Tip of the day
Use modular coding in Verilog assignments by breaking the design into smaller modules. This improves readability, simplifies debugging, and allows for easier testing and reuse of code components in larger designs.
News
In 2024, Visual Studio Code now offers enhanced GitHub Copilot integration for faster, while PyCharm has improved debugging and testing tools, making it ideal for Python students​

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:

Program-to-linked-list-and-node-in-java

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.