import java.util.NoSuchElementException;

public class DList implements Cloneable {
    private DLNode head, tail;
    private int size; 
    public DList() { head = tail = null; size = 0; }
    public boolean isEmpty() { return size <= 0; }
    public int size() { return size; }
    public void addHead(Object item) {
	if (isEmpty()) {
	    head = tail = new DLNode(item, null, null);
	} else {
	    head = new DLNode(item, head, null);
	    head.next.prev = head;
	}
	++size;
    }
    public void addTail(Object item) {
	if (isEmpty()) {
	    head = tail = new DLNode(item, null, null);
	} else {
	    tail.next = new DLNode(item, null, tail);
	    tail = tail.next;
	}
	++size;
    }
    public Object delHead() {
        if (head == null) throw new NoSuchElementException();
	Object t = head.data;
	head = head.next;
	if (head != null) head.prev = null;
	--size;
	return t;
    }
    public Object delTail() {
        if (head == null) throw new NoSuchElementException();
	Object t = tail.data;
	tail = tail.prev;
	if (tail != null) tail.next = null;
	--size;
	return t;
    }
    public Object clone() { // throws CloneNotSupportedException {
	DList copy = new DList();
	DLNode t = tail;
	while (t != null) {
	    copy.addHead(t.data);
	    t = t.prev;
	}
	return copy;
    }
    public boolean isValid() {
	DLNode t = head;
	int i;
	if (size == 0) return head == null;
	for (i=1; i<size; ++i, t=t.next) {
	    if (t.next.prev == t) continue;
	    System.out.print("<"+t+">");
	    System.out.print("<"+t.next.prev+">");
	    return false;
	}
	return head.prev == null && tail.next == null && t == tail;
    }
}