Write a generic class called Deque , from scratch. This class uses a doubly-link

Question

Write a generic class called Deque, from scratch. This class uses a doubly-linked list to implement this API:
Deque. A double-ended queue or deque (pronounced "deck") is a generalization of a stack and a queue that supports inserting and removing items from either the front or the back of the data structure.

Restrictions:

You may NOT use Java's LinkedList class (or ArrayList or any other Java data structure classes). You must implement a doubly-linked structure directly from scratch, using principles.

To implement a doubly-linked lists directly, you should look at the class lecture note on Lists.  
Note that a doubly-linked list could be made with or without dummy head and tail nodes. The decision is up to you. As long as the class Deque works, either implementation is fine. The lecture note does use them, as shown there. But if you don't use them, be sure to be consistent and do not let your code break.

Method Preconditions:

Some of the Deque methods have preconditions that should be met when the method is called. Ensuring that preconditions are met is the responsibility of the client (user) of the Deque class, NOT of the Deque class itself.

However, the Deque class does have the responsibility to check that method preconditions are met. If not, the method should throw the specified exception. The preconditions and corresponding exceptions are:

addFirst(E item) and addLast(E item):
    Precondition: item should not be null.
    throw: NullPointerException in java.lang package)

removeFirst() and removeLast():
    Precondition: Deque should not be empty.
    throw: NoSuchElementException (in java.util package)

remove() method in the inner class DequeIterator
    Precondition:: should never be called; not implemented
    throw: UnsupportedOperationException (in java.lang package)

next() method in the inner class DequeIterator
    Precondition:: the DequeIterator's hasNext() method should return true; that is, the iterator is not already past the last Deque item. So the iterator still has item(s) to return.
    throw: NoSuchElementException (in java.util package)

DequeIterator inner class:

The method iterator() must return an iterator object. You can write an inner class (say DequeueIterator) or an anonymous class, Either way, this class must implement the methods in the Iterator<E> interface:

public boolean hasNext()

public E next()

public void remove() // but it just throws the required exception

This inner class has data members and a constructor. Look at the example code in the class lecture note on Lists for examples.
For the method remove() and next(), see the note under Method Preconditions above.

Testing:

A JUnit test class, DequeTest, is provided, so you don't have to construct tests yourself for this assignment.

DequeTest.java

How to use the provided JUnit test class in Eclipse:

Copy the DequeTest.java to the src folder in the project containing your Deque.java.

Select this project (in the Eclipse's Package Explorer pane). Then open the project's properties and navigate to Libraries

Click on the Add Library... button and select JUnit.
Click next and make sure the JUnit library version is 4 (not 3) and click Finish.
This adds the JUnit classes and testing functionality to your project. You should now be able execute DequeTest as a JUnit test.

In addition a Deque application class is provided. After you have implemented and tested your Deque class with the JUnit DequeTest class, you should be able run this application that uses the Deque class:

DequeApp.java

Hints:

As for the class method implementations, you need to be careful about boundary cases: adding to an empty Deque, removing from a Deque of size 1. The JUnit tests attempt to check that your code works for boundary cases. If a JUnit test fails, it may be because some boundary case is not handled properly.

NullPointerExceptions often occur when you first learn to use linked lists to implement data structure classes like Deque. The causes include

Failing to check preconditions

Failing to handle boundary cases correctly

Trying to access a node AFTER a node reference has already been moved past the last node in a linked list (E.g., the next reference of the last node is often null. So moving the reference past the last node results in the reference being null).

Explanation / Answer

class Deque<E> {
   private DNode<E> head;
   private DNode<E> tail;

   private int size;

   public Deque() // construct an empty deque
   {
       head = null;
       tail = null;
       size = 0;
   }

   public int size() {
       return size;
   }

   public boolean isEmpty() // is the deque empty?
   {
       return size == 0;
   }

   public void addFirst(E item) // insert the item at the front
   {
       if (item == null)
           throw new NullPointerException("Item is null");

       DNode<E> node = new DNode<E>(item, head, null);
       if (head != null) {
           head.setPrev(node);
       }

       if (tail == null) {
           tail = node;
       }

       head = node;
       size++;

   }

   public void addLast(E item) // insert the item at the end
   {
       if (item == null)
           throw new NullPointerException("Item is null");

       DNode<E> node = new DNode<E>(item, null, tail);
       if (tail != null) {
           tail.setNext(node);
       }

       tail = node;
       if (head == null) {
           head = node;
       }
       size++;
   }

   public E removeFirst() // delete and return the item at the front
   {
       if (size == 0)
           throw new NoSuchElementException("Deque is empty");
      
       DNode<E> node = head;
       head = head.getNext();
       head.setPrev(null);
       size--;
       return node.getItem();

   }

   public E removeLast() // delete and return the item at the end
   {
       if (size == 0)
           throw new NoSuchElementException("Deque is empty");
      
       DNode<E> node = tail;
       tail = tail.getPrev();
       tail.setNext(null);
       size--;

       return node.getItem();
   }

   public Iterator<E> iterator() // return an iterator over items in order from front to end
   {
       // Iterator<E> iter = new Iterator<E>();
       return new DequeIterator();

   }
  
   // return an iterator over items in order from front to end
   class DequeIterator implements Iterator<E> {

       private DNode<E> curNode;

       public DequeIterator() {
           curNode = head;
       }
      
       @Override
       public boolean hasNext() {
           if (curNode != null && curNode.getNext() != null)
                return true;
            else
                return false;
       }

       @Override
       public E next() {
           // TODO Auto-generated method stub'
           if(curNode != null && curNode.getNext() != null) {
               DNode<E> temp = curNode;
               curNode = curNode.getNext();
               return temp.getItem();
           }
           return null;
       }

       @Override
       public void remove() {
           // TODO Auto-generated method stub
          
       }
      
   }

}



class DNode<E> {
   private E item;
   private DNode<E> next;
   private DNode<E> prev;

   public DNode(E item, DNode<E> next, DNode<E> prev) {
       this.item = item;
       this.next = next;
       this.prev = prev;
   }

   public E getItem() {
       return item;
   }

   public void setItem(E item) {
       this.item = item;
   }

   public DNode<E> getNext() {
       return next;
   }

   public void setNext(DNode<E> next) {
       this.next = next;
   }

   public DNode<E> getPrev() {
       return prev;
   }

   public void setPrev(DNode<E> prev) {
       this.prev = prev;
   }

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.