DList

gistfile1.java

public class DList<E extends Comparable<E>> {

   private class Node {
      public E data;
      public Node next;
      public Node prev;

      public Node(E data) {
         this.data = data;
      }

      public Node(Node prev,E data,Node next) {
         this.data = data;
      }
   }

   private int size;
   private Node sentinel;
   public FwdIterator fwdIt;
   public RevIterator revIt;	

   public DList() {
      // You will need to initialize everything here.
	size = 0;
	sentinel = new Node(null, null, null);
	sentinel.next = sentinel;
	sentinel.prev = sentinel;
   }

   public int size() {
      return size;
   }

   public void makeFwdIterator()
   {
	fwdIt = new FwdIterator();	
   }

   public void makeRevIterator()
   {
	revIt = new RevIterator();
   }

   public void insertFront(E data)
   {
	sentinel.next = new Node(sentinel, data, sentinel.next);
	sentinel.next.next.prev = sentinel.next;
	size++;
   }

   public void insertEnd(E data)
   {
	sentinel.prev = new Node(sentinel.prev, data, sentinel);
	sentinel.prev.prev.next = sentinel.prev;
	size++;
   }

   public void deleteFront()
   {
	sentinel.next = sentinel.next.next;
	sentinel.next.next.prev = sentinel;
   }

   public void deleteEnd()
   {
	sentinel.prev = sentinel.prev.prev;
	sentinel.prev.prev.next = sentinel;
   }

   private abstract class AllIterator implements Iterator<E> {
      protected Node cursor;
      protected boolean valid;

      public E get() {
         if (valid)
            return cursor.data;
	else return null;
      }

      public boolean isValid() {
         return valid;
      }

      public abstract void next();  // set valid to false if next moves to the sentinel

      public void delete() {
         // your code here!
         // What are your boundary conditions?
	cursor.next.prev = cursor.prev;
	cursor.prev.next = cursor.next;	
	next();
      }
   }

   private class FwdIterator extends AllIterator {
      public FwdIterator() {
	 valid = true;
         cursor = sentinel;
         this.next();
      }

      public void next() {
         if (valid) 
            cursor = cursor.next;
	 if (cursor == sentinel)
		valid = false;
      }
   }

   private class RevIterator extends AllIterator {
      public RevIterator() {
	 valid = true;
         cursor = sentinel;
         this.next();
      }

      public void next() {
         if (valid) 
            cursor = cursor.prev;
	 if (cursor == sentinel)
		valid = false;
      }
   }
}