Java's Iterator Interfaces
Chapter 8
Chapter Contents
The Interface Iterator
Implementing the Interface Iterator
• A Linked Implementation
• An Array-Based Implementation
The Interface ListIterator
• Using the Interface ListIterator
An Array-Based Implementation of the Interface
ListIterator
• The Inner Class
Java Class Library: ArrayList and LinkedList
Revisited
2
The Interface Iterator
Methods provided
• hasNext()
Determines if current entry exists
• next()
Returns reference to current entry, advances
iterator's marker to next entry
• remove()
Removes entry next has just returned
3
The Interface Iterator
Fig. 8-1 The effect of a call to next on a list
4
The Interface Iterator
Fig. 8-2 The effect of
iterator methods on a list.
5
The Interface Iterator
Fig. 8-2 The effect
of iterator
methods on a list.
6
Implementing the Interface Iterator
We add an inner class to implementations
of the ADT list
• A linked implementation with hasNext, next
• Array based list with all three methods of
Iterator
import [Link].*;
public interface ListWithIteratorInterface extends ListInterface
{
public Iterator getListIterator();
An
Aninterface
interfacethat
thatthe
thelist
list
} // end ListWithIteratorInterface
class
classcan
canimplement
implement
7
A Linked Implementation
import [Link];
import [Link];
public class LinkedListWithIterator implements ListWithIteratorInterface
{ private Node firstNode;
private int length;
< Implementations of the constructor and methods of the ADT list go here >
public Iterator getListIterator()
{ return new IteratorForLinkedList(); } // end getListIterator
private class IteratorForLinkedList implements Iterator
{ private Node currentNode; // current node in iteration
public IteratorForLinkedList()
{ currentNode = firstNode;} // end default constructor
< Implementations of methods in the interface Iterator go here. >
} // end IteratorForLinkedList
< Implementation of the private class Node (Segment 6.22) goes here. >
} // end LinkedListWithIterator
8
An Array-Based Implementation
import [Link].*;
public class ArrayListWithIterator implements ListWithIteratorInterface
{ private Object entry[]; // array of list entries
private int length;
private static final int INITIAL_SIZE = 25;
< Implementations of the constructor and methods of the ADT list go here;>
public Iterator getListIterator()
{ return new IteratorForArrayList(); } // end getListIterator
private class IteratorForArrayList implements Iterator
{
< Implementations of methods in the interface Iterator go here. >
} // end IteratorForArrayList
} // end ArrayListWithIterator
9
An Array-Based Implementation
Fig. 8-3 The array of list entries and current Index (a) just
before the call to next(); (b) just after the call to next() but
before the call to remove(); (c) after the call to remove() 10
The Interface ListIterator
Methods provided
• hasNext() Determines if current entry exists
• next() Returns reference to current entry,
advances iterator's marker to next entry
• remove() Removes entry next has just returned
• hasPrevious()
Determines if there is another entry to visit
• previous() Returns reference to current entry,
moves iterator's marker back to previous entry
11
The Interface ListIterator
Methods provided
• nextIndex(), previousIndex()
Gets index of next/previous entry
• add(Object newEntry)
Adds an entry to list before entry that next() would
have returned
• set (Object newEntry)
Replaces last entry in list that either next() or
previous()has returned
12
The Interface ListIterator
Fig. 8-4 The effect of a call to previous() on list.
13
The Interface ListIterator
Fig. 8-5 The indices returned by methods
nextIndex and previousIndex.
14
Array-Based Implementation
Interface ListIterator
Definition of an interface for list class
• Includes operations of the ADT list
• Returns instance of ListIterator instead of
Iterator
import [Link].*;
public interface ListWithListIteratorInterface extends ListInterface
{
public ListIterator getListIterator();
} // end ListWithListIteratorInterface
15
Array-Based Implementation
Interface ListIterator
import [Link].*;
public class ArrayListWithListIterator implements ListWithListIteratorInterface
{ private Object entry[]; // array of list entries
private int length; // current number of entries in list
private static final int INITIAL_SIZE = 25;
< Implementations of the constructor and methods of the ADT list go here; >
public ListIterator getListIterator()
{ return new IteratorForArrayList(); } // end getListIterator
private class IteratorForArrayList implements ListIterator
{
< Implementations of the methods in ListIterator go here. >
} // end IteratorForArrayList
} // end ArrayListWithListIterator
16
Array-Based Implementation
Interface ListIterator
Fig. 8-6 The array of list entries and currentIndex
(a) just before the call to add; (b) just after the call to add.
17
Array-Based Implementation
Interface ListIterator
Fig. 8-7 The array of list entries and currentIndex
(a) just before the call to previous(); (b) just after the
call to previous() but before the call to remove();
18
(c) after the call to remove()
Array-Based Implementation
Interface ListIterator
Fig. 8-8 a … c Possible contexts in which
the method remove() is called
19
Array-Based Implementation
Interface ListIterator
(d)
(e)
Fig. 8-8 d & e Possible contexts in which the
method remove() is called
20
Java Class Library: ArrayList and
LinkedList Revisited
Both of these classes contain methods
analogous to getListIterator
public Iterator iterator();
public ListIterator listIterator(int index);
Adheres to Iterator interface
Begins at list element indicated by index
• Where zero indicates first entry in the list
21