descendingIterator method and BackwardConductor (20 points) Implement a new inner BackwardConductor class that implements Iterator and the method public Iterator descendingIterator() which returns a new BackwardConductor object that visits the nodes from back to front. (The first call to next() on the returned iterator object would return the tail, the second call to next() would return the element before the tail, etc.) size method (20 points) Implement a method public int size() that returns the number of elements of the list in O(1) constant time. You will need to add a member field to DLList to support it. The member field will have to be maintained by the other methods as operations are performed to add or remove elements from the list. get method speedup (10 points) Improve the speed of public T get(int i) by having it work backward from the end of the array if you attempt to get a member which is closer to the end than the start. This improvement will be tested through timing tests on large lists. The method should still return null if i is not a valid index. reverse method (25 points) Implement a method public void reverse() that reverses the list. The list A-B-C-D would become D-C-B-A. The old start (A in the example) should be the new end and the old end should be the start. The next element after the start should be what was the previous element before the end, and so forth. The method should work for a list of any length, including the empty list. This method should not create new Nodes or other objects; the tester will check for this. (Its relatively easy to do this in O(n) time) add with index method (25 points) Implement a method public boolean add(int i, T s) that adds an element with an element of type T at index i. (Note that this uses Javas overload facility since we already have an add method with just a String argument.) Return false if there is not already an element at index i in the list, otherwise add the element and return true. (Note that this doesnt let you add a new element to the very end but the existing add method accomplishes this.) The elements before index i should be unchanged. Your new element will be placed at index i. The elements which were already at index i and after should all be in the same order but moved down (at one index value greater than they were before the call to your add method). all of these are on a doubly linked list with the nodes head,tail, prev and next. Thank

the starting code is

import java.util.Iterator;

public class DLList implements Iterable { private static class Node { // prev is reference to adjacent node closer to head (or null if this node is the head) // next is reference to adjacent node closer to tail (or null if this node is the tail) public Node prev, next; // data is the information stored in the node of type T (T could be String, Integer, etc.) public T data;

public Node(Node prev, T data, Node next) { this.prev = prev; this.next = next; this.data = data; } }

// head is first node (no prev), tail is last node (no next) // They can both reference the same node if the list is one element long // The can both reference null if the list is empty private Node head, tail;

/** * Forward iterator class (conductor). */ private static class Conductor implements Iterator { public Node car; // Next node to visit

public Conductor(DLList list) { car = list.head; // Begin at head }

public boolean hasNext() { return car != null; // No more to visit }

public T next() { T data = car.data; // Remember current car = car.next; // Advance to next car return data; // Return old car data } }

public DLList() { head = tail = null; // Empty list }

/** * Add data to the end (tail) of the list. */ public void add(T data) { if (tail == null) { // Empty list: one node is head and tail head = new Node<>(null, data, null); tail = head; } else { tail.next = new Node<>(tail, data, null); tail = tail.next; } }

/** * Retrieve an element from middle of list. * * @param i * Zero-based index of element * @return The element, or null if invalid i */ public T get(int i) { if (i < 0) throw new IndexOutOfBoundsException(); Node current = head; for (int j = 0; current != null && j < i; j++) { // Count our way up to desired element current = current.next; } if (current == null) throw new IndexOutOfBoundsException(); return current.data; }

/** * Get and remove element i from the list. * * @param i * @return element i or null if invalid i */ public T remove(int i) { if (i < 0) throw new IndexOutOfBoundsException(); Node current = head; for (int j = 0; current != null && j < i; j++) { // Count our way up to desired element current = current.next; } if (current == null) throw new IndexOutOfBoundsException(); if (current.prev != null) // Link prev's next to new next current.prev.next = current.next; else head = head.next; if (current.next != null) // Link next's prev to new prev current.next.prev = current.prev; else tail = tail.prev; return current.data; }

/** * Create a forward iterator for this list. */ public Iterator iterator() { // The Conductor object can walk this list // forward, front to back. Each time // .next() is called, the Conductor // produces one more piece of data, // starting with head and ending with tail return new Conductor(this); } }