// CODE

import java.util.Iterator; import java.util.NoSuchElementException;

import lab4.util.List;

public class CircularDoublyLinkedList implements List {

private class Node { private E value; private Node next, prev;

public Node(E value, Node next, Node prev) { this.value = value; this.next = next; this.prev = prev; }

public Node(E value) { this(value, null, null); // Delegate to other constructor }

public Node() { this(null, null, null); // Delegate to other constructor }

public E getValue() { return value; }

public void setValue(E value) { this.value = value; }

public Node getNext() { return next; }

public void setNext(Node next) { this.next = next; }

public Node getPrev() { return prev; }

public void setPrev(Node prev) { this.prev = prev; }

public void clear() { value = null; next = prev = null; } } // End of Node class

private class ListIterator implements Iterator {

private Node nextNode;

public ListIterator() { nextNode = header.getNext(); }

@Override public boolean hasNext() { return nextNode != trailer; }

@Override public E next() { if (hasNext()) { E val = nextNode.getValue(); nextNode = nextNode.getNext(); return val; } else throw new NoSuchElementException(); }

} // End of ListIterator class, DO NOT REMOVE, TEST WILL FAIL

/* private fields */ private Node header, trailer; // "dummy" nodes private int currentSize;

public CircularDoublyLinkedList() { /** * Set dummy nodes to point to each other * * --> header trailer

@Override public void add(E obj) { /*TODO ADD YOUR CODE HERE*/ }

@Override public void add(E elm, int index) { /*TODO ADD YOUR CODE HERE*/ }

@Override public boolean remove(E obj) { /*TODO ADD YOUR CODE HERE*/ return false; }

@Override public boolean remove(int index) { /*TODO ADD YOUR CODE HERE*/ return false; }

@Override public int removeAll(E obj) { /*TODO ADD YOUR CODE HERE*/ return -1; }

@Override public E get(int index) { /*TODO ADD YOUR CODE HERE*/ return null; }

@Override public E set(int index, E newElement) { /*TODO ADD YOUR CODE HERE*/ return null; }

@Override public int firstIndexOf(E obj) { /*TODO ADD YOUR CODE HERE*/ return -1; }

@Override public int lastIndexOf(E obj) { /*TODO ADD YOUR CODE HERE*/ return -1; }

@Override public E first() { /*TODO ADD YOUR CODE HERE*/ return null; }

@Override public E last() { /*TODO ADD YOUR CODE HERE*/ return null;

}

@Override public int size() { /*TODO ADD YOUR CODE HERE*/ return -1; }

@Override public boolean isEmpty() { /*TODO ADD YOUR CODE HERE*/ return false; }

@Override public boolean contains(E obj) { /*TODO ADD YOUR CODE HERE*/ return false; }

@Override public void clear() { /*TODO ADD YOUR CODE HERE*/

}

@Override public Iterator iterator() { return new ListIterator(); } //DO NOT DELETE, TESTS WILL FAIL

}

1. (20 pts) Head over to SinglyLinkedList. java and find an empty method called reverse (). The instructions for this exercise are as follows : - Implement a member method for the linked list implementation of the List ADT called reverse () which reverses the elements in a SinglyLinkedist. - The method must run in O(n) time, where n is the size of the list. - Solutions that are not O(n) will get at most 50% credit upon inspection by the professor or TAs. - You cannot use extra space to solve this problem (e.g. use another array list to store elements) - For example, if L ={ Ken, Al,Bob,Mel} then a call to L.reverse ( ) turns L into L ={Mel,Bob,Al,Ken}