CSC152 2005F, Class 49: Linked Lists

Admin:
* Questions on the exam?
* Other notes

Overview:
* Review of list basics
* An array implementation
* Using nodes
* Doubly-linked lists
* Circularly-linked lists

/Exam Questions/
* Will you post answers to last problem on exam 2 (binary search)?
  Yes.

/Lists/
* Dynamic, homogeneous collections you can iterate
* Three ways to think about the order of iteration
  * Order controlled by the list implementer: Simple Lists
  * Order controlled by the client: Sequenced Lists
  * Order controlled by a comparator (smallest to largest): Sorted Lists
* Sorted Lists are *not* Priority Queues
  * "get" for priority queues removes elements
  * "get" for lists just visits them
* Typical design decisions for lists
  * How do we represent "where we are in the iteration"?
    * "Cursor" that moves
    * "Position" that doesn't.
  * Do we support simulataneous iterations?  Yes
  * What happens to cursors/iterations when we add/delete elements?
    * INVALIDATE
* Methods
  * See SimpleList.java SortedList.java and SequencedList.java
* How do we implement all of these methods?
  * Use an array or vector
  * Link nodes together linearly
  * Build a tree

/Implementing Simple Lists with Vectors/

* Fields for VectorBasedSimpleList
  * Vector<T> contents;
* Fields for VectorBasedListCursor
  * int index;
* Iterating
  * Implement front
    * Create a new VBLC with index = 0
  * Implement get
    * Get the index from the VBLC
    * Use that to index into the vector
  * Implement advance
    * Increment the index from the VBLC
* Mutating
  * Implement add
    * Add at the end using the built-in Vector operation
  * Implement remove
    * Pull out the thing at the position
    * Either slide over or move the last thing into that position
      * Use Vector.remove() to slide over

/Problems/

* Doesn't expand easily
* Therefore, explore other implementations

/Linearly Linked Nodes: Linked List/
* Fields for LinkedSimpleList
  * Node<T> front
  * Node<T> back
* Fields for LinkedListCursor
  * Node<T> pos
* Iterating
  * Implement front
    * Build a new cursor using the front field
  * Implement get
    * Get the "value" field of the node referred to by the cursor
  * Implement advance
    * pos = pos.next
* Mutation
  * Add
    * To add at the back
      * Make a new node
      * Link the old back to that new node
      * Make back refer to that new node
  * Remove
    * Make the pointer from the prior node point to the next node
      * It's annoying to get the prior node

/Dealing with Remove Troubles/

* Use "removeNext" rather than "remove"
* Don't support "remove" at all
* Add a "prev" link to the previous node
  * this.next.prev = this.prev;
  * this.prev.next = this.next;
  * this.next = null;
  * this.prev = null;
* Lists built with nodes with prev/next links are called "Doubly-Linked Lists"
* Problem with doubly-linked lists: Lots of special cases (okay, only a few, but there are special cases)
* Solution: Have a fixed node that comes after the last node and before the first.  That node holds the "front" and "back" links
* Such lists are called "Circularly-linked lists"
  * How do you prevent looping?
    public void advance(LinkedListCursor llc)
    {
      llc.pos = llc.pos.next;
      if (llc.pos == this.reallyspecialnode)
        llc.pos = null; // off the list
    }