1
Programming II (CS300)
Chapter 9 (Part2): Iterators
MOUNA KACEM
mouna@[Link]
Iterable Interface and Iterators 2
Collection<T> Interface
Iterators
Iterable Interface
For-each loop
Collection Interface 3
Generic Interface Collection<T>
The interface Collection<T> specifies methods for performing some basic
operations on any collection of objects
public interface Collection<E> implements Iterable<E> {
// general operations that can be applied to various types of collections
// To explore the different operations defined in the interface Collection of
[Link], go to:
[Link]
}
Traverse a Collection of Objects 4
A collection of Objects of type T can be
an array,
an ArrayList,
a linkedList,
etc.
Need to traverse a collection to print out every item in the collection
for instance
Is there a generic way to do it?
Diverse ways to traverse a linear collection 0 1 2 3 4 5
{10, 20, 15, 30, 25, 5}
5
Arrays – for instance int[] data = new int[]{10, 20, 15, 30, 25, 5};
0 1 2 3 4 5
data 10 20 15 30 25 5
ArrayList – for instance ListADT<Integer> data = new ArrayList<>(); // add elements to the list
0 1 2 3 4 5 6 7 … [Link]-1
instanceof data
ArrayList 10 20 15 30 25 5 null null … null
size: 6
A chain of linked nodes given its head (Singly linked list) – LinkedNode<T> head
instanceof 0 1 2 3 4 5
LinkedList
10 20 15 30 25 5 X
head
tail
size: 6
Traverse a Collection of Objects 6
How to traverse an array of Objects?
use a for loop to iterate through all the array indices
How to traverse a singly linked list of Objects?
use a while loop in which you advance a pointer along the list
Variety of traversal mechanisms!
How to come up with a single generic
method to traverse a collection that works
for all kinds of collections that are stored in
wildly different forms?
Diverse ways to traverse a linear collection
Arrays – 7
int[] data = new int[]{10, 20, 15, 30, 25, 5};
ArrayList – data is instanceof ArrayList or ListADT
A chain of linked nodes given its head (Singly linked list)
Diverse ways to traverse a linear collection
Arrays – 8
int[] data = new int[]{10, 20, 15, 30, 25, 5};
ArrayList – data is instanceof ArrayList or ListADT
A chain of linked nodes given its head (Singly linked list)
Generic Way to Traverse a 9
Collection of Objects
The problem is solved by using iterators! (design pattern)
Iterator
an object that can be used to traverse a collection
Iterators are defined by a parameterized interface named Iterator<T>
@see [Link]
Different types of collections have iterators that are implemented in
different ways, but all iterators are used in the same way
An iterator provides a good way to iterate over a generic set type
Generic Way to Traverse a Collection of Objects 10
// create a new iterator to traverse a collection storing elements of type T
Iterator <T> itr = new SomeIterator<T>();
// Use the iterator to traverse the collection
while ( [Link]() ){ // while there are more elements in the iteration
// get the next element and use it (print it)
[Link]([Link]() + " ";
}
Generic Way to Traverse a Collection of Objects 11
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
[Link]()
10
Generic Way to Traverse a Collection of Objects 12
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
[Link]() [Link]()
10 20
Generic Way to Traverse a Collection of Objects 13
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
[Link]() [Link]() [Link]()
10 20 30
Generic Way to Traverse a Collection of Objects 14
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
[Link]() [Link]() [Link]() [Link]()
10 20 30 40
Generic Way to Traverse a Collection of Objects 15
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
[Link]() [Link]() [Link]() [Link]() [Link]()
10 20 30 40 50
Iterator <Integer> itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection 16
while ( [Link]() ){
[Link]([Link]() + " ";
}
// An iterator can be used only ONE
// Get a new instance of the iterator to traverse the collection a
// second time
itr = new SomeIterator<Integer>();
// Use the iterator to traverse the collection
while ( [Link]() ){
[Link]([Link]() + " ";
}
0 1 2 3 4
10 20 30 40 50
Question
17
List Abstract Data Type 18
public interface ListADT<T> { T refers to Any Type
// List of Operations
public void add(T newObject); // add at the end of this list
public void add(int index, T newObject); // add at a given index of this list
public boolean contains(T findObject); // checks whether this list contains a match
with findObject
public boolean isEmpty(); // checks whether the list is empty
public int size(); // returns the number of elements stored in this list
public int indexOf(T findObject); // returns the index of findObject within this list,
and -1 if no match found
public T get(int index); // returns the element stored at position index
public T remove(int index); // removes and returns the element at index
} // end ListADT generic interface
Practice Example
19
Implementation of an Iterator ListIterator to iterate through
an instance of a list given its reference of type ListADT
Practice Example
20
Implementation of an Iterator ListIterator to iterate through an
instance of a list given its reference of type ListADT
1. Write a while loop to traverse a list instanceof ListADT
2. Determine which data fields do we need to iterate through the list given its
reference of type ListADT
3. Determine the implementation of hasNext() and next()
int index = 0;
while(index < [Link]())
{
T next = [Link](index);
index++;
// use next
}
Question
Complete the missed line of code within the following [Link]() 21
method to implement appropriately its behavior.
Complete the missed line of code within the following [Link]() 22
method to implement appropriately its behavior.
T next = [Link](index);
index++;
return next;
Iterable interface 23
The Iterable interface is a generic interface of [Link] package.
public interface Iterable<T>
Iterable interface has one method to override
Iterator<T> interator()
returns an iterator over a set of elements of type T
For more details, please visit
[Link]
Question
24
Given the following class declaration, which of the following methods the
Bouquet class must override?
A.
B.
C.
D.
E.
For each loop 25
An object instance of a class that implements the [Link]<T>
interface can be target of the “for each” statement
Syntax
for (<ElementType> <variable> : <collection>){
<loop body> // Does not have any effect on the value of <variable> reference
}
A for-each loop can be used to traverse a collection IF AND ONLY IF the
collection implements the [Link] interface
The Iterable interface provides a clean and elegant way to code the
iteration functionality
In java, we can use the for-each loop to traverse an array
For each loop 26
The for each loop can be used to iterate over a collection if and only if
the collection implements the [Link] interface
The [Link]() method must be overridden
The [Link]() method returns a new reference to an iterator
(Iterator<T>) which can be used to iterate through the collection
The for each loop cannot be used to make change to the contents of a
collection.
Use a while loop or a classic for loop instead if you need to change the
content of the list