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