CSC152 2005F, Class 48: Implementing Lists with Arrays Admin: * BST lab due. * Exam 3 distributed. Overview: * About lists * Three kinds of lists * Cursors and positions * ADTs * Using vectors to implement 'em Lists * Our final ADT (or set of ADTs) * PAMI * Philosophy: What is a list? * A homogeneous collection of values * With an order, (first to last) * With potentially fast addition * Dynamic * Perhaps more open removal than in a queue or a stack * General philosophy: A list is a collection you can *iterate* - visit the elements one by one * SimpleLists - you get to iterate the elements, but you don't control the order ("visit" != "delete", so you can re-iterate the list) * SequencedLists - the client gets to control the order in which things are iterated * SortedLists - when you iterate the elements, you get them in the order from smallest to largest * Key difference: Who control order of iteration? SimpleList - Implementer SequencedList - Client SortedList - Comparator * Warning! Don't discuss in terms of numeric index * A problem in describing lists: How do you refer to the current "place" in the iteration * Strategy one: Use a "position" Lists provide a front() operation Positions provide a Position nextPosition() operation Lists provide a get(Position pos) operation * Strategy two: Use a "cursor" Lists provide a getCurosr operation that returns the cursor at the front of the list Cursor provides void advance() (maybe retreat()) Cursor provides get() (what does the cursor refer to?) "Cursor" derives from the latin word for "run"; the run through the list * Strategy three: Have the list keep track of its current position * Only allows one simultaneous iteration * We'll use strategy two (Cursors) SimpleList Methods * void add(T thingtoadd) * int size() * Cursor getCursor() // Get a cursor that starts at the front of the list. Cursor Methods * T get() // non-mutating * void advance() // mutates // Fails when we try to advance beyond the end // Nick's version wraps around * void retreat() // mutates // Fails when we try to retreat before the beginning // Nick's version wraps around * boolean atEnd() * boolean atFront() * T remove() // removes and returns the current thing // advances to the next thing? // One strategy: All cursors are invalid after remove // Another strategy: Need to do something behind the scene to keep all cursors valid * Cursor clone() Sample code to print all the value in a list c = lst.getCursor(); while (!lst.atEnd()) { pen.println(c.get()); c.advance(); } pen.println(c.get()); Question: * Should lists return cursors, or should lists be parameters to the cursor constructor? * Consider two implementations of lists (with two corresponding implementations of cursors). Implementation A should return cursors of type A, implementation B should return cursors of type B. What happens (in constructor view) if we try to construct a cursor of type B for a list of type A? SequencedList Methods * addToFront(T thingToAdd) * addToEnd(T thingToAdd) * int size() * SequencedListCursor getCursor() // Get a cursor that starts at the front of the list. SequenceListCursor Methods * addBefore(T thingToAdd) * addAfter(T thingToAdd) * And the rest from ListCursor SortedList Methods * Basically the same as SimpleLists