CMP 338, Data Structures & Algorithms, Fall 2015

Implementation:

In lecture, we discussed two implementations of a list. An array based list implementation, and a linked list implemetation. In this assignment, you are going to implement the following ListInterface for both an array based list. and a linked list. The interface is specified in ListInterface.java.
1. Array Based List Class:
  
  Write a Java program that implements the ListInterface as an array based list Your implementation must be in a class named ArrayBasedList. You can assume that the list will not contain more than 10,000 elements.
2. Linked List Class:
  
  Write a Java program that implements the ListInterface as a linked list Your implementation must be in a class named LinkedList.

Test Cases:

You must also write a driver program that demonstrates that both list types work properly. Your driver should use the following test cases, please note that all the elements being added and removed from the lists must be instances of the Integer class in Java:
1. Starting with an empty list, use the addSorted(I obj) method to add java.lang.Integer objects representing the odd numbers (1 ≤ n ≤ 9,999) to the list.
2. Starting with a list containing the odd numbers less than 10,000, use the addSorted(I obj) method to add java.lang.Integer objects representing the even numbers (2 ≤ n ≤ 10,000) to the list.
3. Starting with an empty list, use the add(I obj) method to add 10,000 java.lang.Integer objects to the list.
4. Starting with an empty list, use the add(Object obj, int index) method to add 10,000 java.lang.Integer objects to the list, all at index = 0.
5. Starting with a complete list containing 10,000 java.lang.Integer objects representing all the numbers (1 ≤ n ≤ 10,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 10,000 java.lang.Integer objects representing all the numbers (1 ≤ n ≤ 10,000); 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 9,995, ....

Driver Class:

Your driver must be in a class named Driver. Your Driver class must implement the following:
1. ListType enum
2. TestType enum
3. All the methods specified in the Driver documentation

Linked list node Class:

Your linked list node class must be named LinkedListNode. and it must implement all the methods specified in the LinkedListNode documentation.

Statistics Class:

In addition to printing the run times for each test case, you will have to also display the average time and the standard deviation. You will have a class named Statistics. and it must implement all the methods specified in the Statistics documentation.

Analysis:

Using the tables you created by running Driver.main(), copy your results into a Microsoft Word document and answer the following questions using complete sentences:
1. Discuss the difference in run times between the array based list and the linked list for all the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.
2. Are the run times ever similar for both the array based list and the linked lists? Why or why not? Be as specific as possible.
3. In which test cases is the array based list faster than the linked list? Please explain the reason why or why not. Be as specific as possible.

Homework 3