DATA STRUCTURE:

The logical or mathematical model of a particular organization of data is Called data

structure
Data Structure Operations
The data in data structures are processed by certain operations like
1)Traversing: For processing certain item in record, each record is accessed exactly once.
(Visiting a record)
2)Searching: Finding location of a record with given key value or finding the locations of all
records, which satisfy one or more conditions
3) Inserting: Adding a new record to the structure
4)Deleting: Removing a record from a structure.
5)Sorting: Arranging the records in some order
6)Merging: Combining the records in two different sorted files into a single sorted file
ALGORITHMIC NOTATIONS:
An algorithm is a finite step-by-step list of well-defined instructions for solving a particular
problem. The form for formal representation of an algorithm consists of two parts,
1) It tells the purpose of algorithm, identification variables, which occur in algorithm and
lists, input data.
2) It contains list of steps that is to be executed. There are certain conventions, which has to
be followed in algorithms.
i) Step, control, exit
The steps of algorithm are executed one after another beginning with step1. Sometimes
control may be transferred to step 'n' of algorithm by statement. goto step n' or using
control structures. The algorithm is completed with the statement 'Exit'
ii) Comments
It is given in brackets either at beginning or end of step. It indicates the main purpose of
step.
iii) Variables
Variable names are generally given in capital letters. Also variables used as counters or
subscripts are in capitals.
e.g. MAX:=5
1) Input/Output
 For inpot read statement is med Read: Variable name
For output write/print statement is used Write Messages/Variable names
Control Structures
Generally three types of logic are used in algorithms that are as follows,
1) Sequence Logic 2) Selection Logic 3) Iteration Logic
1) Sequence Logic
Generally modules are executed in some sequence.
The sequence is represented by means of numbered steps.
Generally flow pattern is as follows,
2) Selection Logic:
This logic employs a number of conditions. Accordingly which condition is satisfied that
module is executed. Generally the following statement gives end of such a structure.
These structures are of Three types:
I) Single Alternative
If condition holds true then module A is executed, otherwise module A is skipped and
control transfer to the next step of algrorithm
Ii) Double Alternative
If condition is true module A is executed and
if condition is false module B is executed.

3)Iteration Logic:
Generally these types of structures are called loops. In that two types of loops are there,
1) Repeat for, 2) Repeat while
i) Repeat… for
Repeat for K = R to S by T
Where K= Index variable
R= Initial value of K
S= Final value of K
T=Step (increment/decrement)
*The loop is executed for all values of K starting from R to S with step of T.
ii)Repeat… while

ARRAYS
A linear array is a list of finite number n of homogeneous data elements. The elements of
array are referenced by index set consisting of n consecutive numbers. The elements of
array are stored respectively in successive memory locations.
The number n of elements is called length or size of the array
Length = UB - LB +1
Where UB= largest index i.e. upper bound LB = smallest index i.e. lower bound
Suppose DATA be a 6 element array such that, DATA [1]=247, DATA [2]= 56, DATA [3]= 429
DATA [4]=135, DATA [5]= 87, DATA [6]= 156
247 56 429 135 87 156

Representation of arrays in memory

Let LA be a linear array in the memory of computer.
The elements of LA are stored in successive memory cells.
Then the address of each element is given by the following notation
LOC [LA [K]] = address of the element LA [K] of the array LA.
Base address of array = Base [LA] Using base address the computer calculate the address of
any element of LA
By following formula
LOC [LA [K]]= Base (LA]+ W [K- Lower bound], where W = no of words per memory cell finds
the array LA
e.g. Consider the array AUTO that records the number of automobiles sold each year from
1998 through 2000.
Base (AUTO)=200
W = 4 words per memory cell
LOC (AUTO [1998]] = 200
LOC (AUTO [1999]] = 204
Then address of array element for K = 2000 is.
LOC [AUTO [2000]] = Base [AUTO] + W (2000- lower bound]
=200+4 (2000-1998] = 208
Traversing Linear Arrays
Let A be a collection of data elements stored in the memory of the computer Suppose we
want to print the contents of each element of A or suppose we want to count the number
of elements of A with a given property This is accomplished by traversing A that is by
accessing and processing each
Element of A exactly once The following algorithm traverses a linear array LA
Algorithm for traversing a linear array
Here LA= linear array LB = lower bound of array UB= upper bound of array Process
operation to each element of LA
Step 1: [Initialize [counter]] Set K = LB
Step 2: Repeat steps 3 and 4 while K<=UB
Step 3: apply process to LA[K]
Step 4: set K:= K+1
Step 5: Exit
Inserting Element in array
It means adding another element to the collection A. [Linear array] Inserting an element at
the end of a linear array can be easily done provided the memory space allocated for the
array is large enough to accommodate additional element. But if we want to insert an
element in the middle of the array, then half of the array (average) must be removed
downward to new locations to accommodate the new element and keep the order of other
elements:
Algorithm for inserting element into a linear array
INSERT (LA N, K. ITEM ] LA =Linear array N=Total no. of elements in the array
K= Any positive integer, K<=N
This algorithm inserts an element ITEM into the K position in LA.
Step 1: [Initialize Counter] Set J = N
Step 2: Repeat steps 3 and 4 while J 2 K
Step 3: [Move J element downward] Set LA [J+1) = LA [J]
Step 4: (Decrease Counter] Set J = J-1
Step 5: [Insert element] Set LA [K]=ITEM
Step 6: Set N = N+1
Step 7: Exit
Deleting Element in array
It refers to the operation of removing one of the elements from A. Deleting at an end of
array is simple but deleting an element somewhere in the middle of the array would require
that each subsequent element be moved one location upward in order to fill up the array
Algorithm for deleting an element
This algorithm deletes the K element from a linear array LA and assigns it to A variable ITEM
DELETE [LA, N, K, ITEM] LA= Linear array N = Total no. of elements in array
K = Any positive integer such that K<= N
Step1 :Set ITEM=LA [K]
Step 2: Repeat for J=K to N-1
Step 3: Set LA [J]:= LA [J+1]
Step 4: Set N:= N-1
Step 5: Exit

2.4 BUBBLE SORTING

Sorting means, rearranging the elements in increasing or decreasing order Suppose A[1],
A[2]…..A[n] are in memory. Then bubble sort algorithm works as Follows:
Compare A [1] and A [2] and arrange them in the desired order, so that A [1]. A[2]. Then
compare A [2] and A [3] and arrange them so that A [2], A [3] Continue this process until we
compare A [N-1] with A [N] so that A [N-1] , A [N].
Bubble Sorting Algorithm
(Bubble Sort) BUBBLE [DATA, N]
Here DATA is an array with N elements. This algorithm sorts the elements in DATA
Step 1: Repeat steps 2 and 3 for K = 1 to N-1
Step 2 : Set PTR = 1
Step 3: Repeat while PTR<= N-K
a) IF DATA [PTR]> DATA [PTR + 1], then:
Interchange DATA (PTR) and DATA [PTR + 1]
b) Set PTR PTR +1
Step 4: Exit
Searching
Searching refers to the operation of finding the local on of given element in the list. The
most commonly used searching algems are linear search and binary Search.
In linear search the given element is compared with each element of list one by one. This
method is also called sequential search.
Algorithm Linear Search
LINEAR [DATA, N. ITEM, LOC]
Here DATA is a linear array with N elements and ITEM is a given item of information. This
algorithm finds the location LOC of ITEM in DATA or sets LOC=0, if search is unsuccessful.
Step 1: set DATA [N+1]:= ITEM
Step 2: [Initialize counter] set LOC := 1
Step 3: Repeat while DATA [LOC] ≠ ITEM
Set LOC :=LOC+1 [End of loop]
Step 4: IF LOC = N+1 then set LOC := 0
Step 5: Exit

BINARY SEARCH :
Algorithm for Binary Search
(Binary Search) BINARY [DATA, LB, UB, ITEM, LOC] Here DATA is sorted array with lower
bound LB and upper bound UB and ITEM is given item of information. The variables BEG,
END and MID denote respectively the beginning, end and middle location of a segment of
elements of DATA. This algorithm finds the location LOC of ITEM in DATA or set LOC=NULL
Step 1: Set BEG = LB, END:= UB and MID=INT [(BEG+END)/2]
Step 2: Repeat steps 3 and 4 while BEG <= END and DATA [MID] ITEM
Step 3: IF ITEM < DATA [MID], then
Set END MID-1 Else:
Set BEG MID+1
Set MID: =INT [(BEG+END)/2]
IF data [MID] = ITEM, then:
Set LOC: =MID Else:
Set LOC:=NULL
Step 4: Exit
POINTER ARRAYS
An array whose each element is a pointer is called pointer array
e.g int p[4]-pointer array
Int a [4]-array of integers
P(0)=&a[0] p(2)=&a[2]
P[1]=&a[1] P[3] &a[3]
This pointer array p holds the address of each element in array a so it is called Pointer array
Detailed Example of Pointer Array
Suppose TEAM is an array, which contains the locations of different teams or more
specifically locations of first elements in different teams.

1 Sachin
4 Ajay
Ravi
9
Rakesh
12
Ajit
Nilesh
Vijay
Kapil
Narendra
Ramesh
Niren
$$$$
2.7 RECORD
A record is collection of related data items. Each data item is termed as field. File is
collection of similar records. Each data item may be a group item composed of sub items.
Comparison:
Record Linear Array

A record may be a collection of non

homogeneous data, The data items in an array may have
i.e. the data items in a record may same data types
have different data types.

There may be natural Ordering of its

elements.
The data items in a record are indexed
by attributes So there may not be a
natural Ordering if its elements
LINKED LIST
Linked list or one-way list is a linear collection of data elements called nodes where the
linear order is given by means of pointers. Each node is divided into two parts:
1. First part contains the information of the element.
2. Second part contains the address of next node in list (it is called link field).
START is a pointer variable, which contains the address of first node.
Left part represents the information part of the node while right part represents the
next pointer field of node. The pointer of last node contains a special value called
NULL, which is an invalid address.
The schematic diagram of a linked list with 4 nodes is shown below,

The following diagram shows a linked list:

Name of player and no of runsfrom an information part while next pointer field gives the
next node’s address in linked list.

Name of player Runs Next

Ajay 84 3
Sachin 90 NULL
Ravi 40 2
Ajit 80 1

Representation of Linked List in Memory

Let List be a linked list Then LIST will be maintained in memory as follows,
1) LIST requires 2 arrays, we will call them here INFO and LINK such that INFO [K]
and LINK [K] contain respectively the information part and next pointer field of
a node K of list
2) LIST also requires a variable name such as START, which contains the location of
beginning of list and next pointer sentinel denoted by NULL, which indicates
end of list
The following e g. shows how linked list is stored in memory. The nodes of the list need not
occupy adjacent elements in the arrays INFO and LINK and more than one list may be
maintained in the same linear arrays INFO and LINK. But each list must have its pointer
variable giving the location of its first node.
Linked List can be picturized in following manner.
 1. START=9, INFO [9]=L, LINK [9]= 3
2. INFO [3]= 1, LINK [3]=4
3. INFO [4]=N, LINK [4]= 8
4. INFO (8)=K, LINK [8]=11
5. INFO [11]=L, LINK [11]=6
6. INFO [6]=1, LINK [6]= 7
7. INFO [7]=S, LINK [7] = 12
8. INFO (12)=T. LINK [12]=0. Last node
i.e. “LINK LIST” string is stored in form of Linked List.
Advantages of Linked List
Generally lists are stored in form of arrays. But in arrays insertion and deletion is not easy.
Also array size can’t be easily increased. Using linked list this problem can be solved.
TREE DATA STRUCTURE
In case of Link data structure, each node has link information of next node. Thus
sequentially, we can access all the nodes. It will be time consuming for searching long
list;because each node has information about next node only. In order to reduce time
consumption, binary tree concept was developed. Before going to binary search tree, let us
learn basics of tree structure.
Tree is an hierarchical structure of collected data [Link] is nonlinear structure.
Node. It is as element of list. It may be a character, string or number.

Node Node’s description

ROOT A node which has no parent. The node containing A’ is the root of the
tree

CHILD Nodes of root

(a) LEFT CHILD The left node of root
(b) RIGHT CHILD The right node of root. The node containing A has left child containing
node B and right child containing node C
PARENT Node which has child (or children). A is parent of B and C
LEAF The node which has no child (or children) D, G, K, M are leaves
 SIBLINGS Two nodes have the same parent. The nodes containing D and E are
both children of the node containing B. These nodes are siblings.
ANCESTOR The node is an ancestor of another node, if it is a parent of that node.
The ancestors of the node containing G are the nodes containing E, B, A.
ROOT is always an ancestor of every node.
DESCENDANT The node is a descendant of another node, if it is a child of that node.
The descendant of the node containing E are the nodes containing G, H,
K. All nodes in the tree are descendants of the ROOT
LEFT SUBTREE The descendants of root’s left child which acts a root of subtree.
RIGHT SUBTREE The descendants of root’s right child which acts a root of subtree.
LEVEL The distance from the ROOT The ROOT is always at zero (0) level.

Types of Tree
Trees can be classified according to node structure such as
1) Null free: a tree without node.
2)Binary tree: A tree which has left and right child.
3)Ordered tree: Children of each node are ordered from Left to Right.
4)Nonordered tree: Children of each node are not ordered from Left to Right
Binary Tree
A binary tree T is defined as a finite set of elements called nodes, such that 1) T is empty
(called NULL tree or empty tree) or 2) T contains a distinguished node R called the root of T
and remaining nodes of T form an ordered pair of disjoint binary trees T, and T2.
“If T contains a root R then the two trees T, and T2 are called respectively left and right sub
trees of R. If T, is nonempty, then its root is called left successor of R. Similarly if T2 is
nonempty then its root is called right successor of R
1) B is left successor of A and C Is right successor of node A.
2)The left sub tree of root A consists of node B, D, and E and the right subtree of A consists
of nodes C, G, H, J. K and L.
3)Any node N in a binary tree T has either 0, 1,2 successors. The nodes A, B, C, H have two
successors. The nodes D, E, G, L and K have no successors that nodes are called terminal
nodes.
Binary tree T and T, are said to be similar if they have same structure. The trees are said to
be copies if they are similar and if they have same contents at corresponding nodes.
Algebraic Expressions
These can be represented as tree. Each variable or constant in E appears as Internal node of
T whose left and right subtrees corresponding to the operands of Operation.
Complete Binary Tree:
Consider any binary tree T. Each node at T can have at most two children. The level r of T
can have at most 2’ nodes. The tree T is said to be complete if all its levels except possibly
the last have maximum no. of possible nodes and if all the nodes at the last level appear as
far as left as possible.

Extended Binary Tree

A binary tree T is said to be 2 tree or extended binary tree, if each node N has either n or 2
children. In this case nodes with 2 children are called internal nodes while nodes with 0
children are called external nodes. Any binary tree may be converted into a 2 tree by
replacing each empty subtree by a new node. The nodes in original tree are internal nodes
in the extended Tree and the new nodes are external nodes in the extended tree.

Representing binary trees in memory

Let T be a binary tree There are two way of representing binary trees in Memory
1) Linked representation 2) Sequential representation
1) Linked representation
In this method 3 parallel arrays are used INFO, LEFT and RIGHT 1) INFO [K] contains the data
at node N
1) LEFT [K] contains the location of left child of node N.
2) RIGHT [K] contains the location of right child of node N. 4) ROOT will contain the
location of root R of T. It is a pointer variable.
3) If any subtree is empty then corresponding pointer will contain a null Value
 INFO LEFT RIGHT

Sequential Representation
Suppose T is complete binary tree then only single linear array TREE is used As follows.
1) The root R is stored in TREE [0]
2) 1) If node N occupies TREE [K] then left child is stored in TREE [2K] and Its right child
is stored in TREE [2 K+1]
3) If TREE [1]= NULL then it is empty.

STACK AND QUEUE DATA STRUCTURE

STACK:
A stack is a list of elements in which an element may be inserted/deleted only at one end,
called the top of stack Elements are removed from a stack in a reverse order of that in,
which they were inserted into the stack. So it is generally referred as
LIFO (Last In First Out structure).
Two basic operations associated with stack are as follows
1) Push-To insert an element into a stack
2) 2) Pop-To delete an element from a stack
Queue:
A queue is a linear list of elements in which deletions can take place only at one end called
the front and insertions can take place only at other end called the rear Queues are also
called FIFO (First In First Out lists) i.e. first element in a queue will be first element out of
the queue. Queues abound in every day life. E.g queue Waiting for a bus.