1. Complete the addlast method 2. Include the Big O Notation of the method in the textbox provided 3. How would you go about testing the correntness of the method? Write them down in the textbox. public class Main{ public static void main(String [] argv){ System.out.println("Constructor a palindrome of an even number of elements:"); DoublyLinkedList list = new DoublyLinkedList<>(); list.addFirst("C"); list.addFirst("B"); list.addLast("B"); list.addFirst("A"); list.addLast("A"); System.out.println(list.toString()); System.out.println("Is the list a palindrome? " + list.isPalindrome()); list.removeFirst(); System.out.println("After removing the first element, we have "); System.out.println(list.toString()); System.out.println("Is the list a palindrome? " + list.isPalindrome()); } } class DoublyLinkedList { private DoublyLinkedNode first; private DoublyLinkedNode last; private int numNodes; public DoublyLinkedList() { first = null; last = null; numNodes = 0; } public void addLast(T element) { //Create a DoublyLinkedNode node DoublyLinkedNode temp = new DoublyLinkedNode<>(element); if (numNodes == 0) { //Doubly linked list is empty first = temp; last = temp; } else {//Doubly linked list is not empty temp.setPrev(last); last.setNext(temp); last = temp; } numNodes++; } public void addFirst(T element) { //TODO1 create a DoublyLinkedNode node if (numNodes == 0) { //TODO2 doubly linked list is empty } else {//TODO3 doubly linked list is not empty } numNodes++; } public void removeFirst() { DoublyLinkedNode temp = first; if (numNodes == 1) { //TODO1 doubly linked list consists of one node } else if (numNodes > 1) { //TODO2 doubly linked list consists of more than one node } } public boolean isEmpty() { return (numNodes == 0); } public int size() { return numNodes; } public String toString(){ DoublyLinkedNode temp = first; String result = ""; while (temp != null) { result += temp.getElement() + " -> "; temp = temp.getNext(); } return result; } public boolean isPalindrome(){ DoublyLinkedNode p = first; DoublyLinkedNode q = last; while ((p != null) && (q != null) && ((p != q) && p.getPrev() != q) ){ // Compare data in nodes referred by p and q if (p.getElement().compareTo(q.getElement()) != 0) return false; // TODO1 Move the reference of p to its next node // TODO2 Move the reference of q to its previous node } return true; } } class DoublyLinkedNode { private DoublyLinkedNode next; private DoublyLinkedNode prev; private T element; /** * Default constructor creates an empty node */ public DoublyLinkedNode() { next = null; prev = null; element = null; } /** * Creates a node containing element * @param elem element to be stored */ public DoublyLinkedNode(T elem) { next = null; prev = null; element = elem; } /** * Gets the node that follows this one * @return next linear node */ public DoublyLinkedNode getNext() { return next; } /** * Sets the node that follows this one * @param n LinearNode to follow this one */ public void setNext(DoublyLinkedNode n) { next = n; } /** * Gets the node that is before this one * @return prev LinearNode */ public DoublyLinkedNode getPrev() { return prev; } /** * Sets the node that is before this one * @param p LinearNode to put before this one */ public void setPrev(DoublyLinkedNode p) { prev = p; } /** * Returns the element stored in this node * @return element stored in the node */ public T getElement() { return element; } public void setElement(T elem) { element = elem; } @Override public String toString() { return "{el=" + element + ", next=" + next + ", prev=" + prev + "}"; } }