Your assignment is to improve the DoublyLinked List class we wrote in class. Please start with the version uploaded to Canvas called DLList shown on the back of this page to make sure there is a common starting point, but it should be equivalent to what we wrote in class.

(This version includes generics and an iterator.)

size method (25 points)

Implement a method

public int size() that return s 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 (15 points)

Improve the speed of public T get (inti) 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.

remove method speedup (10 points)

Improve the speed of public T remove(inti) 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 listA-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.

add with index method (25 points)

Implement a method public boolean add(inti,Ts) that adds an element withan 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).

Extra Credit

(2 points): Speed up add with index by working backward from the end of the list if you attempt to add a membe which is closer to the end than the start. This improvement will be tested through timing tests on large lists.

import java.util.Iterator;

public class DLListimplements Iterable{

private Nodehead,tail;

private static class Node {

public Nodeprev,next;

public T data;

public Node(Nodeprev, T data, Node

next) {

this.prev=prev;

this.next=next;

this.data=data;

}

}

private static class Conductorimplements Iterator {

public Nodecar;

public Conductor(DLListlist) {

car=list.head;

}

public boolean hasNext() {

return car!=null;

}

public T next() {

T data=car.data;

car=car.next;

return data;

}

}

public DLList() {

head=tail=null;

}

/**

* Add data to the end (tail) of the list

*/

public void

add(T data) {

if(tail==null) {

head=tail=new Node<>(null,data,null);

}else{

assert(tail.next==null);

tail.next=new Node<>(tail,data,null);

tail=tail.next;

}

}

public T get(int i) {

if(i< 0)return null;

Nodecurrent=head;

for(int j=0; current !=null && j

// Count our way up to desired element

current = current.next;

}

if (current==null) return null;

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) return null;

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)return null;

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;

}

public Iterator iterator() {

return new

Conductor(this);

}

}

Tester.Java

import java.util.Iterator;

public class DLList implements Iterable {

private Node head, tail;

private static class Node {

public Node prev, next;

public T data;

public Node(Node prev, T data, Node next) {

this.prev = prev;

this.next = next;

this.data = data;

}

}

private static class Conductor implements Iterator {

public Node car;

public Conductor(DLList list) {

car = list.head;

}

@Override

public boolean hasNext() {

return car != null;

}

@Override

public T next() {

T data = car.data;

car = car.next;

return data;

}

}

public DLList() {

head = tail = null;

}

/**

* Add data to the end (tail) of the DLList

*/

public void add(T data) {

if (tail == null) {

head = tail = new Node<>(null, data, null);

} else {

assert(tail.next == null);

tail.next = new Node<>(tail, data, null);

tail = tail.next;

}

}

/**

* Retrieve an element from the middle of the list

* @param i Zero-based index of the element to retrieve

* @return The element, or null if invalid index

*/

public T get(int i) {

if (i < 0) return null;

Node current = head;

for (int j = 0; current != null && j < i; j++) {

// Count our way up to the desired element

current = current.next;

}

if (current == null) return null;

return current.data;

}

/**

* Get and remove element i from the list.

* @param i

* @return element i or null if i is an invalid index

*/

public T remove(int i) {

if (i < 0) return null;

Node current = head;

for (int j = 0; current != null && j < i; j++) {

// Count our way up to the desired element

current = current.next;

}

if (current == null) return null;

if (current.prev != null)

current.prev.next = current.next; // Link

prev's next to new next

else head = head.next;

if (current.next != null)

current.next.prev = current.prev; // Link

next's prev to new prev

else tail = tail.prev;

return current.data;

}

public Iterator iterator() {

return new Conductor(this);

}

}