COMP – 10205 – Data Structure and Algorithm

You are to complete the starting code that has been provided for aSortedLinkedListthat 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<T> 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<T> and the ArrayList<T> 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?