Task: Implementation of a List interface and two concrete subclasses: ArrayList and LinkedList.

The ADT of the List interface is given below:

public interface List {

public int size();

public boolean isEmpty();

public Object get(int index) throws OutRangeException;

public void set(int index, Object o) throws OutRangeException;

public void add(int index, Object o) throws OutRangeException;

public Object remove(int index) thorws OutRangeException;

}

Requirements:

Implement the ArrayList and LinkedList classes as well as the List

interface as we discussed in the lectures.

Your implementation has to follow the specification given. Any

other implementation (there are tons of List code on the

Internet) will not receive any credit. In particular

Your ArrayList class does not need to consider the array epansion case,

you can always assume the initial constructed array has sufficient space.

Data fields of ArrayList:

Object[] items;

int size;

Data fields of LinkedList:

Link head;

int size;

Link class has the following data field:

Object e;

Link next;

Test: write a performance comparison program to compare the performance

of the remove operation of the two list classes in running time. To do that,

you need to construct

a big ArrayList and a big LinkedList with a large number of elements in your test program, such as

10,000.

In the performance comparison test, try to do the removing from the tail until the list if empty.

Assume we initially have a list with 10,000 elements (in the test, you have to manually add

10,000 elements to the list though), first you remove the 10,000th element, followed by removing

the 9,999th element, then 9,998th, and so on, until you have an empty list.

Compare their running

time by recording the timestamps before and after the operation.

Demonstrate your result in your test program.

Submission:

Each student submits one copy of the source code: List.java, ArrayList.java, LinkedList.java, Link.java, OutRangeException.java and Test.java.

Create a folder and name it as your Linux user account, e.g., hwang_hw5, by the following command:

$ mkdir hwang_hw5

Copy all your source code to the above folder (clean your source code folder and remove all class files). Linux copy command is "cp filename destination_folder".

Compile a README file (in text format only, do not use Microsoft, use gedit instead) and provide the following:

Your name and CSUID

Compiling instruction

A sample test run (again in text)

Existing bug (things not finished)

Log in grail, go to the parent director of the folder you created, and run (suppose the your folder is "hwang")

turnin -c cis265w -p hw5 hwang_hw5

If there is no error message, your submission is successful.

Task: Implementation of a List interface and two concrete subclasses: Array List and Linked List The ADT of the List interface is given below publie interface List publie int sizet publie boolean isEeptyO public object get(int index) throws OutRangeException public void set(int index, object o) throws OutRangeException publie void add