In these programming questions you wi evaluate two implementations of List interface in terms of their e for different operations List interface is an ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list. The List interface provides four methods for index access to list elements, two methods to search for a specific object, and two methods to efficiently insert and remove multiple elements at an arbitrary location in the list. Note that the speed of these operations may depend on the implementation (e.g. Array or LinkedList)

You are required to write two implementations of List interface, one that uses array, and one that uses doubly-linked list. Then, you will have to test the performance of several operations when using your implementations.

Question 1: Implement the following methods in the two implementations (called MyArrayList and MyLinkedList) of List interface: l Appends the specified element to the end of this list

Boolean add (E e)

void add(int index, E element)

E remove (int index)

Boolean remove (Object o)

String tostring)

int size() /

Define your classes to be generics. The array implementation should have dynamie resizing (double the size when growing and halve the size when less than 25 % of the capacity is used); and the linked list implementation should use doubly linked list. Also, the behavior of these methods should be equivalent to that of Java Standard Library's classes Arraylist or LinkedList. Please refer to the corresponding descriptions online?

For the rest of the methods of te List interface, you may just throw an exception: public type someUnneededMethod throw new UnsupportedoperationException)

Write your driver class ListTester. Use both of your list implementations and compare them to the corresponding Java library implementations (ArrayList and LinkedList) For numbers N= {10, 100, 1000, 10000, 100000, 1000000) a) Starting with empty lists of Number-s; measure how long it takes to insert N integer numbers (int, or Integer) with random values ranging from 0 to 2N into the lists, when inserting them at the beginning, at the end, and into a random location of the list (use indices to indicate where to do the insertion (e.g list.add (randomLocation, number)).