Implement a doubly linked list) The MyLinkedList class used in Listing 24.6 is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new data field name previous to refer to the previous node in the list, as follows: public class Node {

E element;

Node next;

Node previous; public Node(E e) {

element = e;

}

} Implement a new class named TwoWayLinkedList that uses a doubly linked list to store elements. The MyLinkedList class in the text extends MyAbstractList. Define TwoWayLinkedList to extend the java.util.AbstractSequentialList class. You need to implement all the methods defined in MyLinkedList as well as the methods listIterator() and listIterator(int index). Both return an instance of java.util. ListIterator. The former sets the cursor to the head of the list and the latter to the element at the specified index.

Listing 24.6

1 public class MyLinkedList extends MyAbstractList {

2 private Node head, tail; 3 4 /** Create a default list */ 5 public MyLinkedList() { 6 } 7 8 /** Create a list from an array of objects */ 9 public MyLinkedList(E[] objects) { 10 super(objects); 11 } 12 13 /** Return the head element in the list */ 14 public E getFirst() { 15 if (size == 0) { 16 return null; 17 } 18 else { 19 return head.element; 20 } 21 } 22 23 /** Return the last element in the list */ 24 public E getLast() { 25 if (size == 0) { 26 return null; 27 } 28 else { 29 return tail.element; 30 } 31 } 32 33 /** Add an element to the beginning of the list */ 34 public void addFirst(E e) { 35 // Implemented in Section 24.4.3.1, so omitted here 36 } 37 38 /** Add an element to the end of the list */ 39 public void addLast(E e) { 40 // Implemented in Section 24.4.3.2, so omitted here 41 } 42 43 @Override /** Add a new element at the specified index 44 * in this list. The index of the head element is 0 */ 45 public void add(int index, E e) { 46 // Implemented in Section 24.4.3.3, so omitted here 47 } 48 49 /** Remove the head node and 50 * return the object that is contained in the removed node. */ 51 public E removeFirst() { 52 // Implemented in Section 24.4.3.4, so omitted here /** Remove the last node and 56 * return the object that is contained in the removed node. */ 57 public E removeLast() { 58 // Implemented in Section 24.4.3.5, so omitted here 59 } 60 61 @Override /** Remove the element at the specified position in this 62 * list. Return the element that was removed from the list. */ 63 public E remove(int index) { 64 // Implemented earlier in Section 24.4.3.6, so omitted here 65 } 66 67 @Override 68 public String toString() { 69 StringBuilder result = new StringBuilder("["); 70 71 Node current = head; 72 for (int i = 0; i < size; i++) { 73 result.append(current.element); 74 current = current.next; 75 if (current != null) { 76 result.append(", "); // Separate two elements with a comma 77 } 78 else { 79 result.append("]"); // Insert the closing ] in the string 80 } 81 } 82 83 return result.toString(); 84 } 85 86 @Override /** Clear the list */ 87 public void clear() { 88 size = 0; 89 head = tail = null; 90 } 91 92 @Override /** Return true if this list contains the element e */ 93 public boolean contains(E e) { 94 System.out.println("Implementation left as an exercise"); 95 return true; 96 } 97 98 @Override /** Return the element at the specified index */ 99 public E get(int index) { 100 System.out.println("Implementation left as an exercise"); 101 return null; 102 } 103 104 @Override /** Return the index of the head matching element 105 * in this list. Return -1 if no match. */ 106 public int indexOf(E e) { 107 System.out.println("Implementation left as an exercise"); 108 return 0; 109 } 110 111 @Override /** Return the index of the last matching element 112 * in this list. Return -1 if no match. */ 113 public int lastIndexOf(E e) { 114 System.out.println("Implementation left as an exercise"); 115 return 0; 116 } 117 118 @Override /** Replace the element at the specified position 119 * in this list with the specified element. */ 120 public E set(int index, E e) { 121 System.out.println("Implementation left as an exercise"); 122 return null; 123 } 124 125 @Override /** Override iterator() defined in Iterable */ 126 public java.util.Iterator iterator() { 127 return new LinkedListIterator(); 128 } 129 130 private class LinkedListIterator 131 implements java.util.Iterator { 132 private Node current = head; // Current index 133 134 @Override 135 public boolean hasNext() { 136 return (current != null); 137 } 138 139 @Override 140 public E next() { 141 E e = current.element; 142 current = current.next; 143 return e; 144 } 145 146 @Override 147 public void remove() { 148 System.out.println("Implementation left as an exercise"); 149 } 150 } 151 152 // This class is only used in LinkedList, so it is private. 153 // This class does not need to access any 154 // instance members of LinkedList, so it is defined static. 155 private static class Node { 156 E element; 157 Node next; 158 159 public Node(E element) { 160 this.element = element;