Java程序辅导

Friday 3/11
Announcements:
 Homework 5 due Today
 Lab 5 and Homework 6 Posted Soon
 Change in PLU Mask Policy
 Quiz 2 returned on Monday
For Next Time
 Read Section 2.9 Double-Linked List Implementation
Today
 Lab 4 Questions
 Iterators and ListIterators
 Homework 5 Questions
 In-class Exercise (if time permits)
Client Code to Print a List
for (int i=0; i< myList.size(); i++){
String element = myList.get(i);
System.out.println(element);
}
If myList is a linked list that contains n elements, 
what is the Big-O for this code segment?
O(n2)
Iterator
 An Iterator is conceptually between
elements in the list. next() returns an element 
and advances the iterator
LinkedList  myList
LinkedList O(n2) loop
for (int i=0; i iter = myList.iterator();
while (iter.hasNext()) {
String s = iter.next();
System.out.println(s);
}
Where does iter come from?
Iterator Interface
 The Iterator interface is defined in 
java.util
 The List interface has the abstract method  
iterator which returns an Iterator object 
that iterates over the elements of that list
Iterators and Removing Elements
 You can use the  Iterator remove()method to 
remove items from a list as you access them
 remove() deletes the last item returned
 You must call next()before each remove()
otherwise, an IllegalStateException will be 
thrown
 LinkedList.remove(i) vs. Iterator.remove()
LinkedList.remove(i) must walk down the list 
to remove the i-th element, it is O(i)
Iterator.remove removes the last item returned, 
and is O(1)
Iterators and Removing Elements 
Remove all elements from LinkedList myList
that equals some target value:  
//this code is inefficient and incorrect!!!
for (int i=0; i iter = myList.iterator();
while (iter.hasNext()) {
if(iter.next().equals(target))
iter.remove();
}
Iterator and ListIterator
(Client View)
 Iterator Limitations
An Iterator objects always starts at the 
beginning of the list
Traverses List only in the forward direction
Provides a remove method, but no add
method
 ListIterator extends Iterator, overcoming 
these limitations
ListIterator
 Like an Iterator, ListIterator is conceptually 
positioned between elements of the list
 ListIterator positions are assigned an index from 0
to size
 How do you get your hands on a ListIterator?
 Know how  to use a ListIterator (Client View)
ListIterator Interface
ListIterator Interface  -- Client View
Look at an example:
iter = myList.listIterator(2);
System.out.println(iter.next());
iter.remove();
System.out.println(iter.previous());
iter.add(“Liz”);
iter.remove();     
null “Tom” “Dick” “Harry” “Sam” null
0                                    1                                         2                                      3
0                                      1                                        2                                        3   4
 throws an exception
Homework 5 Questions
In-class Exercise
1. Start eclipse and create JavaProject PracticeIterator
2. Download IteratorClientView.java from the class 
website (In-class exercises) to your JavaProject
3. Follow the instructions in IteratorClientView.java