/* DListst.java */

/** The DList class implements a doubly-linked list abstraction.  DLists
 * are mutable data structures.
 */

public class DList {
  /** Constructs an empty dlist.
   */
  public DList() {
    // fill in part I here
  }

  /** Returns true if this DList is empty, 
   *   false otherwise.                                 
   *   @return true if the DList is empty, false otherwise. 
   *  Performance: runs in O(1) time.
   */
  public boolean isEmpty() {
    // Replace the line below with your solution to part II.
    return true;
  }
    
  /** Returns the length of this DList. 
   *  @return the length of the DList.
   *  Performance: runs in O(n) time, where n is the length of the list.
   */
  public int length() {
    // replace the line below with your solution to part II.
    return 99;
  }

  /** Returns the element at position k in the DList. 
   *  If the DList is empty or k <= 0, or k > length(), returns null.  
   *  @return the element at position k.
   *  Performance: runs in O(k) time.
   */
  public Object nthFromFront(int k) {
      // replace the line below with your solution to part III.   
     return null;
  }

  /** Returns the element at position k, counting backwards from the back. 
   *  If the DList is empty or k <= 0, or k > length(), returns null.  
   *  @return the element at position k, counting from the back.
   *  Performance: runs in O(k) time.
   */
  public Object nthFromBack(int k) { 
    // replace the line below with your solution to part III.
    return null;
  }

  /** Inserts obj into this DList at the back.
   *  @param value is the value to be inserted.
   *  Performance: runs in O(1) time.
   */
  public void insertBack (Object value) {
    // replace the line below with your solution to part II.
  }
        
  /** Removes the value from the front of the DList.
   *  If the List is empty, returns null and leaves the 
   *   DList unchanged.
   *  @return the item removed from the list.
   *  Performance: runs in O(1) time.
   */
  public Object removeFront () {
    // replace the line below with your solution to part IV.
    return null;
  }
    
  /** Returns a String representation of the DList. 
   *  @return a String representation of the DList. 
   *  Performance: runs in O(n) time, where n is the length of the list.
   */
  public String toString() {
    String result = "[  ";

    DListNode cur = head.next;

    while (cur != head) {
      result = result + cur.item + "  ";
      cur = cur.next;
    }
    result = result + "]";
    return result;
  }

  /** Runs test cases on the the DList class. 
       Prints summary information on basic operations and halts 
       with an error (and a stack trace) if any of the tests fail. */
  public static void main (String [] argv) {
    // You may put test code here; it will not be graded.
  }

  /* Representation invariants on the data: 
   *  1) head is never null.
   *  2) head refers to a DListNode that contains no null references
   *      in the next or previous fields, and none of the DListNodes 
   *      that you can reach by following previous or next references
   *      contain null references in these fields.
   *  3) head refers to a DListNode that is a cyclic structure.
   */

  DListNode head;  // intentionally left as neither private nor public

}