CSC402 Homework Assignment 5

Implement a generic Deque class, Deque<E> that implements Iterable<E>, that allows insertions and deletions at both ends of a linked list.

The Nodes in the list containing the data should be doubly linked and your methods should be able to take advantage of that fact to be efficent - taking constant time independent of the size of the list.

The data items should be assumed to be of type E, the generic type parameter. So the data will of class type, but do not require E to be Comparable.

This means the Deque class declaration will begin like this:

public class Deque<E> implements Iterable<E>
{
  ...
}
    

The UML description of the Deque class and its members:

Download the hw5.zip file which contains

• DequeTest.java (a JUnit test class for your Deque class)

Write the Deque class (in a file Deque.java) implementing these members and be sure to test your code by running the provided JUnit test DequeTest. If your Deque passes all the tests you will get full credit for this assignment.

Specifications of Deque Members

Data members

The Deque implmentation must use doubly linked Nodes and use head and tail guard Nodes (see below).

boolean isEmpty()

    /**
    * Returns true if the list is empty
    * Note that even if the list is empty, head and tail 
    * should not be null. There should always be two guard
    * Nodes, one at each end of the list referenced by head and tail.
    */
    

int size()

      /**
      * Returns the number of data Nodes in the Deque 
      * Note: This does not count the guard nodes!
      */
    

void pushLeft(E x)

      /**
      * Inserts x (in a Node) at the front of the list (just after the
      * head Node).
      */
    

void pushRight(E x)

      /**
      * Inserts x (in a Node) at the end of the list (just before the
      * tail Node).
      */
    

E popLeft()

      /**
      * Removes the first data Node (the one after head) provided the
      * Deque is not empty and returns the data member of that Node.
      * Throws NoSuchElementException if the Deque is empty.
      */
    

E popRight()

      /**
      * Removes the last data Node (the one before tail) provided the
      * Deque is not empty and returns the data member of that Node.
      * Throws NoSuchElementException if the Deque is empty.
      */
    

Iterator<E> iterator()

      /**
      * Returns a object of type Iterator. That is, an instance
      * of a class that implements the 3 members of the
      * Iterator<E> interface.
      */
    

To implement this method you will need to create an inner class of Deque that implements Iterator<E>

This means the inner class must implement:

1. boolean hasNext()
2. E next()
3. void remove()

The next() method of this innner class should throw NoSuchElementException if hasNext() is false.

The remove() method of this inner class should just throw UnsupportedOperationException.

Doubly Linked Nodes

The Node class for Deque should be an inner class of Deque

The Node class and its members should be private. This means only the Deque member methods can create Nodes and access Node members.

private class Node
{
  private E data;
  private Node prev;
  private Node next;
  private Node(E x) {  
    data = x;
    prev = next = null;
  }
}
    

Guard Nodes and the Deque Implementation

The head and tail nodes below are the guard nodes. The Deque constructor must initialize head and tail by creating these two Nodes and initialize the next member of the head Node and the prev member of the tail Node as shown for the Empty List.

Empty List: size 0

Non-Empty List: size 3

What to Submit

Submit your Deque.java file (only) to Course Online for homework assignment 5.

Be sure to include a comment at the beginning of your Deque.java file with your name!

    /**
    * Deque an linear data type allowing insertions and deletions at
    * both ends.
    * 
    * @author  (your name)
    */