CSC152 2004F, Class 54: Linked Lists

Admin:
* Alum Comedian, Saturday, 7 p.m., South Lounge, Be there
* Questions on the exam?  TOMORROW!

Overview:
* The OrderedList ADT
* Review: Linked Queues
* Linked lists
  * Adding
  * Iterating
  * Deleting

/Question: What operations would you add to simple lists for "lists in which the user controls the order of the values?/

* Order "This comes before this comes before this"
* Not "sorted order"
* NO USING COMPARATORS

* Adding (add "and the position")
  * addToFront(Object addMe)
  * addToRear(Object addMe)
  * addBefore(Cursor c, Object addMe)
  * addAfter(Cursor c, Object addMe)
* Deleting
  * remove(Cursor c)

/How do we implement these in ArrayBasedList?/

* addToFront(Object addMe)
  * Shift everything down
  * Or wrap around to confuse ourselves
* addToRear(Object addMe)
  * Same as add in simple lists
* addBefore(Cursor c, Object addMe)
  * Shift everything
* addAfter(Cursor c, Object addMe)
  * Shift everything

Shifting is easy but expensive

/Alternative implementation: Linked Nodes/

* Addition: Done
* Iteration: Done
* toSTring: Done
* Deletion:
  * (a) Get the previous node and reset its next pointer
    * Problem: How do we find the previous node?
  * (b) Shift all the values and then delete the last node.
    * Problem: Shifting may be expensive
  * (c) Add previous pointers
    * Problem: Harder to maintain
* Suppose we do (a).  
  * How do we find the previous node?
  * What happens if there is no previous node?

Normal solution: Put in two links in each node
  * One leads to the next node
  * One leads to the previous node

class DoublyLinkedNode {
	DoublyLinkedNode prev;
	Object data;
	DoublyLinkedNode next;
}

This solution also simplifies many of the other operations (addAfter, addBefore, etc.)

/Sorted Lists/

* Lists you iterate in sorted order

interface SortedList
* add(Object addMe) - adds the object in the appropriate place, with "appropriate" determined by the comparator
* remove(SimpleCursors here) - deletes the elements most recently returned by next
* getSortedCursor()

interface SortedCursor
* next() - move to the next element in the list and return that value
  Alternative: return a value, v, such that v is greater than or equal to all the values returned previously by next and is less than or equal to any other values still in the list
  Observation: You can define these operations without worrying about positions
* hasNext()

Where does the comparator come from?
* Probably has to be supplied in the constructor

Coming up tomorrow: An Overview of CS