9 Data Structure

Data structure is representation of the logical relationship existing between

individual elements of data. In other words, a data structure is a way of organising
all dataitems thatconsiders not only the elements stored but also their relationship
to each other.
CHAPTER Data structure mainly specifies (or dictates) the following four things
Capsule (i) Organisation of data i) Accessing methods
Daa structure plays the role (ii) Degree of associativity (iv) Processing alternatives for information
key bone of the section of Data structure affects the design of both structural and functional aspects of
Computer awareness for programme.
ery exam. Question are Algorithm + Data structure = Programme

Med from this chapter on

aTay. stack, queue, linked Classification of Data Structure
Stree, graph etc.
Data structures ave normally divided into two broad categories
) Primitive data structure i) Non- primitive data structure
Data structure

Primitive data structure Non-primitive data structure

IntegerLFloat Character Pointer Arrays Lists Files

Linear Lists Non-linear Lists

Stacks Graphs
Queues Trees
Classification of data structure
70 Computer Awarenes
4. The number of elements that can bé stored venby
:
Primitive Data Structure arrayi.e., the size of array
or its length is o
These are basic structures and are directly operated the following equation
(upperbound 1owerbound) +1
upon by the machine instructions. Integer, floating point
numbers, character constants, string constants, pointers For the above array, it would be
etc fall in this category. 1 10
(9 0)
Where, 0 is the lower bound of array and 9ie
Non-Primitive Data Structure is the
upper bound of array
These are more sophisticated data structures. These are 5. Arrays can always be read or written thro
derived from the primitive data structure. The If read a one-dimensional ara
loop. we
non-primitive data structures emphasise on structuring loop for reading and other
requires one
of a gToup of homogeneous (same type)or the array, e-g,
writing (printing)
heterogeneous (different type) data items. Arrays, lists (a) For reading an array
and files are examples.
for (i-0:i<=9;j++)
The most commonly used operation on data structure are scanf ("%d". & a[i]);
broadly categorised into four types (b) For writing an array
1. Create 2. Destroy or Delete for (i-0: i<=9; i++)
3. Selection 4. Updation (printf ( "%d", a[i]):}
Other operations performed on data structure include If we are reading or writing two-dimensional aray i
would require two loops and similarly the array of
.Searching .Sorting Merging8 dimension would require n loops.
Some common operations performed on arrays are
Arrays 1. Creation of an array
An array is defined as a set of finite number of
homogeneous elements or data items. It means an' array
2. Traversing'an array (accessing array elements
3. Insertion of new elements
can contain one type of data only, either all
integers, all 4. Deletion of required element
floating point numbers, or all characters. Declaration of
arrays is as follows 5. Modification of an element
int a[10]J: Merging of arrays
Where, int specifies the data type or type of elements
array stores. a is the name of array, and the number Stacks
specified inside the square brackets is the number of
elements, an array can store, this is also called size or A stack is also an ordered collection of elements lie
length of array. arrays but it has a special feature that deletion ant
insertion of elements can be done only from one end
Following are some of the concepts to be remembered about
arrays called the top of stack, called TOP. Due to this propert,
it is calledas Last In First Out type of data structure 14,
1. The individual element of an array can be
accessed by specifying name of the array, (LIFO).
followed by index or subscript inside square Push Pop
brackets. eg, to access fifth element of array a,
we have to give the following statement,
a[4]:
2. The first element of the array has index zero(0). It
mean the first element and last element will be Stack
specified as, It could be thought of just like a stack of plates placed o
af0. and a[9]. respectively table in a party, a guest always takes off a frest
3. The elements of array will always be stored in from the top and the new plates are placed on
consecutive memory locations. stack at the top.
t Structure 71.

hen an
ment is inserted into a stack or
e l e m e n t

removed Priority Queue

stack, its ase remains fixed whereas the
base
the
of top have a priority
m
ck c h a n g e s . Often the items added to a queue
determines the order
sertion of element into stack is called push and associated with them. This priority
items are
lement from stack is called in which they exit the queue-highest priority
of
pop. The
place on a stack. figure
etion
o wh
s ow the operations take removed first.
oks can be implemented in two ways
sacks

Using arTay (static implementation) Linked Lists

al Using pointers (dynamic implementation) A list (linear linked list) can be defined as a collection
of
list must
variable, number of data items. An element of
yeues contain atleast two field, one for storing data o r
information and other for storing address of next
etes are First In First (Out type of data structure (i.e., be
element. Hence the second field of the list must
O). In a queue, new elements are added to the queuue referred to
end called REAR end and the elements are pointer type. Technically, each such element collectioon
as a node, therefore a list can be defined as a
way'sremovedi
from otherend called the FRONT end.
of nodes as shown in figure below
e people standing a railway reservation row are an
ample of queue. Each new person comes and stands at
Head
end of row (rear end of queue) and persons gettingg
reservations confirmed, get out of the row from the Arun Amit HGeeta Mitu
ntend.
Information field-
ques can also be implemented in two ways Pointer field-
Linear linked list
) Using array i) Using pointers

Operations on Linked List

45 56 78 89 9 12|1
Rear
The basic operations to be performed on the linked lists are as
Front follows
Queue with 7 elements
1. Creation 2. Insertion
3. Deletion 4. Traversing
ous types ofqueues are given below
5. Searching 6. Concatenation
icular Queue 7. Display
a r queue is one in which the insertion ofa
new

ent is done at the very first location of the queue, if Types of Linked List
last location of the queue is full. Basically, uwe can put linked lists into the followving four ype
Q[O] Q[1] 1. Singly linked list is one in which all nodes are
linked together in sbme sequential manner.
Hence, it is also called linear linked list.
Q 4] Clearly, it has the beginning and the end. The
problem with this list is that we cannot acces the
Q [3] predecessor of node from the current node. This
Circular queue can be overcome in
doubly linked lists.
ouble Ended Queue Start
also a elements in which
ior andnomogeneous list of performed from
Rerton -10 -20
Olh the e deletion operationsdouble-ended queue.
are

Singly linked list

30
Hence, it is called
ommonl referred to as dequeue.
 72 Computer Awareneess

2. Doubly linked list is one in which all nodes are Level

linked together by multiple links which help in The level is a node is defined by initially letting the.
accessing both the successor node (next node) be at level 1. If the nodes is at level 1, then its child0
and predecessor node (previous node) for any ren a
level 1+1.
arbitrary node within the list.
To count number of nodes in a particular level =qli-
Start where, i is number of levels.

X10 F20 F30X Height or Depth

Doubly linked list The height or depth of a tree is defined as the maxim
3. Circular linked list is one which has no level of any node'in the tree.

beginning and no end. A singly linked list can be

made a circular linked list by simply storing the Binary Tree
address of the very first node in the link field of It is a finite set of elements that is either empty r
the last node. A circular linked list is shown in
partioned into three disjoint subset. The first suh
figure. called root, the other two subsets are called left and ihe

Start subtrees.
node 1 node 2 node 3 node 4 Strictly Binary Tree
10 20 0 40 G
Ifevery non-leaf node in a binary tree has non-emt
Circular linked list left and right subtrees, the tree is termed as stricti
binary tree.
4. Circular doubly linked list is one which has Total number of nodes in a strictly binary tree =(2n-1
both the successor pointer and perdecessor
pointer in circular manner. It is shown in figure. where, n is number of leafs.

Complete Binary Tree

Start
dwhose all leaves ar
It is a strictly binary tree of depth
10 F|0 F|0 at level d. Total number of nodes in a complete binar
tree = (2n-1)
Circular doubly linked list
where, n is number of leafs.

Trees Binary Search Tree (BST)

A non-linear data structure is called a tree. It is basically It is a binary tree in which all identifiers in the let
These are subtree of tree are less than the identifier in the roc
an arrangement of data in a sorted manner.
hierarchical form. A tree is a finite set of node and all identifiers in the right subtree of tree ar
also called as
one or more nodes such thát there is a specially greater than the identifiers in the root.
designated node called the root and remaining nodes A BST can be traversed (displayed) in three ways
are further divided into disjoint sets in which
each set is
called subtrees of the root. Pre-order Traversal
In this root is traversed first and then left subtreea"
Basic Terminology of Trees then right subtree.
Node So, CLR or Centre, Left, Right
It stands for the item of information plus the branches to In-order Traversal
other itemns.
In this, left first then root (centre) and then rightsubtrsd
Degree So, LCR or Left, Centre, Right
The number of subtrees of a node is called its degree.
Post-order Traversal
Leaf or Terminal Nodes In this, left first then right and then root (centre) suibtree
Nodes that have degree is called leaf or terminal
So, LRC or Left, Right, Centre
zero

nodes.
n a t aS t r u c t u r e
ure

Graph Traversal the

nodes of
visiting all the
of
G r a p h

means
traversal in many
non-linear data structure. A
mathematica A graph be needed
traversal may m e t h o d s for
a
is
is of vertices Vand a set of edges E.
set graph. Graph there may be many
G(V E) a pair of vertices and
Gaph
a
areas and
gaph
A ne d g e c o n n e c t s .
may have weight application
vertices of the graph.
gth, cost or another measuring instrument for visiting the
traversal methods
th graph. Vertices
on the
graph are shown as There are two graph
breadth first
traversal
ecording
are drawn line In
or
circles and edges as arcs or
B r e a d t h First
Traversal
a s the
start position.
point
Thus, an edge can be representing as node is selected unvisited nodes
ment. of a graph, one
then all
where, V and W are pair of vertices. The and marked, in
7, W) It is visited
node a r e visited
and marked
a n d W lie on E. Vertices may be considered as adjacent to the
next
the unvisited
nodes
arcs, ine segment as roads. order. Finally,
vertces

and
and edges, s o m e sequential a r e visited
to these nodes
idesa

are classified in thefollowing categories, immediately adjacent until the entire graph has
Thegraphs marked and s o forth, known a s Breadth
First
Directed Graph (ii) Non-directed Graph been traversed. It is also

i Connected Graph (iv) Non-connected Graph Search. traversal of

first
(vi) Multi-Graph Traversal Breadth
v) Simple Graph First first
Depth. level-by-level. Depth
the graph proceeds from the starting node
a path
of Graph traversal follows first from the start
Basic Terminology includes the following to a n ending node, then another path
have been
until all nodes
Raric terminology ofthe graph to the end and
s o forth

known a s Depth First

Search.
visited. It is also
Edge two vertices or edge is a pair
It is a line which is joining
of verticees
Sorting and Searching
from
speedily and efficiently
Edges are
of thwo types Retrieval of informationoperations in a file processing.
1. Directed edge It has direction specified. have files is o n e of the
core

and merging a r e
three related
which does not sorting
2. Undirected edge Any edge Searching,
make the job of
retrieval of data from
any direction specified. operations which and efficient.
the storage devices, easier, speedier
Vertices
two nodes joined by an edge are
called vertices.
Sorting of an Array of arranging the
Any of array is the technique
an
Sorting either in
Null Graph null array
elements in a specified order i.e.,
node is called
as
order.
which has no edge or
ascending or descending
Any graph
graph. Bubble Sorting
element is compared with
its
Digraph then it is
called as In bubble sort, each
first element is larger than the
the edges are
directed
adjacent element. If the
gTaph, all second one, then the position
of the elements are
diagraph. interchanged, otherwise it is
not changed. Then, next
element and the
Mixed Graph element is compared with its adjacent
some are
undirected,
same process is repeated
for all the elements in the array.
directed and
S o m e edges are
The s a m e process is repeated until
no m o r e elements are
then called mixed graph. left for comparison. Finally, the array is sorted
one.

Multigraph parallel
then it is
called as
Selection Sorting
fina agraph two edges are
The selection sort technique is based upon the extension
multigraph. of the minimum/maximum technique. By of a
nest of for loops, a pass through the array is made to
means

Loop at the
same
vertex is
locate the minimum value.
Any edge which starts
and ends

called loop.
Caller
 74
Computer Awarenec
Once this found, it is placed in the first position of the largest key in the heap. This type of heap is uho
array (position 0). Another, the remaining elements is called descending heap or max heap, as the path fr
made to find the next smallest
element, which is placed the root node to a terminal node forms an ordered li
st of
in the second
position (position 1) and so on elements arranged in descending order.
Insertion Sort The follorwing fgure shows an example of max-ten
An insertion sort is 'one that sorts representation heap
a set of values by
inserting values into an existing sorted file. Suppose an
array a with n elements all, al2,. an is in memory.
The insertion sort algorithm scans a from all to aln,
inserting each element a[k| into its proper position in the
previously sorted sub array al, al2 ak-1
Quick Sort 50)
2 38 (48)
The quick sort algorithm works by partitioning the array
to be sorted and each partition is in turn sorted 65 43 54 26 3848 50
recursively. In partition, one of the array elements is Max-heap
chosen as a key value. This key value can be the first
element of an array. i.e., if a is an array then
key =a0 Searching of Array Element
and rest of the array elements are grouped into two
Searching is used to find the location where, element is
partitions. available or not.
Figure shows a key and partitions of element in an array
There are two types ofsearching techniques as given beloo
1. Linear sequential searching
2. Binary searching
Partition 1 Partition 2
Linear or Sequential Searching
In linear search, we access each element of an
array one
Value> key key Value > key by one sequentially and see whether it is desired element
or not. A search will be unsuccessful, if all the elements
One partition contains elements smaller than the key are accessed and the desired element is not found.
value.
Another partition contains elements larger than the Binary Searching
key value. Binary searching is an extremely efficient algorithm.
This search technique searches the given item in
Radix Sort
minimum possible comparisons. To do the
Bucket sort or radix sort is a method can be used to sort
binary
search, first we had to sort the array elements.
a list of names alphabetically, here the base or radix is Searched in 1st half Searched in 2nd
26, (the 26 letters of the alphabetic). of array Mid value half of array
Merge Sort
First value First +Last)/2 Last value
Merge sort is a sorting technique which divides the array
into sub-arrays of size 2 and merge adjacent pairs. We Binary search sketch diagram for middle value
then have approximately n/2
arrays of size 2. This The
process is repeated until there is only one array logic behind this technique is given below
remaining of size n. 1. First find the middle element of the array.
Heap Sort 2. Compare the mid element with an item.
A heap is defined as an almost 3. There are three cases which arises
complete binary tree of n
nodes such that the value of each node is less than or (a Ifit is a desired element then search is successtul.
equal to the value of the father. This implies that the root (b) If it is less than desired item then search ony
of the binary tree (i.e., the first
array element) has the the first half of the array, by
using the same step
 75
ngta
Structure
ure

oreater than the desired is the run of the following

element search in the The space needed by a programme

(c) nd half of the array, by

s e c o n a

using the same step. component the code,

includes space for
the sanme eps until an element is found or (a A fixed part that and fixed, size
variable
peat
search area. In this space for simple
in the
hauIst educing the
algorithm every time
search area. So, number of space for
contents etc.
component variables,
of the space
a r e

keep on decreasing. that consists

omparison
(b) A variable part variable whose
size is
neededby component problem
instance

performance Analysis and dependent o n the particular

stack used by
solved and the space
being
Measurement recursive procedures.
evaluation of an algorithm is obtained
erformance
Thepert
totaling the number of occurrences of each operation Time Complexity of
algorithm. is the amount
running the of a programme
when The time complexity
needs to r u n to completion.
computer time of the
Space Complexity p is the sum

The time T(p) taken by programme

a
of a programme is the amount of time.
The space complexity to completion. compile time and the r u n
nemory it needed to
run

LET US Practice
data structure is linear data
6. Which of the following
c a n easily be converted into a 2-tree
1. A binary tree structure?
subtree a new internal node
by (b) Graphs
(a) by replacing each empty (a) Trees
None of these
an internal nodes for non-empty node (d)
(b) by inserting node
(c) Arrays
external nodes for non-empty to evaluate a postfix
(c) by inserting an subtree by a new external 7. The data structure required
(d) by replacing each empty expression is
(d) linked list
node
(a) queue
(b) stack (c) array
of
determining the efficiency of a n algorithm is
2. The time factor when of the average case

algorithm is measured by
8. The complexity than that of worst
much more complicated to analyse
(a)
(a) counting microseconds case
that of worst c a s e
(b) counting the number of key
operations
(b) much more simpler to analyse than
and s o m e other times
of statements more complicated
(C) cOunting the number (c) sometimes

(a) counting the kilobytes of algorithm simpler than that of worst case
condition
3. Which of the following is
not the required (d) None of the above
limitation of binary
for binary search algorithmn? 9. Which of the following is not
a

must be sorted search algorithm?

a)The list access to the middle
the direct (a) Must use a sorted array
(0) There should be data
element in only sublist (b) Binary search algorithm is not efficient when the
mechanism to delete and/or insert elements are more than 1000
(CThere must be
(c) Requirement of sorted array is expensive when a lot of
elements in list
insertion and deletions are needed
(d) None of the above
to every
other node
(d) There must be a mechanism to access middle
node G is adjacent
U in element directly
every
V in G, a graph is said to be
(b) complete 10. Each array declaration need not give, implicitly or
(a) isolated (d) strongly connected explicitly the information about
(c) finite of divide (a) the name of array
algorithm is
sorting (b) the data type of array
following
c h of the (c) the first data from the set to be sorted
and conquer type? (b) Insertion sort
(d) the index set of the array
(a) Bubble sort these
(d) All of
(c) Quick sort
76 Computer Awarenes

11. Which of the

following data structure store the 20. Which of the following data structure is
is not
not linear
homogeneous data elements? data structure?
(a) Arrays (b) Records (a) Arrays (b) Linked lists
(c) Structures (d) None of these (c) Both (a) and (b) (d) None of these
12. When converting binary tree into extended
tree, all the original nodes in binary tree are
binary 21. The in-order traversal of tree will yield a eld a sorted
listing of elements of tree in
(a) internal nodes on extended tree (a) binary trees (b) binary search trees
(6) external nodes on extended tree (c) heaps (d) None of these
(c) vanished on extended tree
(d) None of the above 22. The space factor when determining the
efficiene of
algorithm is measured by
13. The operation of processing each element in the list
(a)counting the maximum memory needed by
is known as
algorithm
he
(a) updating (6) merging (c) inserting (d) traversal (b) counting the minimum memory needed by h
he
14. Which of the algorithm
following data structures are indexed (c) counting the average memory needed by h
structures?
algorithm
he
(a) Linear arrays (b) Linked lists (d) counting the maximum disk space needed by th
(c) AVL tree (d) Binary trees e
algorithm
15. When new data are to be inserted into a data 23. Two-dimensional arrays are also called
structure, but there is no available space; this (a) matrix arrays (b) table arrays
situation is usually called (c) Both (a) and (b) (d) None of these
(a) underfiow (b) overflow
(c) Both (a) and (6) (d) None of these. 24. Which of the following case does not exist in

16. The term

complexity theory?
'push' and pop' is related to the (a) Best case (b) Worst case
(a) array (b) lists (c) Average best (d) Null case
(c) stacks (d) All of these
25. A variable L is called pointer, if
17. Which of the following is two way list?
(a) L contains the address of an element in data
(a) Header header list (b) Circular header list (b) Lpnints to the address of first element in data
) Grounded (d) None of these (c) L stores addréss of address of data
18. The elements of an array are stored (d) None of the above
successively in
memory cells because 26. A data
(a) by this way computer can keep track only the address
structure, where elements can be added or
removed at either end but not in the middle
of the first element and the
addresses of other (a) linked lists (b) stacks
elements can be calculated
(c) queues (d) dequeues
(6) the architecture of computer memory does not allow
arrays to store other than seriaky 27. Two main measures for the
(c) Both (a) and (b)
efficiency of an
algorithm are
(d) None of the above (a) processor and memory
19. In a max-heap tree (b) complexity and capacity
(c) time and space
(a)values innode is greater than every valuein
a
left (d) data and space
subtree and smaller than right subtree
(6) values in a node is greater than every value in children 28. An algorithm that calls itself
of it directly or indirectly
known as
(c) Both of above conditions applies (a) sub algorithm
(d) None of above conditions applies (b) recursion
(c) polish notation (d) traversal algorithm

Answers
1. (d) . (b). 3. (c)
11 (a)
4. (6) 5. (c) 6 (c) 7. (b) 8.(a) 9. (a) 10. (C
12. (a) 13. (d) 14. (a) 15. (b) 16. (c) 17. (d) 18. (a) 19. (6) 20 ()
21. (b) 22. (a) 23. (c) 24. (d) 25. (a) 26. (d) 27. (c) 28. (b)