/**
 * Lists that change and are imploemented with Cons cells.
 *
 * @author Samuel A. Rebelsky
 * @author Yvonne Palm
 * @author Jonathan "Don't I get to make suggestions, too?" Wellons
 * @author Alex "I'm Back, Be Ware" Leach
 */
public class LinkedList
  implements MutableList
{
  // +--------+---------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The front of the list.
   */
  ConsCell front;

  /**
   * The back of the list.
   */
  ConsCell back;

  /**
   * The length of the list.
   */
  int length;

  // +--------------+---------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new, empty, list.
   */
  public LinkedList()
  {
    front = null;
    back = null;
    length = 0;
  } // LinkedList()

  // +---------+--------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Determine if the list is empty
   */
  public boolean isEmpty() {
    return (null == this.front);
  } // isEmpty()

  /**
   * Update the list by adding an element to the front.
   */
  public void addToFront(Object newThingy)
  {
    this.front = new ConsCell(newThingy, this.front);
    // If the list was previously empty, ...
    if (null == this.back) {
      // The back is the same as the front.
      this.back = this.front;
    }
    ++this.length;
  } // addToFront(Object newThingy)

  /**
   * Update the list by adding an element to the end.
   */
  public void addToEnd(Object newThingy) {
    // Create a new cons cell.
    ConsCell newBack = new ConsCell(newThingy, null);
    // Special case: Empty list
    if (this.back == null) {
      this.back = newBack;
      this.front = newBack;
    }
    // Normal case 
    else {
      // Update the cdr of this.back
      this.back.myCdr = newBack;
      // Update this.back
      this.back = newBack;
    }
    ++this.length;
  } // addToEnd(Object)

  /**
   * Update the list by removing the first element.  Return
   * that element.
   */
  public Object removeFirst()
    throws Exception
  { 
    // Remember the first element.
    Object first = this.front.myCar;
    // Update the front of the list to refer to the next element.
    this.front = this.front.myCdr;
    // Do we have to do anything else if the list becomes empty?
    if (null == this.front) {
      this.back = null;
    }
    // Shrink the list
    --this.length;
    // Return the thing we previously identified as first. 
    return first;  
  } // removeFirst()

  /**
   * Remove the last element.
   */
  public Object removeLast()
    throws Exception
  {
    // Remember the last value
    Object last = this.back.myCar;
    // Special case: The list contains only one element.
    if (this.front == this.back) {
      this.front = null;
      this.back = null;
    }
    else {
      // Start at the front of the list and advance until we're
      // right before the end of the list.
      ConsCell temp = this.front;
      while (temp.myCdr != this.back) {
        temp = temp.myCdr;
      } // while
      // We can now delete the last element.
      temp.myCdr = null;
      this.back = temp;
    } // List contains more than one element
    // Shrink the list
    --this.length;
    // Return the old last value
    return last;
  } // removeLast()

  /**
   * Get the length.
   */
  public int length()
  {
    int count;
    ConsCell temp = this.front;
    while (temp != null) {
      ++count;
      temp = temp.myCdr;
    }
    return count; // STUB
  } // length()

  /**
   * Get the first element (non-destructively).
   */
  public Object getFirst()
    throws Exception
  {
    return this.front.myCar;
  } // getFirst()

  /**
   * Convert to a string for ease of printing.
   */
  public String toString()
  {
    if (null == this.front) {
      return "()";
    }
    else {
      return this.front.toString();
    }
  } // toString()

  /**
   * Make an independent copy of this list.
   */
  public MutableList copyMe() {
    return null;
  }
} // class LinkedList