CSC152 2006S, Class 43: Lists (3): Linked Lists

Admin:
* Homework 15: Sorted Lists.
* EC for attending Lindsay's Paper+Dance thing tomorrow at 11:00.
  IN SPITE OF THE FACT THAT IT'S IN CONFLICT WITH CONVO
* Different tecnique today: Acting out operations

Overview:
* List operations
* Implementing lists with nodes.

* Simple List Operations
  * V get(Postition pos)
  * add(V value)
  * removeAll()
  * isEmpty()
  * remove(Position pos)
  * Position predecessor(Position pos)
  * Position successor(Position pos)
  * Position first()
  * Position last()
  * boolean isFirst(Position pos)
  * boolean isLast(Position pos)
* Fields in Node<V> (implements Position)
  * The thing: V val;  (1)
  * A hook to the next thing: Node<V> next; (2)
* Fields in NodeBasedList
  * Node<V> front;

public class LinkedSimpleList<V>
  implements SimpleList<V>
{
  Node<V> front;
  Node<V> back;

  public Position first()
  {
    return this.front;
  }
  public Position last()
  {
/*  // Slow strategy
    Node<V> tmp = this.front;
    while (tmp.next != null) {
      tmp = tmp.next;
    }
    return tmp;
 */
   // Fast strategy
   return this.back;
  }
  public V get(Position pos)
  {
    return ((Node<V>) pos).val;
  }

  public void add(V val)
  {
    // Make a new node, tmp, that contains val
    Node<V> tmp = new Node<V>(val);
    // Abnormal case: List is empty
    if (this.isEmpty()) {
      this.front = tmp;
      this.back = tmp;
    }
    // Normal case: List is not empty
    else {
      // Make tmp the next node of back
      this.back.next = tmp;
      // Make back tmp
      this.back = tmp;
    }
  }

  public void removeAll()
  {
    // Set the front and the end of the list to null
    this.front = null;
    this.end = null;
  } // removeAll

  public boolean isFirst(Position pos)
  {
    return this.front == pos;
  }

  public boolean isLast(Position pos)
  {
    return ((Node<V>) pos).next != null;
  }

  public void remove(Position pos)
  {
     // Special case
     if (this.front == pos) {
       this.front = this.front.next;
       if (this.front = null) {
         this.back = null;
       }
     }
     // General case
     else {
       Node<V> tmp = ((Node<V>) pos).next;
       Node<V> pred = this.front;
       while (pred.next != pos) {
         pred = pred.next;
       }
       if (this.back == pos) {
         this.back = pred;
       }
       pred.next = tmp;
     }
  }
}

* Some problems we noticed:
  * Removal is inefficient, because we have to search the whole list
  * Tons of special cases

* Making removal more efficient
  * Update the Node class so that it has a prev field
  * Every time we set a next, we need to set a previous (unless, of course, the next node is null)

* Solving the "special case problem"
  * All lists contain a special node, whose next element is the first element and whose prev element is the last element.