In this assignment, you will have to write a doubly-linkedlist-based partial implementation of the List interface. Unlike theexisting java.util.LinkedList, your implementation is to optimizethe operations involving the middle positions of the lists– defined as ?list size / 2?, enabling constant timeoperations involving not only the first and the last positions ofthe list, but also the middle ones as well.

Implement the following public methods in yourimplementation of the List interface, calledMidLinkedList:

1. boolean add(E e)

2. void add(int index, E element)

3. E remove(int index)

4. E get (int index)

5. int size()

6. void clear()

7. String toString() (see Java API: AbstractCollection2)

One public constructor should exist in your implementation: onethat takes no parameters and creates an empty list when the classis instantiated.

The class should use generics. The behaviour of the methods inyour implementation should be equivalent to that of JavaStandard Library’s classes (e.g., ArrayList; please refer to theclass API online). For the methods of the interface that you do notneed to implement, you may either leave them empty or throw anexception

public type someUnneededMethod() {

throw new UnsupportedOperationException();

}

Of course, you are free to implement any private or protectedmethods and classes as you see fit. However, the methods mentionedabove (or the ones present in the interface, or in the class’superclasses) are the only public methods your class shouldcontain. Furthermore, your code should not have any side effects,such as printing to the console.

Create some tester class and use it with your listimplementation to investigate its running time complexity as thenumber of items in the list increases and as you vary the indicesof the elements you are trying to operate on. Try measuring therunning time when inserting (deleting, getting…) 10, 100, 1000 …1,000,000 elements at various positions. Confirm that the runningtime follows the expected behaviour for add, remove, and for othermethods.

NOTES

1. Do not use package-s in your project (put yourclasses in the default package). Using packages will cost you a 10% deduction from the assignment mark.

2. Some aspects of your code will be marked automatically (e.g.,how it handles boundary cases and error conditions), using a customtester class. It is also imperative you test your classes. If anyof the java files that you submit do not compile, the wholesubmission will be given a grade of zero, regardless of how trivialthe compiler error is. The code you submit should compile using

javac *.java

command in either Windows, Linux, or MacOS.

3. Your code should include Javadoc comments.

4. Using any java.util implementations of Collection3 or Map4interfaces is not allowed (importing the java.util.Listinterface is of course fine).

Sample Code (AS EXAMPLE ONLY OF HOW CODE SHOULD LOOKLIKE PLEASE TRY TO IMPLEMENT BETTER CODE):

import java.util.List;

public class MidLinkedList implements List{

/* YOUR CODE */

public static class Node{

/* YOUR CODE */

}

/* toStringimplementation to print just the data */

@Override

public StringtoString() {

/*YOUR CODE */

}

}

@Override

public boolean contains(Object o) {

// TODO Auto-generated method stub

return false;

}

@Override

public Iterator iterator() {

// TODO Auto-generated method stub

return null;

}

@Override

public T[] toArray(T[] a) {

// TODO Auto-generated method stub

return null;

}

@Override

public boolean add(E e) {

// TODO Auto-generated method stub

add (size, e);

return true;

}

@Override

public boolean remove(Object o) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean containsAll(Collection c) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean addAll(Collection c) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean addAll(int index, Collectionc) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean removeAll(Collection c) {

// TODO Auto-generated method stub

return false;

}

@Override

public boolean retainAll(Collection c) {

// TODO Auto-generated method stub

return false;

}

@Override

public void clear() {

// TODO Auto-generated method stub

}

@Override

public E get(int index) {

// TODO Auto-generated method stub

return null;

}

@Override

public E set(int index, E element) {

// TODO Auto-generated method stub

return null;

}

@Override

public void add(int index, E element) {

// TODO Auto-generated method stub

}

@Override

public E remove(int index) {

// TODO Auto-generated method stub

return null;

}

@Override

public int indexOf(Object o) {

// TODO Auto-generated method stub

return 0;

}

@Override

public int lastIndexOf(Object o) {

// TODO Auto-generated method stub

return 0;

}

@Override

public ListIterator listIterator() {

// TODO Auto-generated method stub

return null;

}

@Override

public ListIterator listIterator(int index) {

// TODO Auto-generated method stub

return null;

}

@Override

public List subList(int fromIndex, int toIndex) {

// TODO Auto-generated method stub

return null;

}