Transcript Lists and Iterators

Chapter 6
Lists and Iterators
Objectives
Array Lists and Vectors: ADT and
Implementation
Node Lists: ADT and Implementations
Iterators: ADT and Implementation
List ADTs and Collections
Design Patterns
– Adaptor Pattern
– Position Pattern
– Iterator Pattern
Lists and Iterators
CSC311: Data Structures
1
The Array List (Vector) ADT
The Array List ADT
extends the notion of
array by storing a
sequence of arbitrary
objects
An element can be
accessed, inserted or
removed by specifying
its rank (number of
elements preceding it)
An exception is
thrown if an incorrect
rank is specified (e.g.,
a negative rank)
Lists and Iterators
Main Array List operations:
– object get(int r): returns the
element at rank r without
removing it
– object set(int r, Object o):
replace the element at rank
with o and return the old
element
– add(int r, Object o): insert a
new element o to have rank r
– object remove (int r):
removes and returns the
element at rank r
Additional operations size() and
isEmpty()
CSC311: Data Structures
2
Applications of Array Lists
Direct applications
– Sorted collection of objects (elementary
database)
Indirect applications
– Auxiliary data structure for algorithms
– Component of other data structures
Lists and Iterators
CSC311: Data Structures
3
Adaptor Pattern
Adaptor Pattern:
adapting an existing
class to a new class
Contains an instance of
the existing class as a
instance field, and
implement each
method of the new
class by calling the
method of the instance
field object
Adapt Array List ADT to
Deque ADT
Lists and Iterators
class Deque {
private ArrayList al;
public Deque() {
al = new ArrayList();
}
public Object getFirst() {
return al.get(0);
}
public void addFirst(Object e) {
al.add(0, e);
}
public Object removeFirst() {
return al.remove(0);
}
…
}
CSC311: Data Structures
4
Array-based Implementation
Use an array V of size N
A variable n keeps track of the size of the
array list (number of elements stored)
Operation get(r) is implemented in O(1) time
by returning V[r]
V
0 1 2
Lists and Iterators
r
CSC311: Data Structures
n
5
Insertion
In operation add(r, o), we
need to make room for the
Algorithm add(i, e)
new element by shifting
for t = n - 1 to i do
forward the n - r elements
A[t+1]  A[t]
V[r], …, V[n - 1]
A[t]  e
In the worst case (r = 0), this
n  n+1
takes O(n) time
V
0 1 2
r
n
0 1 2
r
n
0 1 2
o
r
V
V
Lists and Iterators
n
CSC311: Data Structures
6
Deletion
In operation remove(r), we
need to fill the hole left by
the removed element by
shifting backward the n - r 1 elements V[r + 1], …, V[n - 1]
In the worst case (r = 0), this
takes O(n) time
V
Algorithm remove(i)
e  A[i]
for t = i to n-2 do
A[t]  A[t+1]
n  n-1
return e
0 1 2
o
r
n
0 1 2
r
n
0 1 2
r
V
V
Lists and Iterators
CSC311: Data Structures
n
7
Performance
In the array based implementation of an
Array List
– The space used by the data structure is O(n)
– size, isEmpty, get and set run in O(1) time
– add and remove run in O(n) time
If we use the array in a circular fashion,
add(0) and remove(0) run in O(1) time
In an add operation, when the array is
full, instead of throwing an exception,
we can replace the array with a larger
one
Lists and Iterators
CSC311: Data Structures
8
Growable Array-based Implementation
Consider an array list
implemented with array
In a add operation, when
the array is full, instead of
throwing an exception, we
can replace the array with
a larger one
How large should the new
array be?
– incremental strategy:
increase the size by a
constant c
– doubling strategy:
double the size
Lists and Iterators
Algorithm add(i, o)
if n = S.length - 1 then
A  new array of
size …
for j  0 to i-1 do
A[j]  S[j]
A[i] = o;
for ji+1 to n do
A[j] = S[j-1];
SA
CSC311: Data Structures
9
Comparison of the Strategies
We compare the incremental strategy and
the doubling strategy by analyzing the
total time T(n) needed to perform a series
of n add operations
We assume that we start with an empty
array list represented by an array of size 1
We call amortized time of an add operation
the average time taken by an add over the
series of operations, i.e., T(n)/n
Lists and Iterators
CSC311: Data Structures
10
Incremental Strategy Analysis
We replace the array k = n/c times
The total time T(n) of a series of n push
operations is proportional to
n + c + 2c + 3c + 4c + … + kc =
n + c(1 + 2 + 3 + … + k) =
n + ck(k + 1)/2
Since c is a constant, T(n) is O(n + k2), i.e.,
O(n2)
The amortized time of an add operation
is O(n)
Lists and Iterators
CSC311: Data Structures
11
Doubling Strategy Analysis
We replace the array k = log2 n
times
The total time T(n) of a series geometric series
of n add operations is
2
proportional to
4
1 1
n + 1 + 2 + 4 + 8 + …+ 2k =
n + 2k + 1 -1 = 2n -1
8
T(n) is O(n)
The amortized time of an add
operation is O(1)
Lists and Iterators
CSC311: Data Structures
12
Position ADT
The Position ADT models the notion of
place within a data structure where a
single object is stored
It gives a unified view of diverse ways
of storing data, such as
– a cell of an array
– a node of a linked list
Just one method:
– object element(): returns the element
stored at the position
Lists and Iterators
CSC311: Data Structures
13
Node List ADT
The Node List ADT
models a sequence
of positions storing
arbitrary objects
It establishes a
before/after
relation between
positions
Generic methods:
– size(), isEmpty()
Lists and Iterators
Accessor methods:
– first(), last()
– prev(p), next(p)
Update methods:
– set(p, e)
– addBefore(p, e),
addAftter(p, e),
– addFirst(e),
addLast(e)
– remove(p)
CSC311: Data Structures
14
Doubly Linked List
A doubly linked list provides a
natural implementation of the
Node List ADT
Nodes implement Position and
store:
– element
– link to the previous node
– link to the next node
prev
next
elem
node
Special trailer and header nodes
nodes/positions
header
trailer
elements
Lists and Iterators
CSC311: Data Structures
15
Insertion
We visualize operation addAfter(p, X), which returns
position q
p
A
B
C
p
A
q
B
C
X
p
A
Lists and Iterators
q
B
CSC311: Data Structures
X
C
16
Insertion Algorithm
Algorithm addAfter(p,e):
Create a new node v
v.setElement(e)
v.setPrev(p)
{link v to its predecessor}
v.setNext(p.getNext()) {link v to its successor}
(p.getNext()).setPrev(v) {link p’s old successor to v}
p.setNext(v)
{link p to its new successor, v}
return v {the position for the element e}
Lists and Iterators
CSC311: Data Structures
17
Deletion
We visualize remove(p), where p = last()
A
B
C
A
B
C
p
D
p
D
A
Lists and Iterators
B
CSC311: Data Structures
C
18
Deletion Algorithm
Algorithm remove(p):
t = p.element {a temporary variable to hold the
return value}
(p.getPrev()).setNext(p.getNext()) {linking out p}
(p.getNext()).setPrev(p.getPrev())
p.setPrev(null) {invalidating the position p}
p.setNext(null)
return t
Lists and Iterators
CSC311: Data Structures
19
Performance
In the implementation of the Node
List ADT by means of a doubly
linked list
– The space used by a list with n
elements is O(n)
– The space used by each position of
the list is O(1)
– All the operations of the List ADT run
in O(1) time
– Operation element() of the
Position ADT runs in O(1) time
Lists and Iterators
CSC311: Data Structures
20
Sequence ADT
The Sequence ADT is the
union of the Array List,
Deque, and Node List ADTs
Elements accessed by
– index, or
– Position
Generic methods:
– size(), isEmpty()
Bridge methods:
– atIndex(r)
– indexOf(p)
Lists and Iterators
CSC311: Data Structures
21
Applications of Sequences
The Sequence ADT is a basic, generalpurpose, data structure for storing an
ordered collection of elements
Direct applications:
– Generic replacement for stack, queue,
vector, or list
– small database (e.g., address book)
Indirect applications:
– Building block of more complex data
structures
Lists and Iterators
CSC311: Data Structures
22
Multiple Inheritance in the
Sequence ADT
Sequence has three super
interfaces: Node List, Array
List, and Deque
Node List-based methods:
–
–
–
–
–
–
–
–
–
–
first()
last()
prev(p)
next(p)
set(p, o)
addBefore(p, o)
addAfter(p, o)
addFirst(o)
addLast(o)
remove(p)
Lists and Iterators
Array List-based methods:
–
–
–
–
get(r)
set(r, o)
add(r, o)
remove(r)
Deque-based methods:
–
–
–
–
–
–
addFirst(o)
addLast(o)
removeFirst()
removeLast()
getFirst()
getLast()
CSC311: Data Structures
23
Iterator ADT
An iterator abstracts the process of
scanning through a collection of elements
Methods of the Iterator ADT:
– boolean hasNext()
– object next()
Implementation with an array or singly
linked list
An iterator is typically associated with an
another data structure
Two notions of iterator:
– snapshot: freezes the contents of the data
structure at a given time
– dynamic: follows changes to the data structure
Lists and Iterators
CSC311: Data Structures
24
Design Pattern: Iterators
We can augment the Stack, Queue, Vector, List
and Sequence ADTs with the following method to
iterate all elements:
– Iterator elements()
For ADTs that support the notion of position,
such as list and sequences, we can provide a
method to iterate all positions:
– Iterator positions()
Lists and Iterators
CSC311: Data Structures
25
Iterators in Java
Java.util.Iterator interface
Iterable ADT provides a method:
– Iterator(): returns an iterator of the elements in the
collection
For-Each loop
– Syntax:
for (type name: expression)
loop_statement;
– Equivalence:
for (Iterator <type> it=expresion.iterator();
it.hasNext();)
{
Type name = it.next();
loop_statement;
}
Lists and Iterators
CSC311: Data Structures
26
ListIterator
List iterator gives access to elements
inside a linked list
ListIterator protects the linked list
while giving access
ListIterator encapsulates a position
anywhere in the linked list
Lists and Iterators
CSC311: Data Structures
27
Conceptual View of the ListIterator
Think of an iterator as pointing between two links
The listIterator method of the LinkedList class gets a list
iterator
LinkedList list = . . .
ListIterator iterator = list.listIterator();
Lists and Iterators
CSC311: Data Structures
28
ListIterator Methods
The next method moves the iterator iterator.next();
– next throws a NoSuchElementException if you are
already past the end of the list
hasNext returns true if there is a next element
if (iterator.hasNext())
iterator.next();
The next method returns the object of the link that it
is passing
while iterator.hasNext()
{
Object obj = iterator.next();
//do something with the object
}
To move the list position backwards, use:
o
o
Lists and Iterators
hasPrevious
previous
CSC311: Data Structures
29
Collections in Java
Collection
Iterator
List
ListIterator
Map
Queue
Set
Lists and Iterators
CSC311: Data Structures
30