CSC152 2005S, Class 46: Implementing Lists with Arrays and Vectors Admin: * E.C. for Psych talk today at 4:15 * E.C. for Convo Thursday Overview: * How do we remove from a Vector-based simple list? * Choosing between vectors and arrays for ADTs * Look at Sun's decisions * Lab /Side Note? * Sam decided to use "Cursor" instead of "Iterator" Why? * Because we're keeping track of a position in the list * Sam didn't want to overlap with "Iterator" in the Java API /Removing!/ * Note the vectors provide a remove function! * Use remove(int index) * You can get the index from the cursor * Advantages: * Know what you're removing * It's easy! The folks who implemented Vectors did all the hard work * Disadvantages: * The Vector remove seems to "shift left", which is expensive O(n) * Can we do better than O(n) for remove? * Sure: Take the last element, shove it in the place of the thing to delete, and reduce the size * How do we do that? Read the docuemntation for Vector closely and then do the LAB /Java API/ * Why would the folks at Sun put the "remove" method in the iterator rather than in the list? list.remove(c) vs. c.remove(); * For similar reasons to the reason we have a cursor/iterator * Might be easier to keep track of stuff * Avoids the problem of a list saying "I didn't create this iterator!" * Avoids the problem of someone passing in the wrong kind of iterator * Removal is specific to the kind of data type * If the iterators are shared between things that make iterators, it avoids repetitious code in the those things * It is possible to pass only an iterator to a helper function and that helper function can remove, as necessary w/o otherwise affecting the list * Why would Sam still leave remove in the list interface? * When you pass a cursor to another method, the other method can look but not change /Lab/ 1 Copy files (as linked on today's page) SimpleList.java Cursor.java VectorBasedSimpleList.java VectorCursor.java TestVBSL.java 2 Implement and test the inefficient remove 3 Implement and test the efficient remove If you still have time 4 Implement and test a VectorBasedSequencedList * note that you probably want to extend VectorBasedSimpleList Questions! * How do I get the position? ((VectorCursor) position).pos * But what if c is not a VectorCursor? * The client is an idiot. * That's why Sun puts remove in the cursor. * Hint from Rolf! Did you hear it?