Data Structures

Book 1 ch13.5-6
Book 2 Ch10.1, Ch 11.1-5
 References
• Implementation Strategies for Stacks, Queues, and Hash Tables
– Book [1]
Ch 13.5 – 13.6 Representing Stacks and
Queues with Linked Lists
– Book [2]
Ch 10.1 Stacks and Queues
Ch 11.1 – 11.5 Hash Tables
• Implementation Strategies for Graphs and Trees
– Book [2]
Ch 22.1 Representations of Graphs
Ch 12.1 Binary Search Tree

Book 1: Hanly, Jeri, and Koffman, Elliot, "Problem Solving and Program Design in C", 7th ed,
Addison Wesley, New York, 2013
Book 2: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”,
The MIT Press, 3rd edition, 2009
Implementation Strategies for Stacks, Queues, and
Hash Tables
 Stacks
• The element deleted from the set is the one most
recently inserted: the stack implements a last-in,
first-out, or LIFO.
Push : The insert operation on a stack
Pop : The delete operation on a stack

Figure 10.1. An array implementation of a stack S. Stack elements appear only in the lightly
shaded positions. (a) Stack S has 4 elements. The top element is 9. (b) Stack S after the calls
PUSH(S, 17)and PUSH(S, 3). (c) Stack S after the call POP(S) has returned the element 3,
which is the one most recently pushed. Although element 3 still appears in the array, it is no
longer in the stack; the top is element 17.
 Stacks
• When [Link] = 0, the stack contains no elements and is empty. We

can test to see whether the stack is empty by query operation

STACK-EMPTY.

• If we attempt to pop an empty stack, we say the stack underflows,

which is normally an error. If [Link] exceeds n, the stack overflows.

STACK-EMPTY(S) PUSH(S,x) POP(S)
if [Link] == 0 [Link] == [Link] + 1 if STACK-EMPTY(S)
return TRUE S[[Link]] = x error “underflow”
else return FALSE else [Link] = [Link] – 1
return S[[Link] + 1]
 Queues
• The element deleted is always the one that has been in the
set for the longest time: the queue implements a first-in, first-
out, or FIFO.
• Enqueue : Insert operation on a queue
• Dequeue : Delete operation on a queue
• The queue has a head and a tail
• When [Link] = [Link], the queue is empty. Initially, [Link] =
[Link] = 1. If we attempt to dequeue an element from an
empty queue, the queue underflows.
• When [Link] = [Link] + 1, the queue is full, and if attempt to
enqueue an element, then the queue overflows.
 Queues
Figure 10.2. A queue implemented
using an array Q[1..12]. Queue
elements appear only in the lightly
shaded positions.
(a)The queue has 5 elements, in
locations Q[7..11].
(b) The configuration of the queue
after the calls ENQUEUE(Q, 17),
ENQUEUE(Q,3), and ENQUEUE(Q,5).
(c) The configuration of the queue
after the call DEQUEUE(Q) returns
the key value 15 formerly at the
head of the queue. The new head
has key 6.
 Queues
ENQUEUE(Q,x) DEQUEUE(Q,x)
Q[[Link]] = x X = Q[[Link]]
if [Link] == [Link] if [Link] == [Link]
[Link] = 1 [Link] = 1
else [Link] = [Link] + 1 else [Link] = [Link] + 1
return x

The pseudocodes assumes that n = [Link]

 Linked List

• A linked list is a data structure in which the

objects are arranged in a linear order.
• The order is determined by a pointer in each
object.
• A list may have one of several forms. In the
remainder of this section, we assume that the
lists with which we are working are unsorted
and doubly linked.
 Hash Tables

Using a hash function h to

map keys to hash-table slots.
Because keys k2 and k5 map
to the same slot, they collide

• An element with key k is stored in slot h(k). We use a hash

function h to compute the slot from the key k. h(k) is the hash
value of key k.
• Two keys may hash to the same slot  collision.
 Collision resolution by chaining
• In chaining, we place all the elements that hash to the
same slot into the same linked list.

Collision resolution by chaining. Each hash-table slot T[j] contains a linked list of all the keys
whose hash value is j . For example, h.k1/ D h.k4/ and h.k5/ D h.k7/ D h.k2/. The linked list
can be either singly or doubly linked; we show it as doubly linked because deletion is faster
that way.
Analysis of hashing with chaining
• The average-case performance of hashing depends on how
well the hash function h distributes the set of keys to be
stored among the m slots, on the average
• Assume that any given element is equally likely to hash into
any of the m slots, independently of where any other
element has hashed to. This assumtion called simple
uniform hashing

For j = 0, 1, . . . , m – 1, let us donate the length of the list T[j] by

nj , so that n = n0 + n1 = … + nm-1.
and the expected value of nj is E[nj] =  = n/m
Theorem 8.1
In a hash table in which collisions are resolved by chaining, an
unsuccessful search takes average-case time (1+), under the
assumption of simple uniform hashing.

Proof
Under the assumption of simple uniform hashing, any key k not
already stored in the table is equally likely to hash to any of the m
slots. The expected time to search unsuccessfully for a key k is
the expected time to search to the end of list T[h(k)] , which has
expected length E[nh(k)]. Thus, the expected number of elements
examined in an unsuccessful search is , and the total time
required (including the time for computing h(k)) is (1+).
Theorem 8.2
In a hash table in which collisions are resolved by chaining, a
successful search takes average-case time (1+), under the
assumption of simple uniform hashing..

Proof
We assume that the element being searched for is equally likely
to be any of the n elements stored in the table.

Let xi denote the ith element inserted into the table, for i = 1,2,
…,n, and let ki = [Link].
For keys ki and kj, we define the indocator random variable Xij
= I{h(ki) = h(kj)}.
Pr{h(ki) = h(kj)} = 1/m and E[Xij] = 1/m
Thus, the total time required for a successful search (including the
time for computing the hash function) is (2 + /2 - /2n) = (1 + )
Implementation Strategies for Graphs and
Trees
 Representations of Graphs
Undirect graph G with 5 vertices An adjacency-list representation
and 7 edges

1 2

5 4

1 2 3 4 5
1 0 1 0 0 1
2 1 0 1 1 1 The adjacency-matrix representation
of G
3 0 1 0 1 0
4 0 1 1 0 1
5 1 1 0 1 0
 Representations of Graphs
Direct graph G with 6 vertices and 8 An adjacency-list representation
edges

1 2 3

4 5 6

1 2 3 4 5 6
1 0 1 0 1 0 0
2 0 0 0 0 1 0
The adjacency-matrix representation
3 0 0 0 0 1 1 of G
4 0 1 0 0 0 0
5 0 0 0 1 0 0
6 0 0 0 0 0 1
• Adjacency-matrix representation of a graph G = (V, E)
that consist of a |V| x |V| matrix A = (aij)

• Representing attribut depends on:

o Programming language
o Algorithm
o How the rest of the program uses the graph
 Binary Search Tree
Binary-search-tree property: 2
Let x be a node in a binary search tree.
If y is a node in the left subtree of x, 5

then [Link]  [Link]. If y is a node in the

7
right subtree of x, then [Link]  [Link].

5 3
6

5 7 2

Nodes: 6, Height: 4.  less efficient

2 3 8

Nodes: 6, Height: 2
 Binary Search Tree
• The binary-search-tree property allows us to print out all the
keys in a binary search tree in sorted order by a simple
recursive algorithm, called an inorder tree walk.

INORDER-TREE-WALK(x)
If x  NIL
INORDER-TREE-WALK([Link])
print [Link]
INORDER-TREE-WALK([Link])
Theorem
If x is the root of an n-node subtree, then the call INORDER-TREE-
WALK (x) takes (n) time.

Proof
Let T(n) debote the time taken by INORDER-TREE-WALK(x) when
is it called on the root of an n-node subtree.
INORDER-TREE-WALK visits all n nodes of the subtree, so
T(n) = (n)
For n > 0, suppose that INORDER-TREE-WALK is called on a node x
whose left subtree has k nodes and whose right subtree has n-k-1
nodes. Time to perform is bounded by T(n)  T(k) + T(n-k-1) + d
for some constant d > 0.
We use the substitution method to show that T(n) = O(n) by
proving that T(n)  (c+d)n+c. For n = 0, we have (c+d).0+c =
c = T(0). For n > 0,

T(n)  T(k) + T(n-k-1) + d

= ((c + d) k + c) + ((c + d)(n – k - 1)+ c) + d
= (c + d)n + c -(c + d) + c + d
= (c + d)n + c