ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
List: iterative list processing
by
Marcel Turcotte
Version March 20, 2020
Preamble
Preamble
Overview
Overview
List: iterative list processing
We compare the computational time required to traverse a linked list when statements have
access to the nodes of the list against the implementation using the methods of the
interface of the list. We explore an efficient implementation without accessing the nodes of
the list directly.
General objective :
This week you will be able to explain and use an iterator.
1 65
Foreword
The topics covered in this module will reinforce the notions of encapsulation and
object-oriented programming, including the notion of the state of the object, as
well as the interfaces.
It is also an opportunity to informally introduce the complexity of computation
(asymptotic analysis) that will be presented to you in the data structure course.
2 65
Preamble
Learning objectives
Learning objectives
Compare the time required to traverse a linked list, discuss the case where statements
have access to nodes in the list compared to the implementation having access only to
the methods of its interface.
Compare nested static and non-static Java classes.
Modify the implementation of an iterator in order to add a method to it.
Lectures:
Pages 89-96, 103-112 of E. Koffman and P. Wolfgang.
3 65
Preamble
Plan
Plan
1 Preamble
2 Motivation
3 Concept
4 Implementation 1.0
5 Implementation 2.0
6 Implementation 3.0
7 Prologue
4 65
Motivation
Motivation
Problem
Motivation
You must devise a method to traverse a linked list.
5 65
Motivation
Details
Details
We’re working with an singly linked implementation of the interface List.
pub l i c i n t e r f a c e L i s t
boolean add (E e lement ) ;
E get ( i n t i n d e x ) ;
boolean remove (E e lement ) ;
i n t s i z e ( ) ;
}
The difficulties would be the same if the list was doubly linked.
We’ll call this implementation LinkedList.
6 65
An example of a list
L i s t
c o l o r s = new L i n k e d L i s t
c o l o r s . add ( ” b l e u ” ) ;
c o l o r s . add ( ” b l anc ” ) ;
c o l o r s . add ( ” rouge ” ) ;
c o l o r s . add ( ” j aune ” ) ;
c o l o r s . add ( ” v e r t ” ) ;
c o l o r s . add ( ” orange ” ) ;
7 65
Motivation
Internal implementation
Implementation A : inside the class
Inside the class LinkedList, we have access to the implementation details. In
particular, we have access to the nodes.
Give an implementation:
8 65
Motivation
External implementation
Implementation B : out of the class
Outside the class LinkedList, we don’t have access to the implementation details. In
particular, we don’t have access to the nodes.
Give an implementation:
9 65
Remark
From outside the class LinkedList, we need to use E get(int pos) to access the
elements of the list.
10 65
Motivation
Computation time
Discussion
Compare the runtime of the two implementations (internal and external).
Is the implementation of the inside the class faster or slower?
Are the differences minor or major?
11 65
Computation time
These are the execution times in nanoseconds for lists of increasing size.
# nodes A B
20,000 73,214 523,248,106
40,000 138,208 2,054,870,866
80,000 277,909 8,430,799,795
160,000 671,434 36,546,381,116
320,000 1,461,222 157,744,738,581
640,000 3,428,519 655,822,468,389
1,280,000 5,922,119 45 minutes!
For 1, 280, 000 elements, it takes about 45 minutes to go through the list with calls to
get(pos), whereas it only takes 5.92 milliseconds for the approach A.
12 65
Motivation
Discussion
Discussion
How do you explain that difference?
For each implementation, what mathematical relationship is there between the
number of elements in the list, n, and the computation time?
Complete the sentence: every time the number of elements n doubles, the
computation time . . .
13 65
Give the implementation of the method E get(int pos).
Therefore, the implementation of B
f o r ( i n t i =0; i < c o l o r s . s i z e ( ) ; i ++) {
System . out . p r i n t l n ( c o l o r s . ge t ( i ) ) ;
}
Is equivalent to this:
Number of nodes visited
Call # of nodes visited
get(0) 1
get(1) 2
get(2) 3
get(3) 4
. . .
get(n-1) n
15 65
Motivation
Conclusion
Discussion
Implementation A visits n nodes.
Implementation B visits n2 nodes!
16 65
Concept
Concept
Objective
Concept
Objective: Devise an approach to traverse the list one and only once.
The user of the list will not have access to the implementation (p.next and others)!
The proposed solution will be applicable in a very specific context, when all nodes of
the list are visited sequentially.
This is not a general solution to speed up get(i).
17 65
Iterator
The iterator is a uniform and general mechanism for traversing a variety of data
structures, such as lists, but also trees and others (see CSI2110);
Provides access to the elements one element at a time;
Part of the Java collections.
18 65
Concept
Interface
Interface Iterator
pub l i c i n t e r f a c e I t e r a t o r
E next ( ) ;
boolean hasNext ( ) ;
}
19 65
Discussion : implementation
Which class will implement Iterator?
How do you create and initialize an iterator?
How do you move the iterator?
How do I detect the end of the iteration?
20 65
Implementation 1.0
Let’s develop an initial implementation that will be quite different from the final
implementation.
It will be a good intermediate step, though.
The class LinkedList implements the interface Iterator.
21 65
Implementation 1.0
Implementation 1.0
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e Node
// . . .
pub l i c E next ( ) { . . . }
pub l i c boo lean hasNext ( ) { . . . }
}
22 65
Implementation 1.0
Example
Contract
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
Conceptually, the iterator is to the left of the first element at the beginning of the
iteration.
When a call is made to the method next:
1. The iterator is moving forward;
2. Returns the value of the element visited.
A call to the method next when the list is empty or at the end of iteration (when
hasNext returns false) is an error and an exception will be thrown.
23 65
Example
L i s t l ;
l = new L i n k e d L i s t () ;
f o r ( i n t i =0; i <5; i ++) {
l . add (new I n t e g e r ( i ) ) ;
}
i n t sum = 0 ;
whi le ( l . hasNext ( ) ) {
I n t e g e r v = l . nex t ( ) ;
sum += v . i n t V a l u e ( ) ;
}
System . out . p r i n t l n ( "sum = " + sum ) ;
24 65
Example
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
0 1 2 3 4
^^ ^ ^ ^ ^
i n t sum = 0 ;
whi le ( l . hasNext ( ) ) {
I n t e g e r v = l . nex t ( ) ;
sum += v . i n t V a l u e ( ) ;
}
System . out . p r i n t l n ( "sum = " + sum ) ;
25 65
Implementation 1.0
Discussion
What are the necessary instance variables?
All it takes is one, current.
What’s the type of the variable current?
Node
What will be the initial value of current?
The initial value is null and conceptually, the iterator is positioned in before the first
element.
On the first call,
the method next positions the variable current on the first node, and returns the value
found there.
For each subsequent call,
next moves current to the next element.
head
B CA
current
Before iteration
head
B CA
current
after the call to next()
head
B CA
current
after the call to next()
head
B CA
current
after the call to next()
27 65
Implementation 1.0
Instance variable
Implementation 1.0
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e Node
p r i v a t e Node
// . . .
pub l i c E next ( ) { . . . }
pub l i c boo lean hasNext ( ) { . . . }
}
28 65
Implementation 1.0
next
Implementation 1.0
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e Node
p r i v a t e Node
pub l i c E next ( ) {
}
}
29 65
Implementation 1.0
30 65
Implementation 1.0
hasNext
Implementation 1.0
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e Node
p r i v a t e Node
pub l i c boo lean hasNext ( ) {
}
}
31 65
Implementation 1.0
32 65
Is it fast?
These are the execution times in nanoseconds for lists of increasing size.
# nodes Inside Iterator
20,000 73,214 113,817
40,000 138,208 167,639
80,000 277,909 324,540
160,000 671,434 758,642
320,000 1,461,222 1,760,357
640,000 3,428,519 3,717,519
1,280,000 5,922,119 7,239,676
For 1, 280, 000 elements, the computation time is 7.2 milliseconds, barely 13% slower
than the implementation having access to the elements!
33 65
Implementation 1.0
Discussion
Discussion
What’s the biggest restriction of our implementation?
Only one iteration at a time.
What does it take to overcome that limitation?
Several references. One reference per iterator.
34 65
Implementation 2.0
Implementation 2.0
Memory diagram
Memory diagram
Discuss this memory diagram.
head
DB CA
current current
35 65
Discussion
head
DB CA
current current
LinkedList does not implement the interface Iterator.
The iterator is an object that has an instance variable, current, of type Node
As many iterators as it takes.
The iterator must have access to the elements of the list.
A first level class wouldn’t have access to the elements.
Suggestions?
That’s right, the iterator is a nested class.
36 65
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
An itrator must belong to a given list.
An itrator must access the variable head from its list.
pub l i c E next ( ) {
i f ( c u r r e n t == nu l l ) {
c u r r e n t = head ;
} e l s e {
c u r r e n t = c u r r e n t . nex t ;
}
i f ( c u r r e n t == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
re tu rn c u r r e n t . v a l u e ;
}
Memory diagram
Discuss this memory diagram.
head
DB CA
current
i
current
j
myList
myList
38 65
Implementation 2.0
Instance variables and constructor
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r
p r i v a t e Node
p r i v a t e L i n k e d L i s t
p r i v a t e L i s t I t e r a t o r ( L i n k e d L i s t
t h i s . myL i s t = myLis t ;
c u r r e n t = n u l l ;
}
pub l i c boo lean hasNext ( ) { . . . }
pub l i c E next ( ) { . . . }
}
p r i v a t e Node
}
Implementation 2.0
next
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r
p r i v a t e Node
p r i v a t e L i n k e d L i s t
pub l i c E next ( ) {
i f ( c u r r e n t == n u l l ) {
c u r r e n t = ;
} e l s e {
c u r r e n t = c u r r e n t . nex t ;
}
i f ( c u r r e n t == n u l l ) {
throw new NoSuchElementExcept ion ( ) ;
}
r e t u r n c u r r e n t . v a l u e ;
}
pub l i c boo lean hasNext ( ) { . . . }
}
p r i v a t e Node
}
Implementation 2.0
hasNext
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r
p r i v a t e Node
p r i v a t e L i n k e d L i s t
pub l i c E next ( ) { . . . }
pub l i c boo lean hasNext ( ) {
i f ( c u r r e n t == n u l l && != n u l l ) {
r e t u r n t rue ;
} e l s e i f ( c u r r e n t != n u l l && c u r r e n t . nex t != n u l l ) {
r e t u r n t rue ;
} e l s e {
r e t u r n f a l s e ;
}
}
}
p r i v a t e Node
}
Implementation 2.0
iterator
pub l i c c l a s s L i n k e d L i s t
p r i v a t e s t a t i c c l a s s Node
p r i v a t e s t a t i c c l a s s L i s t I t e r a t o r
p r i v a t e Node
p r i v a t e L i n k e d L i s t
p r i v a t e L i n k e d L i s t I t e r a t o r ( L i n k e d L i s t
t h i s . myL i s t = myLis t ;
c u r r e n t = n u l l ;
}
pub l i c E next ( ) { . . . }
pub l i c boo lean hasNext ( ) { . . . }
}
pub l i c I t e r a t o r
}
p r i v a t e Node
}
Implementation 2.0
Example
L i n k e d L i s t l ;
l = new L i n k e d L i s t () ;
// . . .
I t e r a t o r i ;
i = l . i t e r a t o r ( ) ;
whi le ( i . hasNext ( ) ) {
I n t e g e r v1 = i . nex t ( ) ;
I t e r a t o r j ;
j = l . i t e r a t o r ( ) ;
whi le ( j . hasNext ( ) ) {
I n t e g e r v2 = j . nex t ( ) ;
System . out . p r i n t l n ( ” ( “+v1+” , “+v2+” ) ” ) ;
}
}
Implementation 2.0
Computation time
Is it fast?
These are the execution times in nanoseconds for lists of increasing size.
# nodes Inside Iterator
20,000 73,214 113,817
40,000 138,208 167,639
80,000 277,909 324,540
160,000 671,434 758,642
320,000 1,461,222 1,760,357
640,000 3,428,519 3,717,519
1,280,000 5,922,119 7,239,676
For 1, 280, 000 elements, the computation time is 7.2 milliseconds, barely 13% slower
than the implementation having access to the elements!
47 65
Implementation 3.0
Implementation 3.0
Inner class
«Getting in Touch with your Inner Class»
www.javaranch.com/campfire/StoryInner.jsp
48 65
http://www.javaranch.com/campfire/StoryInner.jsp
Definition
An inner class is a non-static nested class.
An object of an inner (non-static) class has access to the variables and methods of
the object of the outer class from which it was created.
49 65
Implementation 3.0
next
Implementation 3.0
hasNext
Implementation 3.0
iterator
Implementation 3.0
Memory diagram
Inner class
head
DB CA
current
i
current
j
53 65
Classe interne
head
DB CA
current
i
current
j
54 65
Example
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
55 65
Implementation 3.0
Example
head
l1
DB CA
current
i
current
j
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
i f ( j . hasNext ( ) ) {
S t r i n g o = j . nex t ( ) ;
}
head
l1
DB CA
current
i
current
j
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
whi le ( j . hasNext ( ) ) {
S t r i n g o = j . nex t ( ) ;
}
head
l1
DB CA
current
i
current
j
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
i f ( i . hasNext ( ) ) {
S t r i n g o = i . nex t ( ) ;
}
head
l1
DB CA
current
i
current
j
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
head
l2
2 31
current
k
i f ( k . hasNext ( ) ) {
I n t e g e r o = k . next ( ) ;
}
head
l1
DB CA
current
i
current
j
head
l1
DB CA
current
i
current
j
head
l2
2 31
current
k
head
l2
2 31
current
k
whi le ( k . hasNext ( ) ) {
I n t e g e r o = k . next ( ) ;
}
Computation time
These are the computation times in nanoseconds for lists of increasing size.
# nodes Inside Iterator Get
10,000 43,508 66,849 1.118841e+08
20,000 49,233 66,986 4.619370e+08
40,000 99,714 108,464 1.873445e+09
80,000 240,057 252,130 8.404544e+09
160,000 592,818 615,779 2.892314e+10
320,000 1,039,555 1,142,309 1.401875e+11
640,000 2,328,335 2,448,321 6.258633e+11
1,280,000 5,124,979 4,896,708 2.753671e+12
2,560,000 11,500,576 11,700,579 1.476815e+13
For 2,560,000 elements, get(pos) is 1 million times slower than the iterator!
1.48e+13 ns = 4.1 hours.
61 65
Prologue
Summary
The iterator is a mechanism for traversing a list one element at a time.
The method hasNext returns true if a call to the method next is possible.
The method next returns the next element in the iteration.
An inner class is a nested non-static class.
Objects of inner classes have access to the variables and methods of the outer class.
62 65
Next module
List : recursive processing
63 65
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
64 65
Marcel Turcotte
Marcel.
École de science informatique et de génie électrique (SIGE)
Université d’Ottawa
65 / 65
Marcel.
Preamble
Overview
Learning objectives
Plan
Motivation
Problem
Details
Internal implementation
External implementation
Computation time
Discussion
Conclusion
Concept
Objective
Interface
Implementation 1.0
Example
Discussion
Instance variable
next
hasNext
Discussion
Implementation 2.0
Memory diagram
Instance variables and constructor
next
hasNext
iterator
Example
Computation time
Implementation 3.0
Inner class
next
hasNext
iterator
Memory diagram
Example
Prologue