package net.datastructures;
/**
* Implementation of the Deque interface by means of a doubly linked
* list. This class uses class DLNode, which implements a node of
* the list.
*
* @author Natasha Gelfand
* @author Roberto Tamassia
*/
public class NodeDeque implements Deque {
protected DLNode header, trailer; // sentinels
protected int size; // number of elements
/** Creates an empty deque. */
public NodeDeque() { // initialize an empty deque
header = new DLNode();
trailer = new DLNode();
header.setNext(trailer); // make header point to trailer
trailer.setPrev(header); // make trailer point to header
size = 0;
}
/**
* Return the size of the deque, that is the number of elements it has.
* @return Number of elements in the deque
*/
public int size() {
return size;
}
/**
* This function returns true if and only if the deque is empty
* @return true if the deque is empty, false otherwise
*/
public boolean isEmpty() {
if (size == 0)
return true;
return false;
}
/**
* Inspect the first element without modifying the deque.
* @return The first element in the sequence
*/
public Object first() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
return header.getNext().getElement();
}
public Object last() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
return trailer.getPrev().getElement();
}
public void insertFirst(Object o) {
DLNode second = header.getNext();
DLNode first = new DLNode(o, header, second);
second.setPrev(first);
header.setNext(first);
size++;
}
public void insertLast(Object o) {
DLNode secondtolast = trailer.getPrev();
DLNode last = new DLNode(o, secondtolast, trailer);
secondtolast.setNext(last);
trailer.setPrev(last);
size++;
}
public Object removeFirst() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
DLNode first = header.getNext();
Object o = first.getElement();
DLNode second = first.getNext();
header.setNext(second);
second.setPrev(header);
size--;
return o;
}
public Object removeLast() throws EmptyDequeException {
if (isEmpty())
throw new EmptyDequeException("Deque is empty.");
DLNode last = trailer.getPrev();
Object o = last.getElement();
DLNode secondtolast = last.getPrev();
trailer.setPrev(secondtolast);
secondtolast.setNext(trailer);
size--;
return o;
}
}
|