CSC152 2006S, Class 41: List ADTs

Admin:
* HW14: Text Analysis (due Wednesday).
* Because so many people turned in the exam late (with permission), I don't plan to go over it until Friday.
* ChocoLATE

Overview:
* What is a list?
* Two ways to iterate lists: Cursors and Positions
* Three kinds of lists: Simple, Sequenced, and Sorted

What is a list?
* Something that groups objects (a kind of collection)
  * May not have an index, like in an array
  * Don't require deletion to get, like the LinearStructures
  * Something which has a unique first element, a unique last eleemnt, and in which each element but the first has a unique predecessor and each element but the last has a designated successor
* Four things to think about when discussing ADTs
  * P - Philosophy
    * Collections with the "first/last/pred/succ" property described above
  * A - Applications
    victims: Ben, Lindsay, Tony, Betsy, Hak, Christine, Ben, Ben, IanA, ...
    * Add Scott after Betsy
       victims: Ben, Lindsay, Tony, Betsy, Scott, Hak, Christine, Ben, Ben, IanA, ...
       Type of addAfter(V pred, V value)
       But ... there are three Ben
       Whoops ... can't use values to mark predecessors

  * M - Methods
    * Strategy one: Mark positions
      * addAfter(Position predecessor, V value)
      * Position predecessor(Position something)
      * Position successor(Position something)
      * Position first()
      * Position last()
      * isFirst(Position pos)
      * isLast(Position pos)
      * get(Position pos)
    * Strategy two: Have an iterator (cursor) that moves through the list
      * Methods for the List interface
        * Iterator front()
      * Methods for the Iterator interface
        * advance()
        * retreat()
        * atEnd()
        * atFront()
        * get()
* For strategy one: How would you write code that answers the question "Is Sam in the list?"
  public boolean containsSam(List<String> l)
  {
  /*
    if (l.get(l.first()).equals("Sam")) {
      return true;
    }
    else  {
      return containsSam(l, l.successor(l.first()));
    }
   */
    return containsSam(l, l.first());
  } // containsSam(List<String>)
  public boolean containsSam(List<String> l, Position pos)
  {
    if (l.get(pos).equals("Sam")) {
      return true;
    }
    else if (l.isLast(pos)) {
      return false;
    }
    else {
      return containsSam(l, l.successor(pos));
    }
  } // containsSam(List<String>)
  public boolean contains(List<V> l, V value)
  {
  } // contains(List<V>, V)
* For strategy two: How would you write code that answers the question "Is Sam in the list?"
  public boolean containsSam(List<String> l)
  {
    Iterator<String> it = l.front();
    do {
      if (it.get().equals("Sam")) {
        return true;
      }
      else {
        it.advance();
      }
    } while (!it.atEnd());
    return false;
  } // containsSam(List<String>)
  public boolean contains(List<V> l, V value)
  {
  } // contains(List<V>, V)

  * I - Implementation

Question: In what order are the things in the list?
* Simple lists: It's up to the implementer
* Sequenced lists: It's up to the client
* Sorted lists: It's up to a separate comparator

How do we implement lists?
* With vectors or arrays.
* With linked nodes