Java程序辅导

Monday 3/14
Announcements:
 Lab 5 and Homework 6 are Posted
 Quiz 2 returned Today
For Next Time
 Do Lab 5 Before Lab
 Read Section 4.1 (Stacks)
Today
 Quiz 2 Questions or Lab 4 Questions
 KWLinkedList Implementation
 Lab 5 Before Lab
 In-class Exercise (Client View of Iterators)
Implementing the ListIterator
Interface
 KWListIter is an inner class of KWLinkedList
which implements the ListIterator interface
 There are three fields
KWListIter
nextItem
lastItemReturned
index   
null
0
KWLinkedList
Implementation
 We will define a KWLinkedList class which 
implements some of the methods of the List
interface
 What are the fields?
KWLinkedList Memory Diagram 
Node
next =
null = prev
data = "Tom"
KWListIter
nextItem = 
lastItemReturned = 
index = 1
KWLinkedList
head = null
tail = null
size = 3
Node
next =
= prev
data = "Harry"
Node
next = null
= prev
data = "Sam"
ListIterator iter;
iter = myList.listIterator(0);
iter.next();
public class KWLinkedList  {
// Data Fields
private Node  head = null;    
private Node  tail = null;    
private int size = 0;
//public KWLinkedList methods
// most are implemented using a ListIterator
private static class Node {
…
}//Node
private class KWListIter implements ListIterator {
…
}//KWListIter
Lab 5
public class KWLinkedList extends AbstractSquentialList{
//fields
private Node head;
private Node tail;
private int size;
//write three public methods 
private static class Node {
}
private class KWListIter implements ListIterator{
private Node nextItem;
private Node lastItemReturned;
private int index;
//write two public methods here
}//KWListIter
}//class
KWLinkedList.get(index)
Use a ListIterator
object to implement get:
1. Check for exception – is 
this necessary?
2. Obtain a list iterator that 
is positioned just before 
the Node at position 
index
3. Return the next item 
currently referenced by 
this iterator
/** Get the element at position
index.
@param index Position of 
item to be retrieved
@return The item at index
@throws 
IndexOutOfBoundsException
if the index is out of range 
(index < 0 || index >= size())
*/
public E get(int index) {
if (index<0 || index >= size) throw
new IndexOutOfBoundsException(); 
ListIterator iter =  
this.listIterator(index); 
return iter.next(); 
}
KWLinkedList.add(index,obj)
Use a ListIterator object to 
implement add:
1. Obtain an list iterator that is 
positioned just before the 
Node at position index
2. Insert a new Node containing 
obj before the Node
currently referenced by this 
iterator
/** Add an item at the specified
index.
@param index The index at 
which the object is
to be inserted
@param obj The object to be
inserted
@throws 
IndexOutOfBoundsException 
if the index is out of range 
(index<0 || index>size())
*/
public void add(int index, E obj) {
this.listIterator(index).add(obj);
}
It is not necessary to declare a 
local ListIterator; the 
method call listIterator
returns an anonymous 
ListIterator object
Inner Classes: Static and Nonstatic
 KWLinkedList contains two inner classes:
Node is declared static: can not access the data fields 
of its parent class, KWLinkedList
KWListIter cannot be declared static because its 
methods access and modify data fields of KWLinkedList
 An inner class which is not static can reference the fields of its 
parent object
 Since its parent class is already defined with the type 
parament , KWListIter cannot be declared as 
KWListIter; if it were, we would be hiding the type 
parameter of the parent class (KWLinkedList)
KWLinkedList Memory Diagram 
Node
next =
null = prev
data = "Tom"
KWListIter
nextItem = 
lastItemReturned = 
index = 1
KWLinkedList
head = null
tail = null
size = 3
Node
next =
= prev
data = "Harry"
Node
next = null
= prev
data = "Sam"
ListIterator iter;
iter = myList.listIterator(0);
iter.next();
Programmer’s View
ListIterator / Lab05 - Before Lab
Create Lab 5 Java Project and download KWLinkedList.java
Let myList be a LinkedList of size 4
 Draw the memory map for myList
a) Write client code that will create a ListIterator, 
myIter, that starts at the end of myList.
b) Write client code that will move myIter two positions left
c) Draw the memory map that includes the ListIterator
d) Write client code that moves myIter one position to the right
e) Draw the memory map that includes the ListIterator
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