net.datastructures
Class NodeDeque

java.lang.Object
  net.datastructures.NodeDeque

All Implemented Interfaces:

Deque

public class NodeDeque

extends Object

implements Deque

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, Roberto Tamassia

Field Summary

protected DLNode	header
protected int	size
protected DLNode	trailer

Constructor Summary

NodeDeque()
Creates an empty deque.

Method Summary

Object	first() Inspect the first element without modifying the deque.
void	insertFirst(Object o) Insert an element at the beginning.
void	insertLast(Object o) Insert an element at the end.
boolean	isEmpty() This function returns true if and only if the deque is empty
Object	last() Gets the last element (without modifying the deque).
Object	removeFirst() Remove the element at the beginning.
Object	removeLast() Remove the element at the end.
int	size() Return the size of the deque, that is the number of elements it has.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

header

protected DLNode header

trailer

protected DLNode trailer

size

protected int size

Constructor Detail

NodeDeque

public NodeDeque()

Creates an empty deque.

Method Detail

size

public int size()

Return the size of the deque, that is the number of elements it has.

Specified by:

size in interface Deque

Returns:

Number of elements in the deque

isEmpty

public boolean isEmpty()

This function returns true if and only if the deque is empty

Specified by:

isEmpty in interface Deque

Returns:

true if the deque is empty, false otherwise

first

public Object first()
             throws EmptyDequeException

Inspect the first element without modifying the deque.

Specified by:

first in interface Deque

Returns:

The first element in the sequence

Throws:

EmptyDequeException - if the deque is empty

last

public Object last()
            throws EmptyDequeException

Description copied from interface: Deque

Gets the last element (without modifying the deque).

Specified by:

last in interface Deque

Returns:

last element in the deque.

Throws:

EmptyDequeException - if the deque is empty

insertFirst

public void insertFirst(Object o)

Description copied from interface: Deque

Insert an element at the beginning.

Specified by:

insertFirst in interface Deque

Parameters:

o - new element to be inserted.

insertLast

public void insertLast(Object o)

Description copied from interface: Deque

Insert an element at the end.

Specified by:

insertLast in interface Deque

Parameters:

o - new element to be inserted.

removeFirst

public Object removeFirst()
                   throws EmptyDequeException

Description copied from interface: Deque

Remove the element at the beginning.

Specified by:

removeFirst in interface Deque

Returns:

element removed.

Throws:

EmptyDequeException - if the deque is empty

removeLast

public Object removeLast()
                  throws EmptyDequeException

Description copied from interface: Deque

Remove the element at the end.

Specified by:

removeLast in interface Deque

Returns:

element removed.

Throws:

EmptyDequeException - if the deque is empty