Transcript Ch08v2.0
Iterators
Chapter 8
Slides by Steve Armstrong
LeTourneau University
Longview, TX
2007, Prentice Hall
Chapter Contents
• What is an Iterator?
• The Interface Iterator
Using the Interface Iterator
• An Inner Class Iterator
A Linked Implementation
An Array-Based Implementation
• Why Are Iterator Methods in Their
Own Class?
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Chapter Contents
• The Interface ListIterator
Using the Interface ListIterator
• An Array-Based Implementation of the
Interface ListIterator
The Inner Class
• Java Class Library: The Interface
Iterable
• Iterable and for-each Loops
• The Interface List Revisited
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
What Is an Iterator? 1
• A program component
Enables you to step through, traverse a
collection of data
Can tell whether next entry exists
• Iterator may be manipulated
Asked to advance to next entry
Give a reference to current entry
Modify the list as you traverse it
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface Iterator 3
• Found in java.util in Java Class
Library
• One of two iterator classes
• View source code of interface Iterator
Specifies a generic type for entries
• Note three methods
Method hasNext
Method next
Method remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface Iterator 4
• Position of an iterator is not at an entry
Positioned either before first entry
Or between two entries
Fig 8-1 The effect of a call to next on a list iterator
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface Iterator 6
• Consider a list of names created with the
code below (from chap 6)
• Then create a separate class iterator
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface Iterator
Fig. 8-2 The effect
of iterator methods
on a list.
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface Iterator
• Now execute several commands for
illustration
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface Iterator 7
Fig. 8-3 The effect of
the iterator
methods next and
remove on a list
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Multiple Iterators 10
• Possible to have
several iterators
of the same list
• View sample
code
Fig 8-4 Counting
the number of
times that Jane
appears in a list of
names
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Class SeparateIterator 12
• Used to connect an iterator with a list
Invoke SeparateIterator constructor
• View source code of SeparateIterator
Note data field that references list
Note the class is independent of how the list is
implemented – use ListInterface
• Note methods
hasNext
next
remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Class SeparateIterator
Fig. 8-6 A list and nextPosition
(a) just before the call to next;
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Class SeparateIterator
Fig. 8-6 A list and nextPosition (b) just after the call to
next but before the call to remove;
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Class SeparateIterator
Fig. 8-6 A list and nextPosition
(c) after the call to remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Inner Class Iterator 16
• An alternative to separate class iterators
• Define the iterator class as an inner class of the
ADT
Multiple iterations possible
Has direct access to ADT's data fields as inner class
• Required interface – Listing 8-3
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Inner Class Iterator 17
• View class LinkedListWithIterator
• Note methods declared in interface
Iterator
Found within inner class
IteratorForLinkedList
This inner class has data field nextNode to
track an iteration
nextNode references the node that method
next must access
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Inner Class Iterator 20
Fig. 8-7 An inner class iterator with direct access to the
linked chain that implements the ADT
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Array-Based Implementation 24
• View outline of ArrayListWithIterator
• Note methods required for the inner class
hasNext
next
remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Array-Based Implementation 28
Fig 8-8 The array of list entries and nextIndex
(a) just before to the call to next
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Array-Based Implementation
Fig 8-8 The array of list entries and nextIndex
(b) just after the call to next but before the call to remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
An Array-Based Implementation
Fig 8-8 The array of list entries and nextIndex
(c) after the call to remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Why are Iterator Methods in Their
Own Class? 29
• Consider modification of linked
implementations of list
Include the methods specified in Java
interface Iterator
Method remove not included for simplicity
• View outline of ListWithTraversal
Note similarities and differences with
Listing 8-4
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Why are Iterator Methods in Their
Own Class? 30
• Note that traversal methods do execute
quickly
Direct access to underlying data structure
• But …
Only one traversal can be in progress at a
time
Resulting ADT requires too many operations
(interface bloat)
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface ListIterator 32
• An alternative interface for iterators in Java
Class Library
• Enables traversal in either direction
• Allows modification of list during iteration
• View interface java.util.ListIterator
• Note methods
hasPrevious
previous
add
set
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface ListIterator 35
Fig. 8-9 The effect of a call to previous on a list
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface ListIterator 36
Fig. 8-10 The indices returned by the
methods nextIndex and previousIndex
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface ListIterator
37
• Assuming
The interface ListIterator implemented
as an inner class which implements ADT list
Iterator includes methods add, remove, set
Method getIterator added to ADT list
List called nameList, contains 3 names
Iterator traverse
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Using the Interface ListIterator 37
Note sample commands and output
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator 41
• First define an interface with
Operations from ADT list
Method getIterator
• Now define the class that implements the
ADT list
Same data fields and methods as version of
AList from chapter 5
Note inner class IteratorForArrayList
implements ListIterator
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator 43
Fig. 8-11 Possible contexts in which the method remove
throws an exception when called by the iterator traverse
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator
Fig. 8-11 Possible contexts in which the method remove
throws an exception when called by the iterator traverse
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator 48
Fig. 8-12 The array of list entries and nextIndex
(a) just before the call to add; (b) just after the call to add
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator 49
Fig. 8-13 The array of list entries and nextIndex
(a) just before the call to previous
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator
Fig. 8-13 The array of list entries and nextIndex
(b) just after the call to previous
but before the call to remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Array-Based Implementation of
ListIterator
Fig. 8-13 The array of list entries and nextIndex
(c) after the call to remove
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Java Class Library: The Interface
Iterable 51
• Consider Listing 8-10 The interface
java.lang.Iterable
Method has same purpose
as previous method
getIterator
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Java Class Library: The Interface
Iterable
• Listing 8-11 The interface
ListWithIteratorInterface
modified to extend Iterable
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
Iterable and for-each Loops 52
• Class which implements Iterable has
distinct advantage
• Able to use a for-each loop to traverse
objects in an instance of the class
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X
The Interface List Revisited 53
• Recall interface java.util.List from
segment 4.19 of Chapter 4
• It extends Iterable
Thus has method iterator
• Also has methods
Carrano, Data Structures and Abstractions with Java, Second Edition, (c) 2007 Pearson Education, Inc. All rights reserved. 0-13-237045-X