Algorithms & data structures

Basic data structures

Damjan Strnad
 2

Data structure
●
a data structure is a way of storing and organizing a
dataset in a computer in order to facilitate its access
and modification
●
operations on data structures include searching,
inserting and deleting data
●
operation efficiency depends on the type of data
structure (sequential, hierarchical, …)
●
individual data structure element can contain a data
field, called a key, and associated satellite data, such
as pointers to other elements
 3

Operations on data structures

●
operations on data structures are of two types:
– query operations, which return information about the data
structure
– modifying operations, which change the data structure
●
typical operations are:
– SEARCH(S,k) returns a pointer to element x with key value k in
data structure S (i.e., key[x]=k) or NIL if there is no such
element in S
– INSERT(S,x) inserts element x into data structure S
– DELETE(S,x) removes element x from data structure S
– MINIMUM(S) and MAXIMUM(S) return a pointer to element x with
the smallest resp. largest key value in data structure S
– SUCCESSOR(S,x) and PREDECESSOR(S,x) return a pointer to
element with next larger resp. smaller key value than that of
element x in data structure S or NIL if there is no such element
 4

Array
●
a one-dimensional array is a sequence of n keys of the
same data type, which are stored in consecutive memory
locations and accessible through their index

key[0] key[1] key[2] ... key[n-1]

●
each array element is accessible in constant time, i.e., in
O(1)
●
arrays can be used for implementation of other data
structures and strings
 5

Stack
●
is a data structure that uses strategy LIFO (last-in, first-
out) in which we can directly access only the last
inserted element (real examples are stack of plates or
towels)
●
for inserting an element onto a stack we use operation
push; for removing the last inserted element from a
stack we use operation pop*
PUSH POP
 6

Stack
●
is a data structure that uses strategy LIFO (last-in, first-
out) in which we can directly access only the last
inserted element (real examples are stack of plates or
towels)
●
for inserting an element onto a stack we use operation
push; for removing the last inserted element from a
stack we use operation pop

12
11 11 11
9 9 9 9 9
8 8 8 8 8 8
1 1 1 1 1 1

PUSH(11) PUSH(12) POP() POP() POP()

 7

Stack
●
stack is used for hardware implementation STACK-EMPTY(S)
of interrupts, method calls, recursion and if top = 0 then
temporary data storage (e.g., undo/redo) return TRUE
else
●
we will use array S for implementation of return FALSE
stack; the array length determines
maximum number MAX of elements PUSH(S,x)
that can be pushed onto the stack if top = MAX then
return overflow
●
top is the index of the next free location else
on the stack; S[0] is the bottom stack S[top] ← x
element and S[top-1] is the top stack top ← top + 1
element
●
stack is empty if top=0 POP(S)
if STACK-EMPTY(S) then
●
top is incremented by PUSH and return error
decremented by POP else
top ← top - 1
●
each operation has time complexity return S[top]
O(1)
 8

Stack
0 1 2 3 4 5
●
example: S 12 7 2
– stack currently contains
three elements 12, 7 and 2 top=3
(top=3)
0 1 2 3 4 5
– after executing PUSH(S,9) S 12 7 2 9 6
and PUSH(S,6) we get
top=5
top=5
– executing POP(S) returns
0 1 2 3 4 5
element 6, which remains
S 12 7 2 9 6
in the array but will be
overwritten by next PUSH
top=4
 9

Queue
●
is a data structure that uses strategy FIFO (first-in, first-
out) in which we can directly access only the element
that has been in the queue for the longest time (a real
example is checkout line)
●
for inserting an element into the queue we use operation
enqueue; for removing an element from the queue we
use operation dequeue
●
a queue is used, for instance, as a buffer for data
streaming
●
we will use array Q to implement a queue; an array of
length MAX can store MAX–1 queue elements
●
head is the index of first queue element and tail is the
index of first free array cell into which we will write next
element
 10

Circular queue
●
a circular queue reuses previously occupied and
released locations in a linear array ⇒ after location
Q[MAX-1] fills, we write the next element to location Q[0]
(if it has been released in the meantime)
●
queue is empty if head=tail (initial state is head=tail=0)
QUEUE-EMPTY(Q)
if head = tail then
return TRUE
else
return FALSE
 11

Circular queue
●
when inserting elements we write to location Q[tail] and
circularly increase tail; time complexity is O(1)
ENQUEUE(Q,x)
if (head=tail+1) or (head=0) and (tail=MAX-1) then
return overflow % queue is full
else
Q[tail] ← x % insert element
if tail = MAX - 1 then
tail ← 0 % circularly increase tail
else
tail ← tail + 1
 12

Circular queue
●
when removing elements we read from location Q[head]
and circularly increase head; time complexity is O(1)
DEQUEUE(Q)
if QUEUE-EMPTY(Q) then
return error % queue is empty
else
x ← Q[head] % read element
if head = MAX - 1 then
head ← 0 % circularly increase head
else
head ← head + 1
return x
 13

Circular queue
●
example:
– the queue currently contains elements 3, 1, 12, 9 and 7,
head=4 and tail=9

head
0 1 2 3 4 5 6 7 8 9
Q 3 1 12 9 7 3

1
head=4 tail=9 tail 7
9 12
 14

Circular queue
●
example:
– the queue currently contains elements 3, 1, 12, 9 and 7,
head=4 and tail=9
– if we execute operations ENQUEUE(Q,4) and
ENQUEUE(Q,8), tail circularly increases to 1

tail
head
0 1 2 3 4 5 6 7 8 9 8
Q 8 3 1 12 9 7 4 3
4
1
tail=1 head=4 7
9 12
 15

Circular queue
●
example:
– the queue currently contains elements 3, 1, 12, 9 and 7,
head=4 and tail=9
– if we execute operations ENQUEUE(Q,4) and
ENQUEUE(Q,8), tail circularly increases to 1
– after we execute DEQUEUE(Q), head increments to 5
tail

0 1 2 3 4 5 6 7 8 9 8
Q 8 3 1 12 9 7 4 3
4 head
1
tail=1 head=5 7
9 12
 16

Linked list
●
a linked list is a linear dynamic data structure in which
consecutive elements are connected through pointers
●
each element contains a key (data field) and pointers
prev and next to previous and next element in the list
– if some element has no predecessor (successor) the
corresponding pointer is NIL
●
head is the pointer to first and tail is the pointer to last
element of the list
– list is empty if head=NIL

– the list contains a single element if head=tail

 17

Linked list
●
types of linked list:
key next
– singly linked list (each
element only has pointer 8 17 15 NIL
next) head tail

prev key next

– doubly linked list (each
element has both NIL 8 17 52 NIL
pointers next and prev)
head tail

– circular linked list (the first

8 17 15
and last element are
head tail
connected)
 18

Linked list
●
advantages:
●
the length of linked list is not limited except by the
amount of available memory
●
elements can be inserted anywhere
●
disadvantages:
●
access to elements is sequential
●
poor use of cache
●
extra space consumption for pointers
 19

Singly linked list – search

● procedure LIST-SEARCH(L,k) finds first element with
key k in list L
– if no such element is in the list, the procedure returns
NIL
●
time complexity of searching is O(n)
LIST-SEARCH(L,k)
x ← head
while x ≠ NIL and key[x] ≠ k do
x ← next[x]
return x
 20

Singly linked list – insertion

● procedure LIST-INSERT(L,x) inserts element x in the
head of list L*
● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L
●
the insertion itself is O(1), but locating the insertion point
requires O(n)

LIST-INSERT(L,x)
next[x] ← head
if tail = NIL then
tail ← x
head ← x
 21

Singly linked list – insertion

● procedure LIST-INSERT(L,x) inserts element x in the
head of list L*
● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)

8 NIL 8
x head=x

17 next[head] 17 next[head]
head head
 22

Singly linked list – insertion

● procedure LIST-INSERT(L,x) inserts element x in the
head of list L
● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L*
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)

LIST-INSERT-AFTER(L,y,x)
next[x] ← next[y]
next[y] ← x
if tail = y then
tail ← x
 23

Singly linked list – insertion

● procedure LIST-INSERT(L,x) inserts element x in the
head of list L
● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L*
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)

8 NIL
x

20 next[y] 17 next[next[y]]
y next[y]
 24

Singly linked list – insertion

● procedure LIST-INSERT(L,x) inserts element x in the
head of list L
● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L*
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)

8 next[y]
x

20 x 17 next[next[y]]
y next[y]
 25

Singly linked list – deletion

●
when removing an element from singly linked list we
need a pointer to its predecessor, if one exists
● procedure LIST-DELETE(L) removes the first element
of list L*

LIST-DELETE(L)
x ← head
head ← next[head]
if tail = x then
tail ← NIL
destroy x
 26

Singly linked list – deletion

●
when removing an element from singly linked list we
need a pointer to its predecessor, if one exists
● procedure LIST-DELETE(L) removes the first element
of list L*

20 next[head] 17 next[next[head]]
head next[head]

20 next[head] 17 next[head]
head head
 27

Singly linked list – deletion

● procedure LIST-DELETE-AFTER(L,x) removes the
element that comes after element x in list L*
●
time complexity of deletion is O(1), but when removing a
successor of some element we need to find it first which
requires O(n)
LIST-DELETE-AFTER(L,y)
x ← next[y]
next[y] ← next[next[y]]
if tail = x then
tail ← y
destroy x
 28

Singly linked list – deletion

● procedure LIST-DELETE-AFTER(L,x) removes the
element that comes after element x in list L*
●
time complexity of deletion is O(1), but when removing a
successor of some element we need to find it first which
requires O(n)

20 next[y] 17 next[next[y]] 8 next[next[next[y]]]

y next[y] next[next[y]]

20 next[y] 17 next[next[y]] 8 next[next[next[y]]]

y next[y] next[next[y]]
 29

Doubly linked list – insertion

●
procedure for searching is identical to the one for a singly
linked list
● procedure LIST-INSERT(L,x) inserts element x in the
head of list L*

LIST-INSERT(L,x)
next[x] ← head
if head ≠ NIL then
prev[head] ← x
head ← x
prev[x] ← NIL
if tail = NIL then
tail ← x
 30

Doubly linked list – insertion

●
procedure for searching is identical to the one for a singly
linked list
● procedure LIST-INSERT(L,x) inserts element x in the
head of list L*

NIL 8 NIL NIL 8 y

x head=x

NIL 17 next[head] x 17 next[y]

head=y y
 31

Doubly linked list – insertion

● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L*
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)
LIST-INSERT-AFTER(L,y,x)
next[x] ← next[y]
next[y] ← x
prev[x] ← y
if tail = y then
tail ← x
else
prev[next[x]] ← x
 32

Doubly linked list – insertion

● procedure LIST-INSERT-AFTER(L,y,x) inserts
element x after element y in list L*
●
time complexity of insertion is O(1), but when inserting
after some element we need to find it first which requires
O(n)
NIL 8 NIL
x

prev[y] 20 next[y] y 17 next[next[y]]

y next[y]

y 8 next[y]
x

prev[y] 20 x x 17 next[next[y]]
y next[y]
 33

Doubly linked list – deletion

● procedure LIST-DELETE(L,x) removes element x from L*
– because every element has a pointer to its predecessor and
successor, we do not need a separate LIST-DELETE-AFTER
●
time complexity of deletion is O(1), but when removing a
successor of some element we need to find it first which
requires O(n)
LIST-DELETE(L,x)
if prev[x] ≠ NIL then
next[prev[x]] ← next[x]
else
head ← next[x]
if next[x] ≠ NIL then
prev[next[x]] ← prev[x]
else
tail ← prev[x]
destroy x
 34

Doubly linked list – deletion

● procedure LIST-DELETE(L,x) removes element x from L*
– because every element has a pointer to its predecessor and
successor, we do not need a separate LIST-DELETE-AFTER
●
time complexity of deletion is O(1), but when removing a
successor of some element we need to find it first which
requires O(n)

prev[prev[x]] 20 x prev[x] 17 next[x] x 8 next[next[x]]

prev[x] x next[x]

prev[prev[x]] 20 next[x] prev[x] 17 next[x] prev[x] 8 next[next[x]]

prev[x] x next[x]
 35

Abstract and concrete data struct.

●
array and linked list are examples of low-level data
structures, which determine the organization and access
to data in memory (sequentially, with pointers) ⇒ we can
say they are concrete, physical or implementation-
oriented data structures
●
stack and queue are examples of higher-level data
structures, which determine the behavior of operations on
data and are implemented using low-level data structures
⇒ we can say they are abstract, logical or behavior-
oriented data structures
●
how would you implement operations on stack and queue
using a doubly linked list instead of an array?
 36

Abstract and concrete data struct.

QUEUE-EMPTY(Q)
if head[Q] = NIL then
STACK-EMPTY(S)
return TRUE
if head[S] = NIL then
else
return TRUE
return FALSE
else
return FALSE ENQUEUE(Q,x)
if QUEUE-EMPTY(Q) then
PUSH(S,x) LIST-INSERT(Q,x)
LIST-INSERT(S,x) else
LIST-INSERT-AFTER(Q,tail[Q],x)
POP(S)
if STACK-EMPTY(S) then DEQUEUE(Q)
return error if QUEUE-EMPTY(Q) then
else return error
x ← head[S] else
LIST-DELETE(S,head[S]) x ← head[Q]
return x LIST-DELETE(Q,head[Q])
return x
note: procedure LIST-DELETE is adapted, such that the removed element is not destroyed