import java.util.NoSuchElementException; * A linked implementation of a list. * A LinkedList is similar to an ArrayList except that the elements * are stored in nodes linked together and not in an array * @param type of elements stored in the list public class LinkedList { // The list is made up of Node objects private class Node { E element; 1/ element stored in this node Node next; // link to next node in the list private Node head; // link to the first node in the list private Node tail; // link to the last node in the list private int size; // number of elements stored in the list * Constructor - creates an empty list */ public LinkedList() { head = tail = null; size = 0; } list. /** * Adds the given element to the end of the * @param elem element to add */ public void add(E elem) { Node n = new Node(); n.element = elem; if(isEmpty()) { head = tail = n; } else { tail.next = n; tail = n; } size++; } /** * Removes the first element from the list. * @return first element * @throws NoSuchelementException if list is empty public E removeFirst() { if (isEmpty() throw new NoSuchelementException(); E elem = head.element; head = head.next; if (head == null) tail = null; size--; return elem; } * Removes the first occurrence of the given element from the list. * @param elem element to remove @throws NoSuchElementException if element not in the list public void remove(E elem) { Node walker = head; Node follower = null; while(walker != null && I walker.element.equals(elem)) { follower = walker; walker = walker.next; if (walker == null) // elem not in list throw new NoSuchElementException(); else if (walker == head) { // elem is head element head = head.next; if (head == null) tail element walker.next; is tail tail = null; } else { // elem is a middle or follower.next = if (walker == tail) // elem tail = follower; } size--; } * Returns the first element in the list. * @return first element * @throws NoSuchElementException if list is empty public E first() { if (isEmpty() throw new NoSuchelementException(); return head.element; } * Returns the last element in the list. * @return last element * @throws NoSuchElementException if list is empty */ public E last() { if (isEmpty() throw new NoSuchElementException(); return tail.element; } * Returns true if the given element is in the list. * @param elem element to find @return true if element in the list public boolean contains (E elem) { Node walker - head; while(walker != null) { return true; } walker = walker.next; } return false; } public boolean isEmpty() { return size==0; } public int size() { return size; } @Override public String toString() { String s = ""; Node walker = head; while(walker != null) { s += walker.element+" walker = walker.next; } return s; } } Double the links, double the fun! In this lab, you will modify the LinkedList.java class so that it is a doubly-linked list. Start by downloading the newest version of LinkedList.java from Canvas. Note: Do not create a new class. You are modifying the LinkedList.java class. Task 1: Modify the Node class inside LinkedList so that it includes a link to the previous node. (Note that I have already changed "link" to "next" throughout the class.) Task 2: Modify the add() and removeFirst() methods so that they update all the relevant next and previous links. The add() method adds a new node to the end of the list. The removeFirst method removes the node at the head of the list. Task 3: Add the removeLast() method that removes the tail element from the list. This must be a constant time, O(1), method. (We did this in class.) Task 4: Add the printReverse() method that prints all of the elements in the list, starting with the tail. (You can use this method to verify that your other methods are correct since this method relies on the previous links.) Task 5: Modify the remove() method so that it updates the relevant next and previous links. You only need to update the "element is head element" and "element is a middle or tail element" cases in the method. TEST! Write your own main method to test that all of the methods modified in this lab still work correctly