Homework 3

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Spring 2022

This Homework Is Due By 11:59 PM on Wednesday March 9, 2022

Overview

In this assignment you will be implementing the List Abstract Data Type (ADT) using two different implementations:

1. Array Based List
2. Linked List

In addition, you will also be writing a driver to test your List implementations and you will be measuring the test times and memory usage of each test case.

You will also be using the TestTimes class that you created for Homework 1.

Finally, you will be analysing and comparing the performance of the test cases on both the Array Based List and the Linked List implementations.

Details

1. TestTimes zyLab

   You will copy the TestTimes class that you created in Homework 1 to the project you are using for this assignment. Please note that you will also have to re-submit TestTimes.java to zyBooks in the TestTimes zyLab

2. ArrayBasedList zyLab

   You will write the ArrayBasedList.java class which will implement the List Interface. The interface may be downloaded from here .

3. LinkedList zyLab

   You will write the LinkedList.java class which will implement the List Interface. The interface may be downloaded from here .

4. LinkedListNode zyLab

   Your will write the LinkedListNode. Please see the Linked List Node Documentation for all the methods you will need.

5. ListDriver zyLab

   You will write the ListDriver.java class which will implement the ListDriver Interface. The interface may be downloaded from here .

   Please note that, in addition to implementing the ListDriverInterface, you are also required to write your own public static main(String[] args) method in ListDriver.java that performs all of the required tests as specified below.

Required Tests

Definitions:

You will test two list implementations with different tests. You will run all tests on both implementations of the ListInterface. The ListDriverInterface includes the definitions of two enums:

1. ListDriverInterface.ListType

   This enum defines all the possible list types that you will will implement. They are:

   ArrayBasedList

   The array based implementation of the ListInterface.

   LinkedList

   The linked implementation of the ListInterface.

2. ListDriverInterface.TestType

   All the elements being added and removed from the lists must be instances of the Integer class.

   This enum defines all the tests that you will be performing. The tests are:

   ListDriverInterface.TestType.AddSortedOdd:

   You will initialize your list to be empty. The test case will use the addSorted(I element) method to add java.lang.Integer objects representing the odd numbers (1 ≤ n ≤ 9,999) to the list.

   ListDriverInterface.TestType.AddSortedEven:

   You will initialize your list to contain the odd numbers less than 10,000. Your test case will use the addSorted(I element) method to add java.lang.Integer objects representing the even numbers (2 ≤ n ≤ 10,000) to the list.

   ListDriverInterface.TestType.AddAll:

   You will initialize your list to be empty. The test case will use the add(I element) method to add 10,000 java.lang.Integer objects to the list.

   ListDriverInterface.TestType.AddAllAtIndexZero:

   You will initialize your list to be empty. The test case will use the add(I element, int index) method to add 10,000 java.lang.Integer objects to the list, all at index = 0.

   ListDriverInterface.TestType.RemoveAllEven:

   You will initialize your list to contain 10,000 java.lang.Integer objects representing all the numbers (1 ≤ n ≤ 10,000). The test case will remove all the even numbers by repeatedly calling the remove(int index) method. Remove the even numbers starting with 2, then 4, then 6, ....

   ListDriverInterface.TestType.RemoveAllOdd:

   You will initialize your list to contain 10,000 java.lang.Integer objects representing all the numbers (1 ≤ n ≤ 10,000). The test case will remove all the odd numbers by repeatedly calling the remove(int index) method. Remove the odd numbers starting with 9,999, then 9,997, then 9995, ....

Output From Driver Main Method

Please note that, in addition to implementing the ListDriverInterface, you are also required to write your own public static main(String[] args) method in ListDriver.java.

Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:

For each call to the runTestCase() method your main() method will print out a table with the following output for the Array Based List and the Linked List implementations:

Please note that the test times and the average are in Seconds and the memory usage is in Mega Bytes. You will need to make the necessary conversions.

For each call to the runTestCase() method your main() method will print out a table with the following output for the Array Based List and the Linked List implementations:

Running test = Test Case Name
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList
LinkedList
    

Sample Output

Running test = AddSortedOdd
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.02307  0.01399  0.01030  0.01123  0.01072  0.01021  0.00992  0.01120  0.01037  0.01075  0.01218    7.73121  
LinkedList      0.04180  0.03222  0.02897  0.02790  0.02673  0.02876  0.02632  0.02728  0.03080  0.02582  0.02966    2.92120



Running test = AddSortedEven
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.05055  0.03056  0.03102  0.02940  0.02806  0.03170  0.03088  0.02807  0.02978  0.02852  0.03186    24.36255
LinkedList      0.09666  0.08369  0.08281  0.08503  0.08833  0.08474  0.09145  0.08415  0.09071  0.07999  0.08675     5.47630



Running test = AddAll
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.00099  0.00077  0.00053  0.00056  0.00059  0.00066  0.00064  0.00061  0.00060  0.00062  0.00066    21.80157
LinkedList      0.00035  0.00010  0.00010  0.00010  0.00010  0.00010  0.00010  0.00010  0.00010  0.00010  0.00012     5.47639



Running test = AddAllAtIndexZero
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.03448  0.03356  0.03297  0.03371  0.03378  0.03390  0.03310  0.03369  0.03337  0.03381  0.03364    21.80177
LinkedList      0.00106  0.00027  0.00026  0.00022  0.00022  0.00022  0.00016  0.00098  0.00025  0.00023  0.00039     4.19656



Running test = RemoveAllEven
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.02156  0.01578  0.01456  0.01461  0.01493  0.01546  0.01498  0.01487  0.01544  0.01445  0.01566    23.08179
LinkedList      0.03528  0.03296  0.02743  0.02793  0.03115  0.02535  0.02531  0.03454  0.03125  0.02417  0.02954     4.19664



Running test = RemoveAllOdd
                 Run 1    Run 2    Run 3    Run 4    Run 5    Run 6    Run 7    Run 8    Run 9    Run 10  Average  Memory Usage
                Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds  Seconds   Mega Bytes
                -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  -------  ------------
ArrayBasedList  0.00825  0.00819  0.00812  0.00753  0.00744  0.00779  0.00768  0.00736  0.00714  0.00748  0.00770    21.80184
LinkedList      0.04604  0.04306  0.04110  0.04615  0.04815  0.04794  0.03827  0.04334  0.04164  0.04790  0.04436     4.19664
  

Analysis:

Using the tables you created by running ListDriver.main(), copy your results and your graphs into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

1. Create graphs from the test times you measured.
2. Discuss the difference in run times between the array based list and the linked list for all the test cases. Explain the reason(s) why the test times are different between the implementations. Did the results match your expectations? Why or why not? Be as specific as possible.
3. Are the run times ever similar for both the array based list and the linked lists? Explain the reason(s) why the test times in both implementations are similar. Did the results match your expectations? Why or why not? Be as specific as possible.

Please submit the completed assignment in your zyBooks , in the Homework 3 Chapter.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted. Please include your graphs in the same file as your analysis.