Asymptotic Analysis

Part I: Reversing a List

In this lab, you will adding a single method to DoublyLinkedList: reverse(). When called, reverse() should reverse the order of nodes in the list. You may use any methods we've implemented in class to accomplish this.

Note: You must reverse this list in-place. That means you may not change node.value; you may only change node.prev and node.next.

When you are finished, add a Driver class with a main method which tests this method.

Part II: Algorithm Analysis

Analyze your algorithm using Big-Oh notation. Assuming the list contains n elements, what is its worst-case running time? Answer in a comment in the main method of your Driver class.

Part III: Problem Analysis

Is your algorithm asymptotically optimal? That is, is it possible to write a function that does better in the worst case? Answer in a comment in the main method of your Driver class.

Code for Doubly Linked List:

public class DoublyLinkedList { private Node header; private Node trailer; private int size; public DoublyLinkedList() { header = new Node<>(null, null, null); trailer = new Node<>(null, null, header); header.next = trailer; size = 0; } private void insertBetween(E v, Node first, Node second) { Node newNode = new Node<>(v, second, first); second.prev = newNode; first.next = newNode; size++; } private E removeBetween(Node first, Node second) throws IllegalStateException { if(header.next == trailer) //if(size == 0) { throw new IllegalStateException("Cannot delete from empty list"); } E valueToReturn = first.next.value; first.next = second; second.prev = first; size--; return valueToReturn; } public void insertAtHead(E v) { insertBetween(v, header, header.next); } public void insertAtTail(E v) { insertBetween(v, trailer.prev, trailer); } public E removeHead() throws IllegalStateException { return removeBetween(header, header.next); } public E removeTail() throws IllegalStateException { return removeBetween(trailer.prev, trailer); } public String toString() { if(size == 0) { return "list is empty!"; } String r = ""; Node temp = header.next; while(temp != trailer) { r += temp.toString() + " "; temp = temp.next; } return r; } public void printBackward() { if(size == 0) { System.out.println("list is empty!"); } Node temp = trailer.prev; while(temp != header) { System.out.print(temp + " "); temp = temp.prev; } System.out.println();

} private static class Node { private T value; private Node next; private Node prev; public Node(T v, Node n, Node p) { value = v; next = n; prev = p; } public String toString() { return value.toString(); } }

}