Chapter 4 Data Structures

Introduction:

Definition: A data structure is a specialized format for

organizing and storing data.

Data representation:
➢ Logical and mathematical description of structure.

➢ Implementation of structure on a computer.

➢ Analysis of structure which includes determining

amount of space in memory and optimization of time
taken for processing.
 Chapter 4 Data Structures
Classification of data structures
 Chapter 4 Data Structures
Primitive data structures:
Operations on primitive data structures
Create:
For example: int x;
Destroy:
Select:
Update:
For example: int x=2;
Again, x=4
 Chapter 4 Data Structures
Non primitive data structures:
Linear data structure:
Non linear data structure:
Operations on linear data structure:
• Traversal
• Insertion
• Deletion
• Searching
• Sorting
• Merging
 Chapter 4 Data Structures
Arrays:

Types of arrays
One-dimensional array
Two-dimensional array
Multi-dimensional array
 Chapter 4 Data Structures
One-dimensional array:
Array can be denoted as,
Data_type array_name[size];
Features:
➢ Array size should be positive number only.
➢ String array always terminates with null
character (‘\0’).
➢ Array elements are counted from 0 to n-1.
➢ Useful for multiple reading of elements.
 Chapter 4 Data Structures
One-dimensional array
Calculating the length of array:
L=UB-LB+1
Example: if an array A has values
10,20,30,40,50,60 stored in
locations 0,1,2,3,4,5 then UB=5
and LB=0.
Size of the array L=5-0+1=6
 Chapter 4 Data Structures
Representation of one-dimensional arrays in memory:
LOC(A[P])=Base(A)+W(P-LB)
Example:
Address content location
1000 A s[0]
1001 B s[1]
1002 C s[2]
1003 D s[3]
1004 E s[4]

Address(s[3])=base(s)+w(p-LB)
= 1000+1(3-0)
=1003
 Chapter 4 Data Structures
Basic operations on one-dimensional arrays:
1.Traversing
2.Searching
3.Sorting
4.Insertion
5.Deletion
6.merging
 Chapter 4 Data Structures
Traversing a linear array
Algorithm:
1.for LOC=LB to UB
PROCESS A[LOC]
end of for
2. exit
 Chapter 4 Data Structures
Searching an element
Search element =3 1≠3 1 A[0]
Linear Search:
Algorithm: 2≠3 2 A[1]

Step 1: LOC=-1 3=3 3 A[2]

Step 2: for P=0 to N-1 4 A[3]
if(A[P]=ELE)
5 A[4]
LOC=P
GOTO step 3
end of if
end of for
Step 3: if(LOC>=0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: exit
 Chapter 4 Data Structures
Binary Search :
Let B and E denote the beginning and end locations of the
array. The middle element A[M] can be obtained by first
finding the middle location M by M=(B+E)/2.

1. If A[M]=ELE, them search is successful. Otherwise new

segment is found as follows:
2. If ELE<A[M], searching is continued at the left-half of
the segment. Reset E=M-1.
3. If ELE>A[M], searching is continued at the right-half of
the segment. Reset B=M+1.
4. If ELE not found then we get a condition B>E. this
results in successful search.
Chapter 4 Data Structures
B=0
E=4
M = 0+4/2=2

3=3 Search Element = 3

if(ele==a[M]
0 1 2 3 4
1 2 3 4 5

3 is at position 2
Chapter 4 Data Structures
B=0
E=4
M = 0+4/2=2

3≠5 Search Element = 5

if(ele>a[M]
B=M+1
0 1 2 3 4
1 2 3 4 5
Chapter 4 Data Structures
Search Element = 5
if(ele>a[M])
B=M+1

4≠5

0 1 2 3 4
1 2 3 4 5
Chapter 4 Data Structures
Search Element = 5
if(ele>a[M])
B=M+1

5=5

0 1 2 3 4
1 2 3 4 5

5 is at position 4
Chapter 4 Data Structures
Search Element = 1
if(ele<a[M])
E=M-1
3≠1

0 1 2 3 4
1 2 3 4 5
Chapter 4 Data Structures
Search Element = 1
if(ele<a[M])
E=M-1
2≠1

0 1 2 3 4
1 2 3 4 5
Chapter 4 Data Structures
Search Element = 1
if(ele<a[M])
E=M-1
1=1

0 1 2 3 4
1 2 3 4 5

1 is at position 0
Algorithm:
Chapter 4 Data Structures
Step 1: set B=LB, E=UB
Step 2: while(B<=E)
M=int(B+E)/2
if(ELE=A[M])
loc=M
goto 3
else
if(ELE<A[M])
E=M-1
else
B=M+1
end of while
Step 3: if(LOC>=0)
PRINT LOC
else
PRINT “Search is unsuccessful”
Step 4: exit
 Chapter 4 Data Structures
Insertion of an element:
 Chapter 4 Data Structures
Insertion of an element:
Chapter 4 Data Structures
Chapter 4 Data Structures
 Chapter 4 Data Structures

70 60 50 10 80 60 70 50 10 80

Correct Key
position

70 60 50 10 80 60 50 70 10 80

60 70 50 10 80 50 60 70 10 80

Key Key
 Chapter 4 Data Structures

50 60 70 10 80 50 10 60 70 80

50 60 10 70 80 10 50 60 70 80

Key

10 50 60 70 80
Chapter 4 Data Structures
 Chapter 4 Data Structures
Two-dimensional arrays

Representation of 2-dimensional array in memory

There are two methods:
➢ Row-major order
➢ Column-major order
 Chapter 4 Data Structures
➢ Row-major order
LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
 Chapter 4 Data Structures
➢ Column-major order
LOC(A[I][J]) = Base(A) + W[(I-LB) + m(J-LB)]
 Chapter 4 Data Structures
Example: Consider the array A of order 25 x 4 with base
value 2000 and one word per memory location. Find the
address of A[12][3] in row-major order and column-major order.
 Chapter 4 Data Structures
Applications of arrays
1. Arrays are used to implement other
data structures such as heaps, hash
tables, queues, stacks and strings etc.

2. Arrays are used to implement

mathematical vectors and matrices.

3. Many databases include one-

dimensional arrays whose elements
are records.
 Chapter 4 Data Structures
Advantages of arrays
1.It is used to represent multiple
data items of same type by using
only single name.

2.It can be used to implement other

data structures like linked lists,
stacks, queues, trees, graphs etc.

3.Two-dimensional arrays are used to

represent matrices.
 Chapter 4 Data Structures
Disadvantages of arrays
1. We must know in advance that how many elements
are to be stored in array.

2. Array is static structure. It means that array is of fixed size.

The memory which is allocated to array cannot be increased
or reduced.

3. Since array is of fixed size, if we allocate more memory than

requirement then the memory space will be wasted. If we
allocate less memory than requirement, then it will create
problem.

4. The elements of array are stored in consecutive

memory locations. So insertions and deletions are very
difficult and time consuming.
 Chapter 4 Data Structures
Stacks:
Introduction:
A stack is an ordered collection of items
where the addition of new items and the
removal of existing items always takes place
at the same end.
This end is commonly referred as the top. The
end opposite to top is known as the base.
Stacks works on the principle of LIFO, Last In
First Out.
 Chapter 4 Data Structures
Stacks:
Examples,
i. plates kept one on another in a
cafeteria.
ii. Books kept one on another.
iii. undo mechanism in text editor
iv. Web browser contains back
button
 Chapter 4 Data Structures
Stacks:
Representation of stacks in memory

➢ Static representation using arrays

➢ Dynamic representation using linked lists
 Chapter 4 Data Structures
Stacks:
Array Representation of a Stack

TOP=MAXSTK ->
STACK IS FULL

TOP=NULL ->
STACK IS EMPTY
 Chapter 4 Data Structures
Stacks:
Linked list representation of a Stack
 Chapter 4 Data Structures
Stacks:
Linked list representation of a Stack
Insertion
 Chapter 4 Data Structures
Stacks:
Linked list representation of a Stack
Deletion
 Chapter 4 Data Structures
Stacks:
Operation On Stack
➢ stack() creates a new stack that is empty. It needs no parameters
and returns an empty stack.
➢ push(item) adds a new item to the top of the stack. It needs the
item and returns nothing.
➢ pop() removes the top item from the stack. It needs no
parameters and returns the item. The stack is modified.
➢ peek() returns the top item from the stack but does not remove it.
It needs no parameters. The stack is not modified.
➢ isEmpty() tests whether the stack is empty. It needs no
parameters and returns a Boolean value.
➢ size() returns the number of items on the stack. It needs no
parameters and returns an integer.
 Chapter 4 Data Structures
Stacks:
Algorithm for PUSH Operation:
 Chapter 4 Data Structures
Stacks:
Algorithm for POP Operation:
 Chapter 4 Data Structures
Applications of Stacks
➢ Stack is used to reverse a word
➢ It is used in “undo” mechanism in text
editors
➢ Conversion of decimal number into binary
➢ To solve Tower of Hanoi
➢ Expression evaluation and syntax parsing
➢ Conversion of infix expression into prefix
and postfix
➢ Quick sort
➢ Run time memory management
 Chapter 4 Data Structures
Arithmetic expression:
Infix expression:
Postfix expression
Prefix expression
 Chapter 4 Data Structures
Infix expression: if an operator is in
between two operands it is called infix
expression

Example 1: a+b, where a and b are

the operands and + is an operator.

Example 2: (a+b)*(c-d)*e
 Chapter 4 Data Structures
Postfix expression: If an operator
follows the two operands it is called
post fix expression.

Example 1: ab +

Example 2: (a+b)*(c-d)*e this infix

expression can be written postfix as,
ab+cd-*e*
 Chapter 4 Data Structures
Prefix expression: If an operator
precedes two operands, it is called
prefix expression.

Example 1: +ab

Example 2: (a+b)*(c-d)*e this infix

expression can be written prefix as,
**+ab-cde
 Chapter 4 Data Structures
Algorithm for infix to postfix
✓ If it is operand, output it.
✓ If it is opening parenthesis, push it on stack.
✓ If it is an operator, then
• If stack is empty, push operator on stack.
• If the top of stack is opening parenthesis, push
operator on stack
• If it has higher priority than the top of stack,
push operator on stack.
• Else pop the operator from the stack and
output it, repeat step 3.
 Chapter 4 Data Structures
Algorithm for infix to postfix
✓ If it is a closing parenthesis, pop
operators from stack and output them
until an opening parenthesis is
encountered. Pop and discard the
opening parenthesis.
✓ If there is no more input, pop the
remaining operators to output.
 Chapter 4 Data Structures
Example: Suppose we want to convert 2*3/(2-1)+5*3 into Postfix form.
Expression Stack Output
2 Empty 2
* * 2
3 * 23
/ / 23*
( /( 23*
2 /( 23*2
- /(- 23*2
1 /(- 23*21
) / 23*21-
+ + 23*21-/
5 + 23*21-/5
* +* 23*21-/5
3 +* 23*21-/53
Empty 23*21-/53*+
 Chapter 4 Data Structures
Queues
Introduction:
a queue is an ordered collection of items where the
addition of new items and the removal of existing items
always take place at different ends.

A queue is an ordered collection of items where an item is

inserted at one end called the REAR and an existing item is
removed at the other end called the FRONT.

Queue works on the principle of FIFO, First In First Out

 Chapter 4 Data Structures
Types of queues
Queue can be of four types:
Simple Queue
Circular Queue
Priority Queue
Dequeue (Double Ended queue)
 Chapter 4 Data Structures
Simple Queue: In Simple
queue insertion occurs at the
rear end of the list, and
deletion occurs at the front
end of the list.
 Chapter 4 Data Structures
Circular Queue: A circular
queue is a queue in which all
nodes are treated as circular
such that the last node follows
the first node.
 Chapter 4 Data Structures
Priority Queue: A priority queue
is a queue that contains items
that have some preset priority. An
element can be inserted or
removed from any position
depending on some priority.
 Chapter 4 Data Structures
Dequeue (Double Ended
queue):
It is a queue in which
insertion and deletion takes
place at both the ends.
 Chapter 4 Data Structures
Operations on queue
Queue() creates a new queue that is empty. It needs
no parameters and returns an empty queue.
enqueue(item) adds a new item to the rear of the
queue. It needs the item and returns nothing. This
operation is generally called as push.
dequeue() removes the front item from the queue. It
needs no parameters and returns the item. The
queue is modified. This operation is generally called
as pop.
isEmpty() tests to see whether the queue is empty.
It needs no parameters and returns a Boolean value.
size() returns the number of items in the queue. It
needs no parameters and returns an integer.
 Chapter 4 Data Structures
Memory representation of a queue using arrays
The condition FRONT = NULL indicates
that the queue is empty and the
condition REAR = N indicates that the
queue is full.
 Chapter 4 Data Structures
Memory representation of a queue using arrays
 Chapter 4 Data Structures
Memory representation of a queue using linked list
Chapter 4 Data Structures
Chapter 4 Data Structures
 Chapter 4 Data Structures
Applications of queues
➢ Simulation
➢ Various features of operating system.
[Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur.]
➢ Multi-programming platform systems
➢ Different type of scheduling algorithm
➢ Round robin technique or Algorithm
➢ Printer server routines
➢ Various applications software is also based on queue data
structure
➢ Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur.
 Chapter 4 Data Structures
LINKED LISTS
Introduction
 Chapter 4 Data Structures
Types of linked lists
1. Singly linked list (SLL)
2. Doubly linked list (DLL)
3. Circular linked list (CLL)

1. Singly linked list (SLL)

 Chapter 4 Data Structures
2. Doubly linked list (DLL)

BACK: It is a pointer field containing the address

of the previous node.
FORW: It is a pointer field that contains the
address of the next node.
INFO: It contains the actual data.
 Chapter 4 Data Structures
3. Circular linked list (CLL)
T
 Chapter 4 Data Structures
Operations on linked lists
1. Creating a linked list
2. Traversing a linked list
3. Inserting an item into a linked list
4. Deleting an item from the linked
list
5. Searching an item in the linked list
6. Merging two or more linked lists
 Chapter 4 Data Structures
Creating a linked list
 Chapter 4 Data Structures
Non-linear data structure
Introduction
Pros
➢Uses memory efficiently as contiguous
memory is not required for allocating data
items.
➢The length of the data items is not
necessary to be known prior to allocation.
Cons
➢Overhead of the link to the next data item.
 Chapter 4 Data Structures
TREES
A tree is a data structure consisting of nodes organized as a hierarchy
 Chapter 4 Data Structures
Terminology
Node: is a structure which may contain a value, a condition, or
represent a separate data structure.
Parent node: A node that has a child is called the parent node (or
ancestor node, or superior).
Leaf Node: Nodes that do not have any children are called leaf nodes
(Terminal node).
height of a node: the length of the longest downward path to a leaf
from that node.
depth of a node: The length of the path to its root.
Root Node: The topmost node in a tree is called the root node.
An internal node or inner node: any node of a tree that has child
nodes and is thus not a leaf node.
subtree: a tree consisting of a node and all of its descendants in tree.
 Chapter 4 Data Structures
Binary trees: A binary tree is a tree in which each node has
at most two descendants - a node can have just one but it
can’t have more than two.
 Chapter 4 Data Structures
Complete Tree: Tree in which each leaf is at the same distance from
the root. i.e. all the nodes have maximum two subtrees.
GRAPHS
A graph is a set of vertices and edges which connect them. A graph is
a collection of nodes called vertices, and the connections between
them, called edges.
The following diagram shows a graph with 5 vertices and 7 edges.
The edges between A and D and B and C are pairs that make a
bidirectional connection, represented here by a double-headed
arrow.
 Chapter 4 Data Structures
THANK YOU!