COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 8-3 : OOD10 Iterable and Iterator
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Java interfaces Iterable and Iterator
ITERABLE and ITERATOR
REMEMBER THE FOR-EACH LOOP?
int[] numbers = {1,2,3,4,5};
for(int element: numbers) {
System.out.println(element); }
The for-each loop (also called enhanced for loop) can make your code more readable and can be convenient to use. It is not helpful when you need to refer to the index of an element. For certain data structures is the only loop we can use…
ITERABLE AND ITERATOR
The use of a for-each loop is made possible by the use of two interfaces: Iterator and Iterable.
For beginners, the two interfaces are often confusing. Even though they are similar, they refer to two different things:
Objects of type Iterable are representations of a series of elements that can be iterated over. (e.g. a specific ArrayList)
Objects of type Iterator allows you to iterate through objects that represent a collection (a series of elements).
JAVA ITERABLE INTERFACE
public interface Iterable
}
A class that implements Iterable needs to implement the iterator() method. The iterator() method returns an object of type Iterator that can then be used to iterate through the elements of this instance.
A class that implements Iterator needs to implement the methods hasNext() and next().
public interface Iterator
T next(); // returns current,
// and advances to next
void remove(); // optional, ignore it
}
OBSERVATION
public interface Iterable
}
The iterator() method returns an iterator to the start of the collection. Using hasNext() and next() you can move forward in the collection. If you want to traverse the collection again, you’ll need a new Iterator.
public interface Iterator
T next(); // returns current,
// and advances to next
void remove(); // optional, ignore it
}
ITERABLE AND FOR-EACH LOOP
Implementing the Iterable interface allows an object to make use of the for-each loop. It does that by internally calling the iterator() method on the object!
HOW TO IMPLEMENT THE INTERFACES
As always when implementing interfaces, a class that implements an interface must implement every method from such interface.
Generally, when we write a class that implements the interface Iterable we also write a class that implements the interface Iterator. Often, such class is defined as an inner class of the first class.
Why? To implement Iterable, we need to implement the method iterator(). Such method need to return an object of type Iterator that can iterate through the elements of a specific object of the outer class. We need a class that can create such object.
EXAMPLE
public class MyCollection
return new MyIterator
}
}
In general, if the class MyIterator is used only by the class MyCollection, good practice is to make that class a private inner class of MyCollection.
public class MyIterator
: }
}
SLinkedList
iterator() returns an object of type Iterator that points to the head of the provided list.
next() returns the element of the list that the Iterator is currently referencing, and then moves to the next node.
public class SLinkedList
private SNode
public SLLIterator iterator() {
return new SLLIterator(this); }
private class SLLIterator implements Iterator
SLLIterator(SLinkedList
cur = list.head; }
public boolean hasNext() {
return (cur != null);
}
public E next() {
SNode
cur = cur.next;
return tmp.element;
} }
}
THE BIG PICTURE
interface
Iterable
iterator()
extends
extends
interface
Iterator
next() hasNext()
interface
Iterable iterator()
interface
Collection
interface
List
implements
implements
implements
class
SLLIterator
SNode next() Boolean hasNext()
class
SLinkedList
: SLLIterator iterator()
class
LinkedList
EXAMPLE
Suppose we have a SLinkedList of Shapes:
SLinkedList
iter
Then by calling iterator() we create an object of type Iterator that points to the head of the list.
Iterator iter = list.iterator();
list
head
size
4
null
SLinkedList
Shape s;
s
list
head
size
null
4
SLinkedList
Shape s;
Iterator
s
list
iter1 iter2
head
size
null
4
SLinkedList
Shape s;
Iterator
s = iter1.next();
iter1
iter2
s
head
size
list
The iterators iterate over nodes, not Shapes. The next()
method returns a Shape.
null
4
SLinkedList
Shape s;
Iterator
s = iter1.next();
s = iter1.next(); iter1
iter2
s
head
size
list
null
4
SLinkedList
Shape s;
Iterator
s = iter1.next();
s = iter1.next(); iter1 s = iter2.next();
iter2
s
head
size
list
null
4
SLinkedList
Shape s;
Iterator
s = iter1.next();
s = iter1.next(); iter1 s = iter2.next();
s = iter2.next();
iter2
s
head
size
list
null
4
SLinkedList
Shape s;
Iterator
s = iter1.next();
s = iter1.next(); iter1 s = iter2.next();
s = iter2.next();
s = iter2.next();
head
size
s
iter2
list
null
4
ITERATING THROUGH ELEMENTS IN A LINKED LIST
What is the time complexity of the following two snippet of code? (suppose the size of the list is N)
for (k = 0; k < list.size(); k ++) System.out.println(list.get( k ));
for (E element : list) System.out.println(e);
In the next videos: Induction and Recursion