DATA STRUCTURES

Why are we studying Data Structures ?

Modern world all about … DATA
 Dealing with data…
• How to use it ?
• How to store it ?
• How to process it ?
• How to gain “knowledge” from it ?
• How to keep it secret?
 Dealing with data…
• How to use it ?
• How to store it ?
• How to process it ?
• How to gain “knowledge” from it ?
• How to keep it secret?
How should data be stored?
Depends on your requirement
 Data is diverse ..
But we have some building blocks
 Definition

• Data structure is representation of the logical

relationship existing between individual
elements of data.
• In other words, a data structure is a way of
organizing all data items that considers not
only the elements stored but also their
relationship to each other.
 Introduction

• Data structure affects the design of both

structural & functional aspects of a program.
Program=Algorithm + Data Structure
• You know that a algorithm is a step by step
procedure to solve a particular function.
 Introduction

• That means, algorithm is a set of instruction

written to carry out certain tasks & the data
structure is the way of organizing the data
with their logical relationship retained.
• To develop a program of an algorithm, we
should select an appropriate data structure
for that algorithm.
• Therefore algorithm and its associated data
structures form a program.
 Classification of Data Structure
• Data structure are normally divided into
two broad categories:
– Primitive Data Structure
– Non-Primitive Data Structure
 Classification of Data Structure

Data structure

Primitive DS Non-Primitive DS

Integer Float Character Pointer

 Classification of Data Structure

Non-Primitive DS

Linear List Non-Linear List

Array Queue Graph Trees

Link List Stack

 Primitive Data Structure
• There are basic structures and directly
operated upon by the machine
instructions.
• In general, there are different
representation on different computers.
• Integer, Floating-point number, Character
constants, string constants, pointers etc,
fall in this category.
 Non-Primitive Data Structure
• There are more sophisticated data
structures.
• These are derived from the primitive data
structures.
• The non-primitive data structures
emphasize on structuring of a group of
homogeneous (same type) or
heterogeneous (different type) data items.
 Non-Primitive Data Structure
• Lists, Stack, Queue, Tree, Graph are
example of non-primitive data structures.
• The design of an efficient data structure
must take operations to be performed on
the data structure.
Non-Primitive Data Structure

• The most commonly used operation on data

structure are broadly categorized into
following types:
– Create
– Selection
– Updating
– Searching
– Sorting
– Merging
– Destroy or Delete
 Difference between them
• A primitive data structure is generally a
basic structure that is usually built into the
language, such as an integer, a float.
• A non-primitive data structure is built out
of primitive data structures linked
together in meaningful ways, such as a
linked-list, binary search tree, AVL Tree,
graph etc.
 Elementary Data “Structures”
• Arrays head

• Lists
• Stacks 2
1

• Queues 3 4
7 8
• Trees 5 6

F R

19
 Examples

• Basic Types
– integer, real (floating point), boolean (0,1),
character
• Arrays
– A[0..99] : integer array
0 1 2 3 4 5 6 7 99
A 2 1 3 3 2 9 9 6
… 10

– A[0..99] : array of images

…

0 1 2 99
20
 Abstract Data Type

A mathematical definition of objects, with

operations defined on them

21
 ADT: Array

A mapping from an index set, such as

{0,1,2,…,n}, into a cell type
Objects: set of cells
Operations:
• create(A,n)
• put(A,v,i) or A[i] = v
• value(A,i)

22
 Description of various
Data Structures : Arrays
• An array is defined as a set of finite
number of homogeneous elements or
same data items.
• It means an array can contain one type of
data only, either all integer, all float-point
number or all character.
 Arrays

• Simply, declaration of array is as follows:

int arr[10]
• Where int specifies the data type or type of
elements arrays stores.
• “arr” is the name of array & the number
specified inside the square brackets is the
number of elements an array can store, this is
also called size or length of array.
 Arrays
• Following are some of the concepts to be
remembered about arrays:
– The individual element of an array can
be accessed by specifying name of the
array, following by index or subscript
inside square brackets.
– The first element of the array has index
one[1]. It means the first element and
last element will be specified as:arr[1]
& arr[10]
Respectively.
Stacks
 Stack
A list for which Insert and Delete are allowed
only at one end of the list (the top)
– LIFO – Last in, First out

Pop Pop
Push
 What is this good for ?
• Page-visited history in a Web browser
 What is this good for ?
• Page-visited history in a Web browser
• Undo sequence in a text editor
 What is this good for ?
• Page-visited history in a Web browser
• Undo sequence in a text editor
• Saving local variables when one function
calls another, and this one calls another
 How should we represent it ?
• Write code in python ?
 How should we represent it ?
• Write code in python ?
• Write code in C ?
 How should we represent it ?
• Write code in python ?
• Write code in C ?
• Write code in Java ?

Aren’t we essentially doing the same

thing?
 Stack ADT
Objects:
A finite sequence of nodes
Operations:
• Create
• Push: Insert element at top
• Top: Return top element
• Pop: Remove and return top element
• IsEmpty: test for emptyness
 Exceptions
• Attempting the execution of an operation of ADT
may sometimes cause an error condition, called
an exception
• Exceptions are said to be “thrown” by an
operation that cannot be executed
• In the Stack ADT, operations pop and top cannot
be performed if the stack is empty
• Attempting the execution of pop or top on an
empty stack throws an EmptyStackException

35
 Exercise: Stacks
• Describe the output of the following series of stack
operations
– Push(8)
– Push(3)
– Pop()
– Push(2)
– Push(5)
– Pop()
– Pop()
– Push(9)
– Push(1)

36
 C++ Run-time Stack
main() {
• The C++ run-time system keeps int i;
track of the chain of active i = 5; bar
functions with a stack foo(i); PC = 1
• When a function is called, the } m=6
run-time system pushes on the foo(int j)
stack a frame containing { foo
– Local variables and return value int k; PC = 3
k = j+1; j=5
– Program counter, keeping track of bar(k); k=6
the statement being executed }
• When a function returns, its bar(int m) main
frame is popped from the stack { PC = 2
and control is passed to the …
i=5
method on top of the stack }

37
 Parentheses Matching
• Each “(”, “{”, or “[” must be paired with a
matching “)”, “}”, or “[”
– correct: ( )(( )){([( )])}
– correct: ((( )(( )){([( )])}
– incorrect: )(( )){([( )])}
– incorrect: ({[ ])}
– incorrect: (

Stacks 38
 Parentheses Matching Algorithm
Algorithm ParenMatch(X,n):
Input: An array X of n tokens, each of which is either a grouping symbol, a
variable, an arithmetic operator, or a number
Output: true if and only if all the grouping symbols in X match
Let S be an empty stack
for i=1 to n do
if X[i] is an opening grouping symbol then
S.push(X[i])
else if X[i] is a closing grouping symbol then
if S.isEmpty() then
return false {nothing to match with}
if S.pop() does not match the type of X[i] then
return false {wrong type}
if S.isEmpty() then
return true {every symbol matched}
else
return false {some symbols were never matched}

Stacks 39
 Array-based Stack
Algorithm size()
• A simple way of return t + 1
implementing the
Stack ADT uses an Algorithm pop()
array if empty() then
throw EmptyStackException
• We add elements else
from left to right t = t - 1
• A variable keeps track return S[t + 1]
of the index of the
top element

…
S
0 1 2 t
 Array-based Stack (cont.)
• The array storing the
stack elements may
become full Algorithm push(o)
if t = S.length - 1 then
• A push operation will throw FullStackException
then throw a else
FullStackException t = t + 1
– Limitation of the S[t] = o
array-based
implementation
– An array which is
formed will be
homogeneous
…
S
0 1 2 t
41
 Performance and Limitations
- array-based implementation of stack ADT

• Performance
– Let n be the number of elements in the stack
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the stack must be defined a
priori , and cannot be changed
– Trying to push a new element into a full stack causes
an implementation-specific exception

42
 Singly Linked List
• A singly linked list is a
data structure next
consisting of a
sequence of nodes
• Each node stores
– element elem node
– link to the next node

A B C D
43
 Stack with a Singly Linked List
• We can implement a stack with a singly linked list
• The top element is stored at the first node of the list
• The space used is O(n) and each operation of the
Stack ADT takes O(1) time
nodes

top t Æ

elements
10/9/23 1:22 PM
Vectors 48
A Queue
 Queues

50
 Array-based Queue
• Use an array of size N in a circular fashion
• Two variables keep track of the front and rear
– f index of the front element
– r index immediately past the rear element
• Array location r is kept empty

normal configuration
Q
0 1 2 f r

wrapped-around configuration
Q
0 1 2 r f
52
 Queue Operations
• We use the modulo Algorithm size()
return (N + r – f) mod N
operator
(remainder of Algorithm isEmpty()
return (f = r)
division)

Q
0 1 2 f r

Q
0 1 2 r f

53
 Queue Operations (cont.)
• Operation enqueue throws an Algorithm enqueue(o)
exception if the array is full if size() = N - 1 then
throw FullQueueException
• This exception is
else
implementation-dependent
Q[r] = o
r = (r + 1) mod N

Q
0 1 2 f r

Q
0 1 2 r f

54
 Queue Operations (cont.)
• Operation dequeue Algorithm dequeue()
throws an exception if isEmpty() then
if the queue is throw EmptyQueueException
empty else
o = Q[f]
• This exception is f = (f + 1) mod N
specified in the return o
queue ADT

Q
0 1 2 f r

Q
0 1 2 r f
55
 Performance and Limitations
- array-based implementation of queue ADT

• Performance
– Let n be the number of elements in the queue
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the queue must be defined a
priori , and cannot be changed
– Trying to enqueue an element into a full queue causes
an implementation-specific exception
 Queue with a Singly Linked List
• We can implement a queue with a singly linked list
– The front element is stored at the head of the list
– The rear element is stored at the tail of the list
• The space used is O(n) and each operation of the Queue ADT takes O(1)
time
• NOTE: we do not have the limitation of the array based implementation
on the size of the stack b/c the size of the linked list is not fixed, I.e., the
queue is NEVER full.
r

nodes
rear
front
f Æ

elements
57