CODE IN JAVA

'Here is the code:

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 + "}";

}

}

Doubly linked lists are a linear data structure with wide applications. Let us practice the addFirst(). removeFirst(), and isPalindrome() method. Head NULL | E NULL Tail If you follow the instruction and download the start code (Main.java) before you start the exam, please upload the downloaded file in the Repl.it browser tab: 1) in the files plane of Repl.it, click in the three vertical dots: 2) select the first option upload file and select the Main.java file that you downloaded: 3) read the code and fill missing codes (refer to TODO comments). You could also download the Main Java and open it in Repl.it. Considering the diversity on your side, we also attach the start code Main.file in the end of the question. The Repl.it could make your coding easy. If your machine doesn't allow you to use Repl.it, please read the attached start code and finish four tasks in the question. Task 1. (5 points) Complete the addFirst() method. Hint: 1. Consider edge case that doubly linked list is empty. Draw an empty doubly linked list in your sketchbook and check how to insert a new element. Write statements for the edge case. 2. Consider the case that doubly linked list includes at least one node. Draw a three-node doubly linked list in your sketchbook and check how to insert a new element. Write statements for the case. 3. Do not forget to reflect the change of the linked list size. Task 2. (5 points) Complete the removeFirst() method. (Optional) Task 3. (5 points) Complete the isPalindrome() method. Task4. (5 points) Write down the big O notation of the method addFirst() that you implemented in task 1. Task5. (5 points) Write down the big o notation of the method removeFirst() that you implemented in task 2. Task. (2 points) Write down the big o notation of the method is Palindromel) that you implemented in task 3. Task 7. (3 points) Write down your thoughts in testing the correctness of the method addFirst(). If you add JUnit code, 5 extra-credit could be added. Hint: what are its edge case(s), right case(s), and wrong case(s)? Submission: When you submit your answer for the question, please write down subquestion ID, answer. For programming question, you just need to write down your statements that help complete the program