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
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.
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:
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.
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.
Starting with an empty list, use the add(Object obj) method to add 100,000
java.lang.Object objects to the list.
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.
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, ....
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.
Analysis: (15 Points)
Using the tables you created, answer the following questions using complete sentences:
Discuss difference in run times between the array based list and the linked list for all
the test cases.
Are the run times ever similar for both the array based list and the linked lists? Why or why not.
In which test cases is the array based list faster than the linked list? Please explain the reason
why or why not.
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.