public class DoublyLinkedList implements List { private Node head; private Node tail; private int size; public DoublyLinkedList() { //create an empty list //since head and tail are sentinels, we have to create them head = new Node(null); tail = new Node(null); // note ValueType os always a reference type //in Java, this means that ValueType is descendant of Object //these two point to each other head.setNext(tail); tail.setPrev(head); //set size to zero size =0; }

@Override public boolean isEmpty() { // TODO Auto-generated method stub return (size == 0); }

@Override public int size() { // TODO Auto-generated method stub return size; }

private void addBetween(ValueType value, Node pred, Node succ) { //1) Make a new node containing the value, between pred and succ Node newNode = new Node(value, pred, succ); //1)Linl the nodes in the list to this new node pred.setNext(newNode); succ.setPrev(newNode); //3) Update size variable size++; } @Override public void addToFront(ValueType value) { // TODO Auto-generated method stub addBetween(value, head, head.getNext()); }

@Override public void addToBack(ValueType value) { addBetween (value, tail.getPrev(), tail); } ///removal methods private ValueType removeNode (Node n) { //we just need to updates n's predecessor to point to n's successor and vice versa Node prev = n.getPrev(); Node next = n.getNext(); prev.setNext(next); next.setNext(prev); //decrement the size size--; return n.getValue(); }

@Override public ValueType removeFront() { if (isEmpty()) { throw new IllegalStateException("Cannot Remove From an Empty List"); } return removeNode(head.getNext()); }

@Override public ValueType removeBack() { if (isEmpty()) { throw new IllegalStateException("Cannot Remove From an Empty List"); } return removeNode(tail.getPrev()); } public String toString() { StringBuilder sb = new StringBuilder(); sb.append("(Size = " + size + ")"); //walk through the list, append all values for (Node tmp = head.getNext(); tmp != tail ;tmp = tmp.getNext()) { sb.append(" " + tmp.getValue()); } return sb.toString(); }

//private inner class private class Node{ //private variables private ValueType value; // the value private Node next; // reference to next node private Node prev; // reference to previous node //constructors public Node(ValueType value,Node prev, Node next) { this.value = value; this.next = next; this.prev = prev; } public Node(ValueType value) { this(value, null, null); }

//getters and setters public ValueType getValue() { return value; }

public Node getPrev() { return prev; }

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

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

public Node getNext() { return next; }

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

}

-----------------------------------------------------------------------------------------------