Transcript Analysis of Algorithms - University College Dublin

Analysis of Algorithms
• Running Time
• Pseudo-Code
• Analysis of
Algorithms
• Asymptotic Notation
• Asymptotic Analysis
• Mathematical facts
Analysis of Algorithms
T(n)
n4
Input
Algorithm
Output
1
Portions copyright Goodrich & Tommassia!
Average Case vs. Worst Case
Running Timeof an algorithm
• An algorithm may run faster on certain data sets than on others.
• Finding the average case can be very difficult, so typically
algorithms are measured by the worst-case time complexity.
• Also, in certain application domains (e.g., air traffic control,
surgery, IP lookup) knowing the worst-case time complexity is of
crucial importance.
worst-case
5 ms
}
4 ms
average-case?
3 ms
best-case
2 ms
1 ms
Analysis of Algorithms
A
B
C
D
Input
E
F
G
2
Measuring the Running Time
• How should we measure the running time of an algorithm?
• Approach 1: Experimental Study
– Write a program that implements the algorithm
– Run the program with data sets of varying size and composition.
– Use a method like System.currentTimeMillis() to get an accurate
measure of the actual running time.
t (ms)
60
50
40
30
20
10
Analysis of Algorithms
3
0
n
50
100
Beyond Experimental Studies
• Experimental studies have several limitations:
– It is necessary to implement and test the algorithm in order to
determine its running time.
– Experiments can be done only on a limited set of inputs, and
may not be indicative of the running time on other inputs not
included in the experiment.
– In order to compare two algorithms, the same hardware and
software environments should be used.
Analysis of Algorithms
4
Beyond Experimental Studies
• We will now develop a general methodology for
analyzing the running time of algorithms. In
contrast to the "experimental approach", this
methodology:
– Uses a high-level description of the algorithm instead of
testing one of its implementations.
– Takes into account all possible inputs.
– Allows one to evaluate the efficiency of any algorithm in a
way that is independent from the hardware and software
environment.
Analysis of Algorithms
5
Pseudo-Code
• Pseudo-code is a description of an algorithm that is more structured
than usual prose but less formal than a programming language.
• Example: finding the maximum element of an array.
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax  A[0]
for i 1 to n -1 do
if currentMax < A[i] then currentMax  A[i]
return currentMax
• Pseudo-code is our preferred notation for describing algorithms.
• However, pseudo-code hides program design issues.
Analysis of Algorithms
6
What is Pseudo-Code ?
• A mixture of natural language and high-level programming concepts that
describes the main ideas behind a generic implementation of a data
structure or algorithm.
-Expressions: use standard mathematical symbols to describe
numeric and boolean expressions -use  for assignment (“=” in Java)
-use = for the equality relationship (“==” in Java)
-Method Declarations:
-Algorithm name(param1, param2)
-Programming Constructs: - decision structures:
if ... then ... [else ... ]
- while-loops:
- repeat-loops:
- for-loop:
- array indexing:
-Methods:
Analysis of Algorithms
while ... do
repeat ... until ...
for ... do
A[i]
- calls:
object method(args)
- returns: return value
7
Analysis of Algorithms
• Primitive Operations: Low-level computations
independent from the programming language can be
identified in pseudocode.
• Examples:
– calling a method and returning from a method
– arithmetic operations (e.g. addition)
– comparing two numbers, etc.
• By inspecting the pseudo-code, we can count the number
of primitive operations executed by an algorithm.
8
Example analysis #1:
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
2 operations
currentMax = A[0]
for i = 1 to n -1 do
2 operations
if currentMax < A[i] then
2 operations
currentMax  A[i]
return currentMax
n-1 iterations
Analysis:
Total time = 1 + (n-1)(loop time)
loop time = 4 (assume the worst case -- test is always true)
Total time = 1 + (n-1)4 = 4n
Analysis of Algorithms
- 3 = T(n)
9
Example
of
Asymptotic
Analysis
#2
Algorithm prefixAverages1(X):
Input: An n-element array X of numbers.
Output: An n -element array A of numbers such that A[i] is the average of
elements X[0], ... , X[i].
1 operation
Let A be an array of n numbers.
for i 0 to n - 1 do
1 operation
a0
for j  0 to i do
i iterations with
a  a + X[j]
3 operations i=0,1,2, …, n-1
A[i]  a/(i+ 1)
4 operations
return array A
n iterations
• Analysis ...
total time = 1 + 0i<n (outer loop body time)
outer loop body time = 1 + (inner loop time) + 4
inner loop time = 0j<i (inner loop body time)
inner loop body time = 3
 total time = 1 + 0i<n(1+ 0j<i 3 + 4)
1i n i =
= 1 + 0i<n(5+ 3i)
2+n)/2
(n
= 1 + 0i<n5+ 3 0i<ni
= 1 + 5(n-1) + 3((n-1)2+n-1)/2
10
= 1.5n2+4n-4 = T(n)
Example #3
• A better algorithm for computing prefix averages:
Algorithm prefixAverages2(X):
Input: An n-element array X of numbers.
Output: An n -element array A of numbers such that A[i] is the average of
elements X[0], ... , X[i].
Let A be an array of n numbers.
s 0
1 operation
for i  0 to n do
s  s + X[i]
7 operations
A[i]  s/(i+ 1)
return array A
n+1 iterations
• Analysis ...
Total time = 1 + (n+1)(loop time)
Loop time = 7
Total time = 1 + (n+1)7 = 7n+8 = T(n)
• Compare with T(n) = 1.5n2+4n-4 for previous alg
• Which is better?
Analysis of Algorithms
11
Asymptotic Notation
• Goal: to simplify analysis by getting rid of
unneeded information (like “rounding”
1,000,001≈1,000,000)
• We want to say in a formal way 3n2 ≈ n2
• The “Big-Oh” Notation:
– given functions f(n) and g(n), we say that
f(n) is O(g(n))
if and only if
there are positive constants c and n0 such that
f(n)≤ c g(n) for all n ≥ n0
Analysis of Algorithms
12
Example
For functions f(n)
and g(n) (to the
right) there are
positive constants c
and n0 such that:
f(n)≤c g(n) for n ≥ n0
f(n) = 2n + 6
conclusion:
2n+6 is O(n).
Analysis of Algorithms
13
Another Example
On the other hand…
n2 is not O(n) because there is
no c and n0 such that:
n2 ≤ cn for n ≥ n0
(As the graph to the right
illustrates, no matter how large
a c is chosen there is an n big
enough that n2>cn ) .
Analysis of Algorithms
14
Asymptotic Notation (cont.)
• Note: Even though it is correct to say “7n - 3 is O(n3)”, a
better statement is “7n - 3 is O(n)”, that is, one should make the
approximation as tight as possible
• Simple Rule: Drop lower order terms
and constant factors:
7n-3 is O(n)
8n2log n + 5n2 + n is O(n2log n)
Analysis of Algorithms
15
Asymptotic Notation
(terminology)
• Special classes of algorithms:
logarithmic:O(log n)
linear:
O(n)
quadratic: O(n2)
polynomial: O(nk), k ≥ 1
exponential:O(an), n > 1
• “Relatives” of the Big-Oh
– O(f(n)): Big-Oh -- asymptotic upper bound
–  (f(n)): Big Omega--asymptotic lower bound
–  (f(n)): Big Theta--asymptotic tight bound
Analysis of Algorithms
16
Asymptotic Analysis of The
Running Time
• Use the Big-Oh notation to express the number of primitive
operations executed as a function of the input size parameter n.
• For example, we saw that the arrayMax algorithm has
T(n) = 4n-3 = O(n)
#2 is better
2
2
• Similarly example #2: 1.5n +4n-4 = O(n )
(“asymptotically
example #3:
7n+8 = O(n)
faster”) than #3
• Comparing the asymptotic running time
-an algorithm that runs in O(n) time is better than one that runs in O(n2) time
-similarly, O(log n) is better than O(n)
-hierarchy of functions:
log n << n << n2 << n3 << 2n
• Caution! Beware of very large constant factors. An algorithm
running in time 1,000,000 n is still O(n) but might be less efficient
on your data set than one running in time 2n2, which is O(n2)
17
Summary
1.
2.
3.
4.
we want to predict running time of an algorithm
summarize all possible inputs with a single “size” parameter n
many problems with “empirical” approach (measure lots of
test cases with various n and then extrapolate)
prefer “analytical” approach - examine algorithm to derive a
execution time function T(n) for the number of primitive
operations executed as a function of n (err on the side of pessimism
by always select the worst case)
5.
6.
7.
To select best algorithm, compare their T(n) functions
To simplify this comparision “round” the function using
asymptotic (“big-O”) notation
Amazing fact: Even though asymptotic complexity analysis
makes many simplifying assumptions, it is remarkably useful
in practice: if A is O(n3) and B is O(n2) then B really will be
faster than A no matter how they’re implemented.
Analysis of Algorithms
18
Math You might Need to Review
Logarithms and Exponents (Appendix A)
• properties of logarithms:
logb(xy) = logbx + logby
logb (x/y) = logbx - logby
logbxa = alogbx
logba=
logxa/logxb
• properties of exponentials:
a(b+c) = aba c
abc = (ab)c
ab /ac = a(b-c)
b = a logab
bc = a c*logab
Analysis of Algorithms
19
More Math to Review
• Floor:
x = the largest integer ≤ x
• Ceiling: x = the smallest integer ≥ x
• Summations: (see Appendix A)
• Geometric progression: (see Appendix A)
Analysis of Algorithms
20
Stacks, Queues, Linked Lists, Deques
•
•
•
•
Abstract Data Types (ADTs)
Interfaces and implementations
Stacks, queues, linked lists, dequeues
Java implementations
This week:
- complete P1-P3
- start P4
- read 4.1 - 4.3
Next week:
- complete P4
- read 4.4 - 4.5
Analysis of Algorithms
21
Portions copyright Goodrich & Tommassia!
More terminology: Abstract
Data Types (ADTs)
• An Abstract Data Type is an abstract specification of a data
structure
– what operations can be involved on an instance of the ADT
– Perhaps: invariants that are guaranteed to hold if the ADT is used
properly
– No code!
– Java’s “interface” construct is for specifying ADTs (except
invariants!)
• For example, if we are going to model a bag of marbles as
an ADT, we could specify that:
– Operations
• this ADT stores marbles
• this ADT supports putting in a marble and getting out a marble.
– Invariants
Analysis
of Algorithms
• No
marbles
are ever lost or spontaneously generated
22
Abstract Data Types (ADTs)
• There are lots of formalized and standard ADTs. (A bag of
marbles is not one of them.)
• In this course we are going to learn a lot of different standard
ADTs. (stacks, queues, trees...)
Analysis of Algorithms
23
Stacks
• A stack is a container of objects that are inserted
and removed according to the last-in-first-out
(LIFO) principle.
• Objects can be inserted at any time, but only the
last (the most-recently inserted) object can be
removed.
• Inserting an item is known as “pushing” onto the
stack.
“Popping” off the stack means removing
an (the M-R-U!) item.
• A PEZ® dispenser as an analogy:
Analysis of Algorithms
24
The Stack Abstract Data Type
• A stack is an abstract data type (ADT) that supports two main
methods:
– push(o): Inserts object o onto top of stack
– pop():
Removes the top object of stack and returns it;
if the stack is empty, an error occurs
• The following support methods should also be defined:
– size():
Returns the number of objects in stack
– isEmpty():Return a boolean indicating if stack is empty.
– top():
Return the top object of the stack, without
removing it; if the stack is empty, an error occurs.
Analysis of Algorithms
25
Stack Example #1
2
3
1
Laundry
Basket
Analysis of Algorithms
26
Example #2: Stacks in the Java Virtual Machine
• Each process running in a Java program has its own Java Method
Stack.
• Each time a method is called, it is pushed onto the stack.
• The choice of a stack for this operation allows Java to do several
useful things:
– Perform recursive method calls
– Print stack traces to locate an error
Analysis of Algorithms
27
Java Method Stack
newest method context
oldest method
context
Analysis of Algorithms
28
Java stuff
• Given the stack ADT, we need to code the ADT in order to use it in the
programs. You need to understand two program constructs: interfaces and
exceptions.
• An interface is a way to declare what a class is to do. It does not mention
how to do it.
– For an interface, you just write down the method names and the parameters.
When specifying parameters, what really matters is their types.
– Later, when you write a class for that interface, you actually code the
content of the methods.
– Separating interface and implementation is a useful programming technique.
• Interface example:
See lectures 3-4!
Analysis of Algorithms
29
A Stack Interface in Java
public interface Stack {
// accessor methods
public int size();
public boolean isEmpty();
public Object top() throws StackEmptyException;
// update methods
public void push (Object element);
public Object pop() throws StackEmptyException;
}
(yes - Java has a built-in Stack utility class!)
Analysis of Algorithms
30
Array-Based Stack in Java
We want to implement our Stack interface.
Lots of possibilities… one simple technique is to
use an array
public class ArrayStack implements Stack {
?
}
Analysis of Algorithms
31
An Array-Based Stack implementation
• Create a stack using an array by specifying a maximum size N for our
stack, e.g., N = 1000.
• The stack consists of an N-element array S and an integer variable t,
the index of the top element in array S.
NOTE: Array
indices start at 0, so
we initialize t to -1
Pseudo-code is to
the right.
Analysis of Algorithms
Algorithm size():
return t +1
Algorithm isEmpty():
return (t < 0)
Algorithm top():
if isEmpty() then
throw a StackEmptyException
32
return S[t] ...
Pseudo-Code (contd.)
Algorithm push(o):
if size() = N then
throw a StackFullException
tt+1
S[t]  o
Enable garbage collection
(re-use of S[t]’s memory,
if not referenced elsewhere
in program execution).
Analysis of Algorithms
the Stack interface doesn’t
know/care about this situation,
becomes stacks “in the abstract”
have infinite capacity.
However, our simple array
implementation does not
handle this requirement, so we
need to introduce an extra
exception even though it isn’t
mentioned in Stack
Algorithm pop():
if isEmpty() then
throw a StackEmptyException
e  S[t]
S[t]  null
t  t-1
return e
33
An Array-Based Stack (contd.)
• Both the push and pop methods runs in O(1) time
• The array implementation is simple and efficient.
• There is a predefined upper bound, N, on the size of the stack, which may be
too small for a given application, or cause a waste of memory.
• StackEmptyException is required by the interface.
• StackFullException is particular to this implementation.
Algorithm push(o):
if size() = N then
throw a StackFullException
tt+1
S[t]  o
“f(n)=O(1)” means “f(n) is a
constant,
independent of n”
Analysis of Algorithms
Algorithm pop():
if isEmpty() then
throw a StackEmptyException
e  S[t]
S[t]  null
t  t-1
return e
34
Array-Based Stack in Java
public class ArrayStack implements Stack {
// Implementation of the Stack interface using an array.
public static final int CAPACITY = 1000; // default capacity of the stack
private int capacity; // maximum capacity of the stack.
private Object S[ ]; // S holds the elements of the stack
private int top = -1; // the top element of the stack.
public ArrayStack( ) { // Initialize the stack
this(CAPACITY);// with default capacity
}
public ArrayStack(int cap) { // Initialize the stack with given capacity
capacity = cap;
S of= Algorithms
new Object[capacity];
Analysis
35
}
Array-Based Stack in Java (contd.)
public int size( ) { //Return the current stack size
return (top + 1);
}
public boolean isEmpty( ) { // Return true iff the stack is empty
return (top < 0);
}
public void push(Object obj) throws StackFullException{
// Push a new element on the stack
if (size() == capacity) {
throw new StackFullException(“Stack overflow.”);
}
S[++top] = obj;
}
Analysis of Algorithms
36
Array-Based Stack in Java (contd.)
public Object top( )// Return the top stack element
throws StackEmptyException {
if (isEmpty( )) {
throw new StackEmptyException(“Stack is empty.”);
}
return S[top];
}
public Object pop() // Pop off the stack element
throws StackEmptyException {
if (isEmpty( )) {
throw new StackEmptyException(“Stack is Empty.”);
}
Object elem = S[top];
S[top--] = null; // Dereference S[top] and decrement top
return elem;
}
Analysis of Algorithms
37
Array-Based Stack in Java (contd.)
class StackFullException extends RunTimeException {
// don’t need anything in here!
}
class StackEmptyException extends RunTimeException {
// don’t need anything in here!
}
Complete code available from
COMP-2001 web page
Analysis of Algorithms
38
Casting With a Generic Stack
• Have an ArrayStack that can store only Integer objects or Student
objects.
• In order to do so using a generic stack, the return objects must be cast
to the correct data type.
• A Java code example:
Integer year = new Integer(2001);
Stack s = new ArrayStack();
// Stacks can only store Objects
s.push(year);
// Returned values usually must be cast to appropriate class
int y = ((Integer) s.pop()).intValue();
Analysis of Algorithms
39
Queues
enter at end of line
Analysis of Algorithms
This week:
- complete P4, start P5
- finish reading chap 4
Next week:
- complete P5
- read 4.4 - 4.5
exit from front of queue
40
Queues
•A queue differs from a stack in that its insertion and removal routines
follows the first-in-first-out (FIFO) principle. (Remember: Stack=LIFO)
•Elements may be inserted at any time, but only the element which has
been in the queue the longest may be removed.
•Elements are inserted at the rear (enqueued) and removed from the front
(dequeued)
Analysis of Algorithms
41
Queue example - Web spider
Search engines (Altavista, Google, etc) uses programs called spiders
to discover new pages on the web (which can then be indexed for searching,
but that’s another story…)
newly discovered
pages
Input = some particular seed page
Repeatedly: select a previously-discovered
page, and traverse one of its hyperlinks.
To ensure broad coverage of the entire web,
spiders employ a queue data-structure
Analysis of Algorithms
to store & select discovered pages
next page to
42
be explored
The Queue Abstract Data Type
•The queue has two fundamental methods:
enqueue(o):
Insert object o at the rear of the queue
dequeue():
Remove the object from the front of the queue and
return it; an error occurs if the queue is empty
•These support methods should also be defined:
size():
Return the number of objects in the queue
isEmpty():
Return a boolean value that indicates whether the
queue is empty
front(): Return, but do not remove, the front object in the
queue; an error occurs if the queue is empty
Analysis of Algorithms
43
Queue ADT: Java interface code
interface Queue {
boolean isEmpty();
int size();
Object front() throws QueueEmptyException;
Object dequeue() throws QueueEmptyException;
void enqueue(Object);
}
Analysis of Algorithms
44
An Array-Based Queue
•Create a queue using an array in a circular fashion
•A maximum size N is specified, e.g. N = 1,000.
•The queue consists of an N-element array Q and two integer variables:
-f, index of the front element (initially, f=0)
-r, index of the element after the rear one (initially r=0)
•“normal configuration”
•Questions:
What does f=r mean?
How do we compute the
number of elements in
the queue from f and r?
Analysis of Algorithms
45
An Array-Based Queue (contd.)
Algorithm size():
return (N - f + r) mod N
Algorithm isEmpty():
return size() < 1;
Algorithm dequeue():
if isEmpty() then
throw a QEmptyException
temp  Q[f]
Q[f]  null
f  (f + 1) mod N
return temp
Algorithm front():
if isEmpty() then
Algorithm enqueue(o):
throw a QEmptyException
if size = N - 1 then
return Q[f]
throw a QFullException
Q[r]  o
r  (r+1) mod N
Analysis of Algorithms
46
An Array-Based Queue - Java Code
public class ArrayQueue implements Queue {
private final static int CAPACITY = 100;
private int capacity;
private Object[] Q;
private int f;
private int r;
public ArrayQueue() {
this(CAPACITY);
}
public ArrayQueue(int _capacity) {
capacity = _capacity;
Q = new Object[capacity];
f = r = 0;
}
public int size() {
// your code goes here! (Practical 6)
}
public boolean isEmpty() {
// your code goes here! (Practical 6)
Analysis of Algorithms
}
47
Array-Queue Java code - Con’d
public void enqueue(Object o) throws QueueFullException {
// your code goes here! (Practical 6)
}
public Object front() throws QueueEmptyException {
// your code goes here! (Practical 6)
}
public Object dequeue() throws QueueEmptyException {
// your code goes here! (Practical 6)
}
Analysis of Algorithms
48
Linked lists
Analysis of Algorithms
49
Linked lists
Arrays are one way to implement Stacks, queues, etc.
Linked Lists are another -- extremely flexible and general idea!
Linked list = “Node” objects connected
in a “chain” by links (object references)
Special “entry point” reference
null
Stored values (eg, Strings)
Boxes are “Node” objects
(not ‘built in’ -- you must define/manage them!)
Analysis of Algorithms
50
Node objects
class Node {
Node next;
// the next Node in the list
Object element; // the data
}
Wow - a class defined in terms of itself!
Don’t be scared…..
element
next
“Rome”
Analysis of Algorithms
51
Null means “end of list”
A useful trick
Two special entry points
null
head tail
If we maintain these two special entry points,
insert  
it is easy to delete or insert entries at the “head”
delete  
and insert entries at the “tail”
(but still tricky to delete entries at the “tail” -- why??!)
Analysis of Algorithms
52
Removing at the Head
1.
2.
removed item
Analysis of Algorithms
53
Inserting at the Tail
new item
1.
2.
Analysis of Algorithms
54
The point of all this is…..
Using linked lists to implement Queue
Leave
queue
enter
null queue
The head of the list is the front of the queue, and
the tail of the list is the rear of the queue.
Why not the opposite?
LinkedListQueue is an alternative implementation of Queue to ArrayQueue.
Unlimited
capacity -- no wasted memory, no more QueueFullException 55
Analysis of Algorithms
Linked List implementation of Queue - Java
public class LinkedListQueue implements Queue {
private Node front;
private Node rear;
private int size;
private class Node { // Node is an “inner” class since no one else will ever need it
Object element;
Node next;
Node(Object _element, Node _next) {
element = _element;
next = _next;
}
}
public LinkedListQueue() {
front = rear = null;
size = 0;
}
…
Analysis of Algorithms
56
LinkedListQueue - continued
public int size() {
return size;
}
public boolean isEmpty() {
return size==0;
}
public void enqueue(Object o) {
// your code goes here -- Practical 6!
}
public Object front() throws QueueEmptyException {
// your code goes here -- Practical 6!
}
public Object dequeue() throws QueueEmptyException {
// your code goes here -- Practical 6!
}
}
Analysis of Algorithms
57
Deques
2 detours: more O(.), pointers/references, then…
This week:
- complete P5
- start P6
- read Chapter 5
Next week:
- no lecture Monday - bank holiday!
Analysis of Algorithms
58
Digression 1. More O(·)
• “3n2 + 100n is O(n2)”
“as n gets larger,
eventually n2
becomes larger than
3n2+100n (when
linearly scaled up)
n0 = 100
c=4
 n>n0
cn2>3n2+100
Analysis of Algorithms
means
“eventually”
n0
59
More O(·)
• “f(n) is O(g(n))” means “as n gets larger,
eventually f(n) becomes larger than g(n)
(when linearly scaled up by some amount)
n0 = ?
numbers you need to find in order
to prove that f(n) is O(g(n))
c=?
 n>n0: c·g(n)>f(n)
c·g(n)
f(n)
g(n)
Analysis of Algorithms
n0
n
60
O(·) cheat-sheet
•
The formal (c,no) definition is needed
sometimes, but usually the following
simple rules of thumb suffices:
1. Discard all constants
2. Discard all lower-order terms
•
•
3n2 + 100n  O(n2+n)  O(n2)
(n2 log n)/3 + 100n
 O(n2 log n+n)  O(n2 log n)
Analysis of Algorithms
61
Digression 2. References/pointers
Java objects often refer to other objects:
ppsn
age
name
Fred 328723F
37
class Person {
int age;
String name;
String ppsn;
}
Person f = new Person();
f.age = 37;
f.name = “Fred”;
f.ppsn = “328723F”;
These referred objects aren’t literally “inside” the object, but it’s easy
to visualize the object this way, and it doesn’t cause any confusion.
A pedant might draw the following diagram instead:
age
name
37
Analysis of Algorithms
Fred
ppsn
328723F
arrows mean
“refers to object”
62
References, con’t
• In some cases, these more accurate drawings can
help clear up some confusion
Person people[] = new Person[2];
Person f = new Person();
f.age = 37;
f.name = “Fred”;
f.ppsn = “328723F”;
people[0] = f;
people[1] = f;
people[0].name = “Joe”;
System.out.println(“First person’s is ” + people[1].name);
people[0]
age
name
ppsn
people[1]
Analysis of Algorithms
37
Fred
328723F
63
Reference’s con’t
• Returning to our Linked-List diagrams…
1
this code
generates
this list
Make sure you
understand
Analysis of Algorithms
such
a beast!
2
3
class Node {
Node next;
Object element;
}
Node head = new Node();
// 1
head.element = “Rome”;
head.next = new Node();
// 2
head.next.element = “Seattle”;
head.next.next = new Node(); // 3
head.next.next.element = “Toronto”;
head.next.next.next = null;
64
Deque = Double-Ended Queues
A double-ended queue, or deque, supports insertion and deletion from
the front and back.
The Deque Abstract Data Type
insertFirst(e):
Insert e at the deginning of deque.
insertLast(e):
Insert e at end of deque
removeFirst():
Removes and returns first element
removeLast():
Removes and returns last element
first()
returns first element
last()
returns last element
size()
returns number of elements
isEmpty()
is this deque empty?
Analysis of Algorithms
65
Implementing Stacks & Queues with Deques
Stacks with Deques:
Queues with Deques:
Analysis of Algorithms
66
The Adaptor Pattern
•“Patterns” are recurring typical solutions to software design
problems (see Section 2.6)
•Programming languages don’t provide constructs that support for
patterns (whereas they do provide constructs supporting modularity,
encapsulation, abstraction, …)
•Using a deque to implement a stack or queue is an example of the
adaptor pattern. An adaptor pattern means that you implement a
class by using methods of another class (usually giving them other,
more specialized names)
•In general, adaptor classes specialize more generic classes
•Two such applications:
Specialize a general class by changing some methods.
Ex: implementing a stack with a deque.
Specialize the types of objects used by a general class.
Ex: Defining an IntegerArrayStack class that adapts
Analysis of Algorithms
67
ArrayStack to only store integers.
Implementing Deques with
Doubly Linked Lists
•Deletions at the tail of a singly linked
list cannot be done in constant time
(recall slide 32)
•To implement a deque, we use a
doubly linked list. with special header
and trailer nodes
•A node of a doubly linked list has a next and a prev link. It supports the
following methods:
•setElement(Object e)
class DLNode {
head tail
•setNext(Object newNext)
Object element;
•setPrev(Object newPrev)
DLNode next;
insert  
DLNode
prev;
•getElement()
delete  
}
•getNext()
•getPrev()
•By using
a doubly
linked list, all the methods of a deque run in O(1) time.
Analysis
of Algorithms
68
Implementing Deques with
Doubly Linked Lists (cont.)
When implementing a doubly linked lists, we add two special nodes to
the ends of the lists: the header and trailer nodes.
•The header node goes before the first list element. It has a valid next
link but a null prev link.
•The trailer node goes after the last element. It has a valid prev
reference but a null next reference.
NOTE: the header and trailer
nodes are sentinel or
“dummy” nodes because they
do not store elements. Here’s
a diagram of our doubly
linked list:
Analysis of Algorithms
69
Implementing Deques with
Doubly Linked Lists (cont.)
Here’s a
visualization of
the code for
removeLast().
(see page 169
for more examples)
1.
start
2.
Slide
references
3.
done
Analysis of Algorithms
70
Linked Lists - Summary
Linked lists are an extremely flexible, very general idea.
Lead to efficient (time + space) implemented of queues, stacks
Also, often much simpler (compared to, e.g., Q circular array)
Basic idea -- design a Node class that holds the data element(s)
as well as references to other (previous, next, …) Nodes
as needed.
The trick to successful implementation is to draw lots of
“boxes and arrows” diagrams to make sure you understand
in detail how all the Node references should be manipulated
Analysis of Algorithms
71
Summary
• Abstract data types
• Clearly separating specification (interface) from
implementation (class)
• Three simple ADTs
stack (LI-FO), queue (FI-FO),
deque (LorF-IorO)
• Two implementation strategies for storing lists
arrays (simpler, fixed capacity)
linked lists (tricker, ‘infinite’ capacity)
Analysis of Algorithms
72