- Download the attached classes (MyLinkedList.java and TestMyDoublyLinkedList.java) and add them to your project in Eclipse. Fix the package statement in each class to refer to your current package. ( codes are below)

- RenameMyLinkedListclasstoMyDoublyLinkedList(seeUsefulEclipseShortcutsbelow).

- At this point, Eclipse should show no syntax errors.

- Add or change the code in MyDoublyLinkedList so as to convert it to a doubly linked list. That is, you need to have and use two references for each node: next, pointing to the next node, and previous, pointing to the previous node. Comments are added to MyDoublyLinkedList beside the parts that need to be changed. Whenever you make a change, make sure that next and previousproperly point to the correct nodes or to null.

- Some comments ask you to improve the performance of your code usingprevious. Here, you have tothinkabouthowtheperformancecanbeimprovedknowingthateachnodepointstoboth thenext and the previous nodes. For example, if you want to get a reference to the second -to-last node, you wouldonlyneedtousetail.previousinsteadofhavingtotraversethelistfromheaduptothe node at size-2in case of singly linked lists.

- To improve the readability and maintainability of your code, try to use helper methods whenever appropriate. A method that you have to create is getNodeAt(int index) which returns a reference to a node at a given index. Again, you have to try to improve the performance of this method giventhatyou havebothnextandprevious.

- Testing:UsetheTestMyDoublyLinkedListclasstotestyourcode.Youshouldhaveanoutput similar to the one in the next page.

-------------------- MylinkedList---------------

package A8; public class MyLinkedList { private int size; private Node head, tail; // Constructors public MyLinkedList() { head = tail = null; } public MyLinkedList(E[] objects) { for (int i = 0; i < objects.length; i++) add(objects[i]); } // Methods //*** ADDING *** public void add(E e) { addLast(e); } public void addFirst(E e) { /** add code to set 'previous' [1 mark] */ Node newNode = new Node(e); // Create a new node if (tail == null) // if empty list head = tail = newNode; // new node is the only node in list else { newNode.next = head; // link the new node with the head head = newNode; // head points to the new node } size++; } public void addLast(E e) { /** add code to set 'previous' [1 mark]*/ Node newNode = new Node(e); // Create a new for element e if (tail == null) // if empty list head = tail = newNode; // new node is the only node in list else { tail.next = newNode; // Link the new with the last node tail = tail.next; // tail now points to the last node } size++; } public void add(int index, E e){/** add code to set 'previous' & to improve performance [2 marks] */ if (index < 0 || index > size) throw new IndexOutOfBoundsException(); //according to Java doc. else if (index == 0) addFirst(e); else if (index == size) addLast(e); else { Node newNode = new Node(e); Node current = head; // ] for (int i = 1; i < index; i++) // ]- get a reference to index-1 current = current.next; // ] newNode.next = current.next; // Link the new node to element @ index current.next = newNode; // Link element @ index-1 to newNode size++; } } //*** REMOVING *** public E removeFirst() { /** add code to set 'previous' [1 mark]*/ if (size == 0) return null; else { Node temp = head; // element will be returned head = head.next; size--; if (head == null) // if list becomes empty tail = null; return temp.element; // return the removed element } } public E removeLast() { /** improve performance using 'previous' [1 mark]*/ if (size == 0) return null; else if (size == 1) { Node temp = head; head = tail = null; size = 0; return temp.element; } else { Node temp = tail; // to return it Node current = head; // get ref. to second to last for (int i = 0; i < size - 2; i++) current = current.next; tail = current; tail.next = null; // remove last size--; return temp.element; // return last } } public E remove(int index) { /** add code to set 'previous' [2 marks]*/ if (index < 0 || index >= size) return null; else if (index == 0) return removeFirst(); else if (index == size - 1) return removeLast(); else { Node previous = head; for (int i = 1; i < index; i++) previous = previous.next; Node current = previous.next; previous.next = current.next; size--; return current.element; } } public boolean remove(E e) { if (indexOf(e) >= 0) { //if the element exists remove(indexOf(e)); //call the other remove method return true; } else return false; } public void clear() { size = 0; head = tail = null; } //*** GETTING *** public E getFirst() { if (size == 0) return null; else return head.element; } public E getLast() { if (size == 0) return null; else return tail.element; } public E get(int index) { /** improve performance using 'previous' [1 mark]*/ if (index < 0 || index >= size) return null; else if (index == 0) return getFirst(); else if (index == size - 1) return getLast(); else { Node current = head; // ] for (int i = 0; i < index; i++) // ]- get a reference to node @ index current = current.next; // ] return current.element; } } //*** SETTING *** public E set(int index, E e) { /** improve performance using 'previous' [1 mark]*/ if (index < 0 || index > size - 1) return null; Node current = head; for (int i = 0; i < index; i++) current = current.next; E temp = current.element; current.element = e; return temp; } //*** TOSTRING *** public String toString() { StringBuilder result = new StringBuilder("["); Node current = head; for (int i = 0; i < size; i++) { result.append(current.element); current = current.next; if (current != null) result.append(", "); // Separate two elements with a comma else result.append("]"); // Insert the closing ] in the string } return result.toString(); } public String toReversedString(){/** write code to return a string representing the list from right to left [3 marks]*/ return null; } //*** CHECKING *** public int size(){return size;} public boolean contains(E e) { Node current = head; for (int i = 0; i < size; i++) { if (current.element.equals(e)) return true; current = current.next; } return false; } public int indexOf(E e) { Node current = head; for (int i = 0; i < size; i++) { if (current.element.equals(e)) return i; current = current.next; } return -1; } public int lastIndexOf(E e) { /** improve performance using 'previous' [3 marks]*/ int lastIndex = -1; Node current = head; for (int i = 0; i < size; i++) { if (current.element.equals(e)) lastIndex = i; current = current.next; } return lastIndex; } //*** HELPER METHODS *** private void checkIndex(int idx) { if (idx < 0 || idx >= size) throw new IndexOutOfBoundsException("Index: " + idx + ", Size: " + size); } private Node getNodeAt(int index){ /** write code for this method to return a reference to a node at a given index [3 marks]*/ return null; } //*** INNER NODE CLASS *** private static class Node { /** add code to consider 'previous' [1 mark]*/ E element; Node next; public Node(E e) { element = e; } } } 

---------------TestMyDoublyLinkedList-------------- public class TestMyDoublyLinkedList { public static void main(String[] args) { String[] array = {"A", "B", "A", "A"}; MyDoublyLinkedList list = new MyDoublyLinkedList<>(array); System.out.printf("%-32s%-10s ", "Initialized with {A,B,A,A}:", list); testAdding(list); testGetting(list); testSetting(list); testRemoving(list); testChecking(list); System.out.printf(" %-32s%-10s ", "ToString: " , list); System.out.printf("%-32s%-10s ", "ToReversedString: " , list.toReversedString()); //the follow code should throw an exception System.out.println(" Adding 'X' at 20: "); list.add(20, "X"); } private static void testAdding(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Adding elements: ", list); list.addFirst("*"); System.out.printf("%-32s%-10s ", " - '*' at first", list); list.addLast("C"); System.out.printf("%-32s%-10s ", " - 'C' at last", list); list.add("D");System.out.printf("%-32s%-10s ", " - 'D'", list); list.add(2, "#"); System.out.printf("%-32s%-10s ", " - '#' @ 2", list); } private static void testGetting(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Getting elements: ", list); System.out.printf("%-32s%-10s ", " - First Element", list.getFirst()); System.out.printf("%-32s%-10s ", " - Last Element", list.getLast()); System.out.printf("%-32s%-10s ", " - Element at 1", list.get(1)); System.out.printf("%-32s%-10s ", " - Element at 20", list.get(20)); } private static void testSetting(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Setting elements: ", list); System.out.printf("%-32s%-10s ", " - Element @ 0: '"+list.set(0,"+")+"' -> '+'", list); System.out.printf("%-32s%-10s ", " - Element @ 2: '"+list.set(2, "-")+"' -> '-'", list); System.out.printf("%-32s%-10s ", " - Element @ 9: '"+list.set(9, "&")+"' -> '&'", list); } private static void testRemoving(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Removing elements: ", list); System.out.printf("%-32s%-10s ", " - First element '" + list.removeFirst() + "'", list); System.out.printf("%-32s%-10s ", " - Last element '" + list.removeLast() + "'", list); System.out.printf("%-32s%-10s ", " - Element @ 1 '" + list.remove(1) + "'", list); System.out.printf("%-32s%-10s ", " - Element @ 9 '" + list.remove(9) + "'", list); } private static void testChecking(MyDoublyLinkedList list) { System.out.printf(" %-32s%-10s ", "Checking: ", list); System.out.printf("%-32s%-10s ", " - Contains 'A'? ", list.contains("A")); System.out.printf("%-32s%-10s ", " - Contains 'Z'? ", list.contains("Z")); System.out.printf("%-32s%-10s ", " - First occurence of 'A' @ ", list.indexOf("A")); System.out.printf("%-32s%-10s ", " - Last occurence of 'A' @ ", list.lastIndexOf("A")); System.out.printf("%-32s%-10s ", " - First index of 'Z' @", list.indexOf("Z")); System.out.printf("%-32s%-10s ", " - Last index of 'Z' @", list.lastIndexOf("Z")); } }