Project $3$ involves implementing list structures in two different data structures: LinkedList and ArrayList. In addition, you will need to implement other operations on both those data structures. You will then compare the time complexities of a select few list methods when implemented as an ArrayList vs$.$ a LinkedList in analysis.txt or analysis.pdf $($either is acceptable$).$

IMPORTANT: Specifications for each method can be found in List.java, which is a Java interface.

The following $17$ methods should be implemented in for both ArrayList and LinkedList:

boolean add$($T element$)$

boolean add$($int index, T element$)$

void clear$()$

T get$($int index$)$

int indexOf$($T element$)$

boolean isEmpty$()$

int size$()$

void sort$()$

T remove$($int index$)$

void reverse$()$ Note: You must reverse the list IN$-$PLACE $($no intermediate data structures$).$

void removeDuplicates$()$

void intersect$($List otherList$)$

void merge$($List list$)$

T getMin$()$

T getMax$()$

String toString$()$

boolean isSorted$()$

Optimizations $(6$ Points$)$

The following methods need to be optimized in your LinkedList and ArrayList classes. If isSorted is true, then there should be an optimized case for these functions:

int indexOf$($T element$)$

void sort$()$

T getMax$()$

Hint: Use a tail pointer in your LinkedList implementation