Transcript Iterable - Canisius College Computer Science

CSC 212 –
Data Structures
Lecture 23:
Iterators
Question of the Day

Thieves guild states it will sell to members:
lock picking kits  $0.67 each
40’ rope
 $2.12 each
Wire cutters
 $4.49 each
How much would one pay for 4 lock
picking kits, 8 ropes, and 5 wire cutters?

Nothing, they’d steal it.
List ADT

Accesses all elements in a Collection
 Can
access all elements without removals
 set added to accessors and removals

Lists differ how they provide access
 IndexList
access via integer ranks
 PositionList access via relative
Position

What then defines a List?
 Lists
are Iterable
Iterators

Scans collection’s elements
 Start
processing with first element…
 …then process second element…
 …then the third element…
 …and so on until processed last element

(Obviously) Associated with other ADTs
 Provides
mean of processing elements
 Debug structures like Stack, Queue, &
Deque
Using Iterators
Loops can rely on using Iterators
 Improves modularity

 Use

code with any collection providing iterator
Improves reuse
 Leave ADT
implementation issues to Iterator
 Write very generic, simple code
Iterator Interface

Important interface defined by Java:
import java.util.Iterator;
...
public class It<E> implements
Iterator<E>{…}

Interface defines 3 methods:
E next();
boolean hasNext() throws
NoSuchElementException;
void remove() throws
UnsupportedOperationException;
How Iterators Work
Iterators keep cursor with current location
 Cursor is very implementation specific

structure – cursor could be index
 Linked list-based structure – cursor is Node(?)
 Array-based
Cursor Ø
elements
Iterable Data Structures

Data structure for which have an iterator
 Interface

defined as java.lang.Iterable
Used by List ADT
import java.util.Iterator;
import java.lang.Iterable;
...
public interface List<E> extends
Iterable<E> {
public Iterator<E> iterator();
}

Marks any instances will have an Iterator
Why Bother?

Java provides nice shortcut for Iterables
List<Integer> myList;
...
for (Integer i : myList) {
...
}
does the same thing as if we wrote:
List<Integer> myList;
...
for (Iterator j=myList.iterator();
j.hasNext();){
Integer i = j.next();
...
Limit of Iterator

May not want to iterate over elements
 Cannot
change element stored at locations
 Interface provides remove() operation, but…
 …that is slow, ugly, and painful (at best)

Often define Iterator over positions
 In
turn, returns each position
 With the position, can make changes desired

Adds method to PositionList interface:
public Iterator<Position<E>>
positions();
Your Turn

Get back into groups and do activity
Before Next Lecture…
Keep up with your reading!
 Start Week #10 Assignment
 Work on Programming Assignment #2
