cover picture cover picture


Homework 3

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


This Homework Is Due By 11:59 PM on March 1, 2015

  1. Implementation: (15 Points)

    In lecture, we discussed two implementations of a list. An array based list implementation, and a linked list implemetation. Write Java programs that implement the ListInterface specified in ListInterface.java for both list types. For your array based implementation, you can assume that the list will not contain more than 100,000 elements.

  2. Test Cases: (20 Points)

    You must also write a driver program that demonstrates that both list types work. Your driver should use the following test cases for each list type:

    1. Starting with an empty list, use the addSorted(Object obj) method to add java.lang.Integer objects representing the odd numbers (1 <= n <= 99,999) to the list.
    2. Starting with a list containing the odd numbers less than 100,000, use the addSorted method to add java.lang.Integer objects representing the even numbers (2 <= n <= 100,000) to the list.
    3. Starting with an empty list, use the add(Object obj) method to add 100,000 java.lang.Object objects to the list.
    4. Starting with an empty list, use the add(Object obj, int index) method to add 100,000 java.lang.Object objects to the list, all at index = 0.
    5. Starting with a complete list containing 100,000 java.lang.Integer objects representing all the numbers (1 <= n <= 100,000); remove all the even numbers by repeatedly calling the remove(int index) method. Remove the even numbers starting with 2, then 4, then 6, ....
    6. Starting with a complete list containing 100,000 java.lang.Integer objects representing all the numbers (1 <= n <= 100,000); remove all the odd numbers by repeatedly calling the remove(int index) method. Remove the odd numbers starting with 99,999, then 99,997, then 99,995, ....

    Run each test 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each test case. You must use the removeAll() method between test cases to clear the list of all elements.

  3. Analysis: (15 Points)

    Using the tables you created, answer the following questions using complete sentences:

    1. Discuss difference in run times between the array based list and the linked list for all the test cases.
    2. Are the run times ever similar for both the array based list and the linked lists? Why or why not.
    3. In which test cases is the array based list faster than the linked list? Please explain the reason why or why not.
    4. Which of the two implementations is more efficient as far as storage, please explain. You can monitor memory usage using the java.lang.Runtime class.

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project. The analysis must be a typed Microsoft Word file. No other forms of submission will be accepted.