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