II PUC-COMPUTER SCIENCE (41) NOTES

CH4:DATA STRUCTURES(1+1+3+3+5+5=18M)
Data structure: a data structure is a specialized format for organizing and storing the data.
Data structure can classified into two types: Primitive and Non-primitive data structure.
Primitive Data Structure:
Data structure which is directly operated upon by machine level instruction is called
primitive data structure
Ex: int, char, float, double, pointer, etc.
Non-Primitive Data Structure:
Data structure that are derived from primitive data structure are known as non-primitive
data structure.
Non-Primitive data structure classified into two types
1.Linear data structure 2) Non-Linear data structure
1.Linear data structure: data structure in which data elements are stored in linear order
are called linear data structure.
Ex: Array, Stack, Queue, Linked List,
2.Non-Linear data structure: data structure in which data elements are stored in non-
linear order are called non-linear data structure.
Ex: Trees, Graphs.
Operations on Primitive data structure:
1.Create: it is used to create a new data structure. This operation reserves memory space for
variable.
Ex: int a;
2.Destroy: It is used to destroy or remove the data structure from the memory space.
Ex: Destructor is used for destroy the objects.
3.Select: It is used to access the data within data structure.
4.Update: update operation is used to change data of the data structure
Ex: int a=10; a=20; // value of variable is updated as 20.
Operations on linear data structure (or)
Basic operations on one-dimensional arrays.
1.Traversal:It is the process of accessing each data item exactly once to perform some operation.
2.Insertion:It is the process of adding a new data item into the array.
3.Deletion:It is the process of removing an existing data item from the array.
4.Searching:It is the process of finding the location of data item in the array.
5.Sorting:It is is the process of arrangement of data items in ascending or descending order.
6.Merging:It is the process of combining one or more arrays to form a single array.
Arrays: an array is a collection of homogeneous elements with unique name
Types of Arrays: There are three types of arrays
1.One-dimensional array
2.Two-dimensional array
3.Multi-dimensional array.
1.One-dimensional array(1-D array):
An array with only one row or column is called one-dimensional array (or)
An array with only one subscript is called one-dimensional array.

Declaration Syntax: datatype arrayname[size]; Ex: int a[5];

Arrayname-is user defined variable name,
size- is number elements in the array. It should be integer value.

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 1
 II PUC-COMPUTER SCIENCE (41) NOTES

Features(Rules) of Subscript(Index value)

1.Array size should be positive number only.
2.String array always terminates with null character(‘\0’)
3.Arrya must be integer value
4.Array elements are counted from 0 to N-1
Calculating the length of array: array length can be calculated by using the following formula
Length(L)=UB-LB+1 where UB-Upper Bound LB-Lower Bound
Ex: If array A has values 11,12,13,14,15 stored in locations 0,1,2,3,4
Then UB=4, and LB=0 Size of the array L=4-0+1=5
Representation of 1-dimensional array in memory
An array with only one row or column is called 1-d array.
It is finite collection of n number of elements of same type such that
*Elements are stored in continuous locations
*Elements can be referred by indexing or subscript
200 202 204 206 208
10 20 30
a[0] a[1] a[2] a[3] a[4]
2.Two-dimensional array(2-D array):
An array with one row and column is called two-dimensional array (or)
An array with two subscripts is known as two-dimensional array.
Declaration Syntax: datatype arrayname[row][col]; Ex: int a[3][3];
Representation of 2-dimensional array in memory
There are two methods to represent two-dimensional array:
Row major order(RMO) and Column major order(CMO)

10 20 A[0] Ex: int a[2][2]; MxN=2x2=4 A[0][0]=10, A[1][0]=30

30 40 A[1] A[0][1]=20 A[1][10=40

RMO/CMO
Applications of Arrays:
1.It is used in matrix manipulation
2.Arrays can be used in storing elements
3.It is used in CPU scheduling.
4.It is used in the representation of polynomials.
Advantages of Arrays:
1.Array is capable of storing many elements at a time.
2.Data access is faster: we can easily access each element of the array effectively.
3.Simple: arrays are simple to understand and use.
4.Arrays can be used to represent other data structures such as stacks, queues, linked list, tress,
graphs, etc.
Dis-advantages of Arrays:
1.Insertion and deletion are very difficult and time consuming.
2.There is a chance of memory wastage or shortage(waste of space)
3.It is a static structure, it means that array is fixed size.
(we can not change size of array at the run time)-memory allocate can not be increased or
decreased
Searching: the process of finding the position of an element in an array is called searching.
Searching techniques are: Linear searching and Binary searching

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 2
 II PUC-COMPUTER SCIENCE (41) NOTES

Differences between Linear Search and Binary Search

Linear Search Binary Search
Advantages: Advantages:
1.It is a simple search technique 1.It is an efficient technique.
2.It allows both sorted and unsorted 2.It allows only sorted elements
elements. 3.It consumes less time for searching
3.It consumes more time elements.

Sorting: the process of arranging the data elements in an order either ascending or descending is
called sorting.

The different types of sorting methods are: insertion sort, bubble sort, quick sort, heap sort,
selection sort, shell sort, bucket sort, etc..

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 3
 II PUC-COMPUTER SCIENCE (41) NOTES

Q#1:Traversing a linear array Algorithm Q#2:Insert element into array Algorithm

Step1: for I=0 to N-1 do Step1: for i=N-1 down to POS
PRINT A[I] [Apply Process] a[i+1]=a[i]
[End of for loop] (End of for loop)
Exit/Stop (or) Step2: a[POS]= ELE //ELE or ITEM
For LOC= LB to UB Step3: N=N+1
Process A[LOC] Step4: Exit
[End of for loop]
Exit/Stop
Q#3: Delete from an array Algorithm: Q#4: Insertion Sort Algorithm:
Step1: ELE=a[POS] Step1:for I=1 to N-1 do
Step2: for i=POS to N-1 Step2: for J=I down to 1(one)
A[i]=a[i+1] Step3: if(a[J]<a[J-1])
(End of for loop) temp=a[J]
Step3: N=N-1 a[J]=a[J-1]
Step4:Exit a[J-1]=temp
(End if)
(End of step2 for loop)
(End of step1 for loop)
Step4: Exit/Stop

Q#5:Binary Search Algorithm: Q#6:Linear Search Algorithm:

Step1:LOC=-1, BEG=0, END=N-1 Step1: LOC=-1
Step2: While(BEG<=END) Step2: for POS=0 to N-1
MID= Int(BEG+END)/2 If(a[POS]=ELE)
If(ELE==a[MID]) LOC=POS
Goto Step 3 Go to Step 3
Else (End of if)
If(ELE<a[MID]) (End of for)
ENF= MID-1 Step3: if(LOC>=0)
Else PRINT “Location”
BEG=MID+1 Else
(End of while) PRINT “Search is not found”
Step3: if(LOC>=0) Step4:Exit
PRINT “Location”
Else
PRINT “Search is not found”
Step4: Exit
ALGORITHM: PUSH OPERATION: ALGORITHM: POP OPERATION:
Step1: if(TOP=N-1) then Step1: if(TOP=-1(null)) then
PRINT “Stack is full/Overflow” PRINT “Stack is empty/Underflow”
Exit Exit
(End of if) (End of if)
Step2:TOP=TOP+1 Step2: ITEM=STACK[TOP] //ITEM/ELE
Step3:STACK[TOP]=ITEM //ITEM/ELE Step3: TOP=TOP-1
Step4: STOP/RETURN Step4: STOP/RETURN

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 4
 II PUC-COMPUTER SCIENCE (41) NOTES

QINSERT(ENQUEUE) OPERATIONS OF STACK(FUNCTIONS):

ALGORITHM: QINSERT(QUEUE, ELE, N) 1.Stack( ): Creates a new empty stack
STEP1: INPUT ELE 2.PUSH(item):adds a new item to the top of the stack
STEP2: if(REAR=N-1) then [Check for Overflow] 3.POP( ):removes the top item from the stack
PRINT “Queue is full” 4.Peek( ):To get the top most element of the stack
Exit 5.Size( ): To get number of elements present into the
STEP3:if(FRONT=-1) then [Check whether Q is empty] stack
FRONT=0 6.isEmpty( ):Check whether stack is empty or not
REAR=0 7.isFull( ):Check whether stack is full or not
Else LIFO/FILO ORDER LIST
REAR=REAR+1 [Increment REAR Pointer] LAST IN FIRST OUT
STEP4: QUEUE[REAR]=ITEM [Copy ele to rear position] FIRST IN LAST OUT
STEP5: RETURN/STOP
QDELETE(DEQUEUE) OPERATIONS OF QUEUE:
ALGORITHM: QDELETE(QUEUE, ELE, N) 1.Queue( ): Creates a new empty queue
STEP1: if(REAR=-1) then [Check Whether Q is empty] 2.Enqueue(item):adds an item to the queue
PRINT “Queue is Empty” 3.Dequeue( ):removes an item from the queue
Exit 4.Peek( ):To get the element at the front of the queue.
STEP2: ITEM=Q[FRONT] Without removing it
STEP3:if(FRONT=REAR) then [If Q has only one element] 5.Size( ): To get number of elements present into the
FRONT=NULL(FRONT=-1) queue
REAR=NULL(REAR=-1) 6.isEmpty( ):Check whether queue is empty or not
Else 7.isFull( ):Check whether queue is full or not
FRONT=FRONT+1 [Increment FRONT Pointer] FIFO ORDER LIST( FIRST IN FIRST OUT)
STEP4: RETURN/STOP
APPLICATIONS OF STACKS APPLICATIONS OF QUEUES
Stacks are used in Queues are used in
1.Back tracking 1.Simulation
2.Reverse a string(word) 2.Printer server routines
3.Quick Sort 3.Multitasking systems
4.Conversion of Infix to Postfix/Prefix 4.Process management
5.Conversion of Decimal number to binary number 5.Round-robin method/technique or algorithm
6.Parsing 6.Network communication system
7.Polish notation 7.Keyboard buffer
8.DFS 8.Different types of scheduling algorithms
9.Balanced parenthesis 9.In shared resource management
10.Run time memory management 10.Various features of operating system
11.Undo and Redo operations

QINSERT(ENQUEUE)-Method 2 APPLICATIONS OF LINKED LIST

ALGORITHM: QINSERT(QUEUE, ELE, N) Linked List are used in
STEP1: INPUT ELE 1.Implementation of stacks and queues
STEP2: if(REAR=N-1) then [Check for Overflow] 2.Implementation of graphs
PRINT “Queue is full” 3.Dynamic memory allocation
Exit 4.Doubly linked list is use etc, for tree representation
[End of if] 5.Sum of two long integers
REAR=REAR+1 [Increment REAR Pointer] 6.Maintaining directory of names
STEP3: QUEUE[REAR]=ELE [Copy ele to rear position]
STEP4:RETURN/STOP

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 5
 II PUC-COMPUTER SCIENCE (41) NOTES

Differences between Stack and Queue:

Stack Queue
A Stack is an ordered collection of items A Queue is an ordered collection of items
where the addition of new items and the where the addition of new items and the
removal of existing items always take place removal of existing items always take place
at the same end.(TOP) at the different end(FRONT and REAR)
Stack is also known as LIFO list Queue is also known as FIFO list
(LAST IN FIRST OUT order) (FIRST IN FIRST OUT order)
Linked List
Types of Linked List: Operations of Linked Lists:
1.Singly Linked List(SLL) 1).Creating a linked list
2.Doubly Linked List(DLL) 2).Traversing a linked list
3.Circular Linked List(CLL) 3).Inserting an element into a linked list
4).Deleting an element(item) from the
linked list
5).Searching an item in the linked list
6).Merging two or more linked list

STACK: 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 ordering principle is sometimes called LIFO/FILO
Last In First Out or First In Last Out
QUEUE: Queue is an order collection of item, where an item is inserted at one end called
“rear”
And item can be removed at the other end called “front”
Insertion and deletion is performed according to the FIRST IN FIRST OUT(FIFO) order.
Queue is also called as FIFO list,

Queue is an abstract data structure(linear data structure) somewhat similar to stacks,

One end is always used to insert data(enqueue) and the other end is used to remove
data(dequeue)
Types of Queues:
There are four different types of queues.
1).Simple Queue
2).Circular Queue
3).Priority Queue
4).Double Ended Queue (Dequeue)
1).Simple Queue: In a simple queue, Insertion operation takes place at the REAR end and
Deletion operation takes place at the FRONT end.
It strictly follows the FIFO rule

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 6
 II PUC-COMPUTER SCIENCE (41) NOTES

2).Circular Queue: In this, Last node (element) of the queue is connected to first
node(element) of the queue and forms the circular organization of memory locations(also
called as Ring buffer)
[In a circular queue, Last node is connected to the first node]
The main advantages of a circular queue over a simple queue is better memory utilization.

3).Priority Queue: a priority queue is a special type of queue in which each element is
associated with a priority and is served according to its priority.

4).Double Ended Queue(Dequeue): in a dequeue, insertion and deletion operations can

be done(takes place) at both end (FRONT and REAR of the queue.)

Representation of Stacks in Memory:

(Implementation of Stack)
There are two ways/types of stack representation
1).Stack representation using arrays (using arrays)
2).Stack representation using linked list (using linked list)
1).Stack representation using arrays (using arrays):
*Stack can be represented using a one-dimensional array.
*A pointer TOP contains the location of the top element of the stack. A variable N contains
*the maximum number of elements that can be stored in the stack.
*The condition TOP=N-1 indicates that the stack is full.
*TOP=-1(NULL) indicates that the stack is empty
Fig:
10 20 30 40 50
S[0] S[1] S[2] S[3] S[4] TOP=4

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 7
 II PUC-COMPUTER SCIENCE (41) NOTES

Representation of Queues in Memory:

(Implementation of Queue)
There are two ways/types of queue representation
1).Queue representation using arrays (using arrays)
2).Queue representation using linked list (using linked list)

1).Queue representation using arrays (using arrays):

*Queue can be represented using a one-dimensional array.
*Let Queue linear queue. The pointer FRONT contains the location of the element to be
removed and the pointer REAR contains location of the last element inserted.
*The condition FRONT=-1(NULL) indicates that the queue is empty. and
*The condition REAR=N-1 indicates that the queue is full.

10 20 30 40
Q[0] Q[1] Q[2] Q[3] Q[4]

FRONT=0 REAR=3

LINKED LIST: It is a linear data structure contains one or more nodes, a node is a memory
chunk has two parts-INFO field and LINK field
Types of Linked List:
1).Singly Linked List(SLL)
2).Doubly Linked List(DLL)
3).Circular Linked List(CLL)
Explanation:
1).Singly Linked List(SLL):Item navigation is forward only
2).Doubly Linked List(DLL): Items can be navigated forward and backward.
3).Circular Linked List(CLL): Last item contains link of the first element as next and the
first element has a link to the last element as previous..
Non-Linear data structure: data structure in which data elements are stored in non-linear
order are called non-linear data structure.
Ex: Trees, Graphs.
Tree: a tree is an acyclic connected graph.
Terminologies of a tree:
1.Node: a node is a functional part of a tree, each element of a tree is called a node of a tree
2.Root: the top node in a tree(starting node)
3.Height: number of levels in a tree is called height of a tree.
4.Degree: the number of sub trees of a tree is called a degree of a tree
5.Depth: The depth of a node is the length of the path to its root.
6.Edge: A connection between two different nodes
7.Subtree: A part of the tree is called sub tree
8.Binary tree: It is a type of tree, in which each parent may have zero, one or two children.
9.Complete tree: A tree in which all the leaf nodes are exist with same distance from the
root node.
9.Leaf node(Terminal node):a node with no children are called leaf node.

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 8
 II PUC-COMPUTER SCIENCE (41) NOTES

10.Internal node: A node has one or more children is called an internal node
11.Parent node: It is an immediate predecessor of a node
( a node from which child is derived)
12.Child node: A successor of a parent node is called the child node
Graph: A graph is a set of vertices and edges which connect them.
G=(V,E) Where V is the set of vertices E is the set of edges.
Types of Graphs: a graph may be directed and undirected
Directed graph: Shows direction in every edge.
Undirected graph: Does not shows direction on its edges.
Lists: lists are linear collections of data items.

Prof.H.Ramesh,MCA., Sr. Faculty in Computer Science, Dept. of CS, Cell:94488 45623(WA) Page 9