Transcript Iterators

Iterators
CS 367 – Introduction to Data Structures
Iterator
• Allows a user to step through each item in
a data structure
– array, vector, linked list, tree, etc.
• Two basic components
– hasNext()
• returns true if the iterator has any more items
– next()
• returns the next item in the iterator
Example
• Print out each item in a vector
Vector v = new Vector();
addItems(v);
Iterator it = v.iterator();
while(it.hasNext())
System.out.println(it.next().toString());
Iterator
hasNext() == true
next
hasNext() == true
next
hasNext() == false
next
Warning
• Note that the next pointer is out-of-bounds
after the last call to next()
– another call to next() will result in exception
• Should always call hasNext() before
calling next()
Implementation
• Three main ways to implement an iterator
– single class for an iterator
• requires all data structures to implement an iterator
specific interface
– create a separate, custom iterator class for
each data structure
– create a custom iterator class for each data
structure and make it an inner class inside the
appropriate data structure
Single Iterator Class
• Implement a single class called Iterator
• Force each data structure that allows
iterators to implement an iterator interface
interface DSIterator {
public int size();
public Object getIndex(int index);
Iterator Class
class Iterator {
private DSIterator ds;
private int nextItem;
public Iterator(DSIterator ds) {
this.ds = ds;
nextItem = 0;
}
public boolean hasNext() {
return nextItem < ds.size();
}
public Object next() {
Object obj = ds.getIndex(nextItem);
nextItem++;
return obj;
}
}
Questions
• What happens if user calls next() at end of
data?
• How many times can user to through
iterator?
• How does user go through the data again?
Notes on Single Iterator Class
• Advantages
– only have to write the iterator class once
• Disadvantage
– performance can suffer greatly for some data
structures
Linked List Example
class LinkedList implements DSIterator {
// start of normal linked list code
...
// end of normal linked list code
private int size; // increment (decrement) in add (delete) methods
public int size() {
return size;
}
public Object getIndex(int index) {
Object tmp = head;
for(int i=0; i<index; i++, tmp = tmp.next);
return tmp;
}
Linked List Example
• Notice the problem with the getIndex()
method
– O(n) performance
• Want our iterator to return the next item in
O(1) time
• Will need a different implementation of the
iterator for a list than for a vector
Custom Class
• Previous example shows the need for
custom iterator classes for different data
structures
• Custom class will:
– take data structure object through constructor
– set a pointer to the first data item
– define next() method that works in O(1) time
Linked List Implementation
class LLIterator {
private Node nextItem;
public LLIterator(LinkedList list) {
nextItem = list.head;
}
public boolean hasNext() {
return nextItem != null;
}
public Object next() {
Object obj = nextItem.data;
nextItem = nextItem.next;
return obj;
}
}
Notes on Custom Iterator Classes
• Advantage
– very good performance
• next() is always O(1)
• Disadvantage
– head of Linked List must be made public
• this is a bad thing – why?
– have to write a custom iterator for each data
type
• means the user must know which one to use for
which data type
Nested Iterator Class
• Java allows one class to be nested inside
another
• Nest class has full access to private data
of main class
– can now let iterator access head
– head is still kept as a private field
Full Example
• Another version of the linked list
interface Iterator {
public boolean hasNext();
public Object next();
}
class LinkedList {
private Node head;
// put all the usual stuff here
public class LLIterator implements Iterator {
private Node nextObject;
public LLIterator() {
nextObject = head;
}
}
public Iterator iterator() {
return new Iterator();
}
}
Notes on Nested Class
• Advantage
– get the same performance as custom class
• it still is a custom class
– encapsulation remains in tact
• head gets to stay private
• Disadvantage
– custom iterator for each data structure
– a bit more confusing to learn and understand
Using Iterators
• Assume a nested iterator class
public void printContents(Object ds) {
Iterator it = ds.iterator();
while(it.hasNext())
System.out.println(it.next().toString());
}
• The above code will work with any data
structure
– of course, it assumes the data structure class
supports iterators