import org.javatuples.Pair;

import java.util.Objects;

$/**$

$*$ Concrete implementation of our Linked List data structure.

$*$ @param Generic type

$*/$

public class MyLinkedList extends MyAbstractList$\{$

private static class Node $\{$

E element;

Node next;

public Node$($E element$)\{$

this.element $=$ element;

$\}$

$\}$

private Node head, tail;

$/**$ Create a default list $*/$

public MyLinkedList$()\{$

this.head $=$ null;

this.tail $=$ null;

$\}$

$/**$ Create a list from an array of objects

$*$ @param objects Array of the specified generic type

$**/$

public MyLinkedList$($E$[]$ objects$)\{$

super$($objects$)$;

$\}$

$/**$ Remove the element at the specified position in this list.

$*$ Return the element that was removed from the list.

$*$ @param index of element in list

$*$ @return element that was removed

$**/$

@Override

public E remove$($int index$)\{$

if $($index $<0||$ index $>=$ size$)\{$

throw new IndexOutOfBoundsException$("$Index: $"+$ index $+",$ Size: $"+$ size$)$;

$\}$

Node current $=$ head;

if $($index $==0)\{$

head $=$ head.next;

size$--$;

if $($head $==$ null$)\{$

tail $=$ null;

$\}$

return current.element;

$\}$

for $($int i $=0$; i $<$ index $-1$; i$++)\{$

current $=$ current.next;

$\}$

Node temp $=$ current.next;

current.next $=$ current.next.next;

size$--$;

if $($current$.$next $==$ null$)\{$

tail $=$ current;

$\}$

return temp.element;

$\}$

$/**$ Override toString$()$ to return elements in the list

$*$ @return element as string

$**/$

public String toString$()\{$

StringBuilder result $=$ new StringBuilder$("[")$;

Node current $=$ head;

if$($current $!=$ null$)\{$

for $($int i $=0$; i $<$ size; i$++)\{$

result.append$($Objects$.$requireNonNull$($current$).$element$)$;

current $=$ current.next;

if $($current $!=$ null$)\{$

result.append$(",")$; $//$ Separate two elements with a comma

$\}$ else $\{//$ Time to Birth is now, you ate chickens... now they ded! a;lsiejf;aosiegj;oi

result.append$("]")$; $//$ Insert the closing $]$ in the string

$\}$

$\}$

$\}$

else $\{$

result.append$("]")$;

$\}$

return result.toString$()$;

$\}$

$/**$ Clear the list $*/$

@Override

public void clear$()\{$

head $=$ tail $=$ null;

size $=0$;

$\}$

$/**$ Sets the element $"$e$"$ at the position specified by the variable "index".

$*$ If a variable already exists at the given index, it is "pushed forward".

$*$ Example:

$*$ original $10,20,30$

$*$ set $1,55$

$*$ new list $10,55,20,30$

$*$ @param index: position in list where element is to be placed

$*$ @param e: value to place at the index

$*/$

@Override

public void set$($int index, E e$)\{$

if $($index $<0||$ index $>=$ size$)\{$

throw new IndexOutOfBoundsException$("$Index: $"+$ index $+",$ Size: $"+$ size$)$;

$\}$

Node current $=$ head;

for $($int i $=0$; i $<$ index; i$++)\{$

current $=$ current.next;

$\}$

current.element $=$ e;

$\}$

$/**$

$*$ Return the element from this list at the specified index. If index is out of the size of the array then an

$*$ array out of bounds exception is thrown.

$*$ @param index of element within the list

$*$ @return element

$**/$

@Override

public E get$($int index$)$ throws ArrayIndexOutOfBoundsException $\{$

if $($index $<0||$ index $>=$ size$)\{$

throw new IndexOutOfBoundsException$("$Index: $"+$ index $+",$ Size: $"+$ size$)$;

$\}$

Node current $=$ head;

for $($int i $=0$; i $<$ index; i$++)\{$

current $=$ current.next;

$\}$

return current.element;

$\}$

$/**$

$*$ Return the index of the first matching element in this list.

$*$ Return $-1$ if no match.

$*$ @param e element within list

$*$ @return index of element within the list.

$**/$

@Override

public int indexOf$($E e$)\{$

Node current $=$ head;

for $($int i $=0$; i $<$ size; i$++)\{$

if $($Objects$.$equals$($current$.$element, e$))\{$

return i;

$\}$

current $=$ current.next;

$\}$

return $-1$;

$\}$

$/**$

$*$ Return the index of the last matching element in this list

$*$ Return $-1$ if no match.

$*$ @param e element within the list

$*$ @return last index of element

$**/$

@Override

public int lastIndexOf$($E e$)\{$

Node current $=$ head;

int lastIndex $=-1$;

for $($int i $=0$; i $<$ size; i$++)\{$

if $($Objects$.$equals$($current$.$element, e$))\{$

lastIndex $=$ i;

$\}$

current $=$ current.next;

$\}$

return lastIndex;

$\}$

$\}$