CSC152 2005S, Class 45: Some List ADTs

Admin:
* Due: Hash table lab
* Extra credit for tomorrow's Psych presentation
* Reminder: Extra credit for Darwin Convo
* For Tuesday: Think about how to implement remove in VectorBasedSimpleList
* For Tuesday: Try to get enough sleep

Overview:
* What is a list?
* Three kinds of lists:
  * Simple
  * Sequenced
  * Sorted
* About list cursors

Lists: Yet another ADT

* Reminder: Three key aspects of ADTs
  * Philosophy: What is the overall purpose/design of the ADT?
  * Methods: What operations support that philosophy/design?
  * Applications: How do we expect to use it

* Reminder: Each ADT has one or more *implementations* as data structures

* Each ADT
  * Philosophy: Use an array, Use linked nodes, Build a tree (+ variations)
  * Details (how the methods actually work)
  * Running time!

Lists: Collections in which you can visit the elements one-by-one without deleting them
* Key operations:
  * add
  * next: look at the next unvisited element
  * reset: restart our "visiting elements one by one"
  * hasNext: does this list have any more unvisited elements?
* Optional (and sometimes hard to implement)
  * remove
    * Note: Removing from an array is expensive, think about shifting
    * Note: Removing from a sequence of nodes is hard to think about (see example on real board in which we have a pointer to the third node in a NodeBasedQueue and want to get rid of it)
      * Idea one: Set the next link of the previous node to the next node of the node to be deleted.  Complicated (likely to go wrong, particularly given this oh-so-elegant specification) and expensive (you need to restart at the beginning until you find the right place)
      * Idea two: Copy the value from the next cell and then set your own next link to the next cell's subsequence cell. 

Terminology: Looking at elements one-by-one is often called "iterating" a list

Note from practice: Sometimes it's useful to iterate *the same list* more than once *at the same time*
* E.g., parallel programming
* E.g., computing some compound value that's based on pairs of elements

Terminology: The thing that keeps track of the state of iteration is called a "cursor"  (or an iterator)

Note: We now have two key ADTs:
* A list
  * add
  * remove (maybe)
  * get a new iterator
* An iterator
  * next
  * hasNext

Problem: Where do we add elements?
* Simple lists: Add it somewhere, I don't care where!
* Sequenced lists: Add it *right here*
  * At the beginning
  * At the end
  * Right before this thing I just looked at
  * Right after this thing I just looked at
* Sorted lists: Add it in such a way that I can iterate the values from smallest to largest

Differences:
* How many parameters to add
  * Simple lists: One (the thing to add)
  * Sorted lists: One (the thing to add)
  * Sequenced lists: One (beginning, end) or Two (before/after)
    * (in ADT SequencedList: addAfter(Object addMe, Iterator where)
* What order are the elements iterated?
  * Simple lists: Who cares, it's up to the implementer
  * Sequenced lists: The order that *I* specified
  * Sorted lists: The order that a Comparator specifies

Three interfaces: Mostly similar, some differences

Time to write Data Structures that implement these things

ArrayBasedSimpleList: Implement simple lists with arrays
* Where's the easiest place to add?  Some place less than the size of the array that's empty
  * The first empty space (design strategy: fill from left-to-right, keep track of how many elements)
    public void add(T addMe)
    {
      if (this.size >= this.elements.length) {
        RESIZE THE DAMN THING
      }
      else {
        this.elements[this.size] = addMe;
	this.size++;
      }
    }

VectorBasedSimpleList: A lot like array-based simple list, but easier
    public void add(T addMe)
    {
      this.elements.add(addMe);
    }
* What does an iterator look like?
  * index: Keep track of an index of the next value to visit
  * VectorBasedSimpleList vbsl: Keep track of the vector we're iterating
  public T next()
  {
    T tmp = this.vbsl.elements.get(this.index);
    this.index++;
    return tmp;
  } // next()
  public boolean hasNext()
  {
    return (this.index < this.vbsl.size)
  } // hasNext()