03/05/1400:39:27 119 CS 61B: Lecture 19 Wednesday, March 5, 2014Today’s reading: Sierra & Bates, p. 664.ENCAPSULATED LISTS (a case study in encapsulation)==================Homeworks 3, 4, and 5 introduced you to three different implementations oflinked lists, each fundamentally different.With the Homework 3 lists, if an application writer wants to query the identityof every item in the list without modifying the list, it takes timeproportional to the square of n, the number of items in the list (i.e.,Theta(n^2) time), because you have to use nth(i) to identify each item in timeproportional to i.The lists in Homeworks 4 and 5 allow an application to directly hold a node ina list. By alternating between the next() method and the item field or method,you can query all the list’s items in Theta(n) time. Similarly, if anapplication holds a node in the middle of a list, it can insert or delete citems there in time proportional to c, no matter how long the list is.The Homework 5 lists (SList and DList) are well-encapsulated, whereas theHomework 4 DList has flaws. I will discuss these flaws today to illustrate whydesigning the really good list ADTs of Homework 5 was tricky. Let’s ask somequestions about how lists should behave.(1) What happens if we invoke l.remove(n)--but the node n is in a different list than l? In Homework 4, Part II asks whether it is possible for an application to break the DList invariants. One way to do this is to mismatch nodes and lists in method calls. When an application does this, the "size" field of the wrong list is updated, thereby breaking the invariant that a list’s size field should be correct. How can we fix this? ADT interface answer: The methods remove(), insertAfter(), etc. should always update the right list’s "size" field. Implementation answer: It’s unacceptably slow to walk through a whole list just to see if the node n is really in the list l. Instead, every node should keep a reference to the list that contains it. In Homework 5, each ListNode has a "myList" field.(2) Should insertAfter(), remove(), etc. be methods of List or ListNode? Normally, we expect the methods that modify a data structure (like a List) to be methods within that data structure’s class. However, if we define methods like insertAfter() and remove() in the ListNode class, rather than the List class, we completely avoid the question of what happens if they’re invoked for a node that’s not in "this" list. This way, the interface is more elegant. ADT interface answer: the list methods are divided among List and ListNode. Some methods of List | Some methods of ListNode | public boolean isEmpty() | public Object item() public void insertFront(Object item) | public ListNode next() public ListNode front() | public void insertAfter(Object item) Implementation answer: again, each node has a "myList" field so we can update a list’s "size" field when we call n.remove(), n.insertAfter(), etc.(3) What happens if we invoke l.remove(n), then l.insertAfter(i, n)? Another way to trash the DList invariants is to treat a node that’s been removed from a list as if it’s still active. If we call insertAfter on a node we’ve already removed, we may mangle the pointers. AARGHH!!!--- --- --- --- --- --- ---|x|<->|n|<->|y| --remove()-> |x|<----->|y| --insertAfter()-> |x|---------->|y|--- --- --- --- --- --- --- ^ ^ ^ ^ | --- | | --- --- | \---|n|---/ \--|n|<->| |<-/ --- --- --- The result violates the invariant that if x.next == y, then y.prev == x. We would prevent the pointer mangling if remove(n) set n’s pointers to null, but that wouldn’t stop insertAfter() from incrementing the list’s "size" field (or throwing a NullPointerException), which is not a reasonable result. Calling remove(n) twice on the same node also corrupts "size". How can we fix this? ADT interface answer: After n.remove() is executed, removing n from the list, n is considered to be an "invalid" node. Any attempt to use n, except to call n.isValidNode(), throws an exception. Why do we change the node, rather than erasing the reference to it? First, the remove() method can’t erase the reference, which is passed by value. Second, there might be lots of other references to the same node, and we need to erase all of them too! All those other references could be used to corrupt the data structure if the node itself isn’t neutralized. Implementation answer: When an item is removed from a list, the corresponding ListNode’s "myList" reference is set to null. This is just a convenient way to mark a node as "invalid". The "next" and "prev" references are also set to null. These steps eliminate opportunities for accidentally corrupting a list as illustrated above. (Also, they help Java’s garbage collection to reclaim unused DListNodes. We’ll discuss garbage collection near the end of the semester.) Any ListNode whose "myList" reference is null is considered "invalid", and any attempt to use it will incite an exception.03/05/1400:39:27 219(4) What happens if we walk off the end of a list? (Using the next() method.) ADT interface answer: In Homework 4, if you invoke next() on the last node in a list, it returns null. In Homework 5, it returns an invalid node instead. There are two reasons for this change. First, it provides consistency, because invoking next() at the end of a list yields the same result as removing a node. Second, if you call a method on the result-- for instance, n.next().item()--it throws an InvalidNodeException instead of a NullPointerException. This eliminates ambiguity; you can catch an InvalidNodeException without wondering why it was thrown, whereas
View Full Document
Unlocking...