Complete the following exercise and submit electronically in the assignments folder on eLearn as an IntelliJ Project Zip the entire folder not just the source files in MyCanvas. Please refer the course Calendar for the exact date and time of the submission. This assignment is to be completed individually. Background You are to complete the starting code that has been provided for a SortedLinkedList that will store a collection of items and maintain the order of the items at all times. You will need to add functionality for the following methods: add remove toString In case of the add method, the elements must be added in sorted order. When you add the following words in this order [Bob, Carol, Aaron, Alex, Zaphod], the list when printed using the toString method will appear as [Aaron, Alex, Bob, Carol, Zaphod]. You may not call any sort algorithm to achieve this result. Your goal is to ensure that the list is always in a sorted state. With the remove method, the element specified must be removed from the list and the current order maintained. The class provided has been provided as a generic class. It will work with any object data type class that is Comparable. In your main method you must demonstrate that this works using two different data types that add elements in random order to the list. The sorting order in all cases will be ascending alphabetic order ('A' at the top, lowest integer at the top, etc...). Once you have demonstrated that your class can handle two different data types (make one of them String), you will need to compare the performance of the class against the standard java ArrayList class. To achieve equivalent functionality with the ArrayList, add each name to the list and then call Collections.sort method after each each item is added (ythis must be placed in the loop that is adding the items. This will ensure that we are comparing the same functionality in both classes (always sorted). The main program as provided will read names from a text file (baby names) and place the content into an array. It is suggested you use this data for comparison purposes for the String data type. Suggested Steps: 1. Create an add method for the SortedLinkedList class 2. Test the add method from main to ensure elements are added in sorted order. To do this you will need to complete the toString method. 3. Create a remove method for the SortedLinkedList class 4. Test the remove method from main to ensure elements are removed from the list and that after removal the list is still in sorted order. 5. Add a Discussion (in a comment) to the top of the file that contains your main method discussing the results obtained. Answer each of the following questions: o Do you notice any significant performance difference between the SortedLinkedList and the ArrayList classes when adding items? Explain the differences using Big O notation for the different algorithms. o Do you notice any significant performance difference between these two collections when removing items? Explain the differences using Big O notation for the different algorithms. o When would you choose to use a SortedLinkedList over an ArrayList based on the results of this assignment? Marking Scheme Program structure Comments, follows best programming practices - 20% Completion of LinkedList Requirements 30% Print timing neatly in a table to screen for both adding and removing items using the provided ArrayList and SortedLinkedList classes. Print a small set of results to show that the sorting works 25% Performance comparison write-up as a comment at the top of the code. 25%

Assignment4.java

package Comp10205_lab4; import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.Collections; import java.util.Random; import java.util.Scanner; public class Assignment4 { public static void main(String[] args) { final int NUMBER_OF_NAMES = 18756; final String filename = "resources/bnames.txt"; final String[] names = new String[NUMBER_OF_NAMES]; // May be useful for selecting random words to remove Random random = new Random(); // Read in all of the names try { Scanner fin = new Scanner(new File(filename)); for (int i=0; i linkedList_String = new SortedLinkedList<>(); long start = System.nanoTime(); for (int i=0; i arrayList_String = new ArrayList<>();

}

bnames.txt

Davi Inaya Theodosia Aairah Layali Neeya Amyri Maddox Calynn Milaya Maecyn Saleen Maizee Azani Yamilet Gamila Joycelynn Sinclair Asna Reina Maire Remee Avariella Foster Peniel Dezarae Sonika Yu Landrey Deethya Vicky Tilden Amyracle Annalise Alee Mareya Stella Noemie Tansy Mikaila Kataleena Anica Hassanatou Fadeelah Korrie Ilynn Diora Geonna Karthika Persephanie Ladan Alzain Zhoemi Kenedy

Emiah Marianna Nadirah Amisha Lillyn Aunesti Brayli Arieal Annarae Silvia Hala Demiana Georgianna Sophiea Kentlee Jlayah Salma Teigen Sabreen Jeliyah Amyra Mackinley Ayak Areebah Blythe Amra Miagrace Lillyana Keelie

SortedLinkedList.java

{ /** * The Node class stores a list element and a reference to the next node. */ private final class Node { T value; Node next; /** * Constructor. * @param val The element to store in the node. * @param n The reference to the successor node. */ Node(T val, Node n) { value = val; next = n; } /** * Constructor. * * @param val The element to store in the node. */ Node(T val) { // Call the other (sister) constructor. this(val, null); } } private Node first; // list head /** * Constructor. */ public SortedLinkedList() { first = null; } /** * The isEmpty method checks to see if the list is empty. * * @return true if list is empty, false otherwise. */ public boolean isEmpty() { return first == null; } /** * The size method returns the length of the list. * @return The number of elements in the list. */ public int size() { int count = 0; Node p = first; while (p != null) { // There is an element at p count++; p = p.next; } return count; } /** * The add method adds an element at a position. * @param element The element to add to the list in sorted order. */ public void add(T element) { } /** * The toString method computes the string representation of the list. * @return The string form of the list. */ public String toString() { String listOfItems = ""; // TODO: Iterate through the list and append items to end of listOfItems return listOfItems; } /** * The remove method removes an element. * @param element The element to remove. * @return true if the remove succeeded, false otherwise. */ public boolean remove(T element) { return false; } }