Introduction

• The logical or mathematical model of a particular organization of data is called a data

structure. Types of data structure:
• Data structures are classified as:
1. Linear data structure:
A data structure is said to be linear if its elements form a sequence, or in
other words, a linear list. There are two basic ways of representing such linear
structure in memory.
2. Non linear data structure:
This structure is mainly used to represent data containing a hierarchical
relationship between elements, that is, records, family trees and table of contents
such as trees and graphs.
 Data structure operations
• Traversing: Accessing each record exactly only once so that certain items in the record may
be processed.
• Searching: Finding the location of the record with the given key value, or finding the
locations of all the records.
• Inserting: Adding a new record to the structure.
• Deleting: Removing a record from the structure.
• Sorting: Arranging the records in some logical order (e.g. alphabetically or numerically).
• Merging: Combining the records in two different sorted files into single sorted file.
 Control Structure
The control structures are as follows:
1. Sequence logic, or sequential flow
2. Selection logic, or conditional flow
3. Iteration logic, or repetitive flow
 Sequence flow
 It means that the flow of the structure flows in sequence. The
sequence can be presented by means of numbered steps or by
which the modules are written.
 Example:
 Selection flow
 Selection logic employs a number of conditions, which lead to a selection
of one out of several alternative modules. The structures which
implement this logic are called conditional structures or IF structures.
 These conditional structures fall into three types :
(a) Single alternative
(b) Double alternative
(c) Multiple alternative
 Iteration flow
 This type of logic refers with a repeat statement involving loops. Each
type begins with a Repeat statement and is followed by a module,
called the body of the loop.
 Example:
 Introduction
 A linear array is a list of finite number “n” of homogenous data elements (data elements of same data) such that:
a. The elements of array are referred respectively by an index set consisting of “n” consecutive number.
b. The elements of array are stored respectively in successive memory locations.
 The number ‘n’ of elements is called the length or size of the array.
 The length or the number of data elements of the arrays can be obtained from the index set by the formula.
LENGTH = UB-LB+1
Where,
UB is the length index called upper bound.
LB is the smallest index called lower bound.
 Traversing
 LA is a linear array with lower bound LB and upper bound UB. This algorithm
traverses LA applying an operation PROCESS to each elements of LA.
 Algorithm:
1. Set K: = LB // Initialize counter
2. Repeat Steps 3 and 4 while K<UB
3. Apply PROCESS to LA[k]. // Visit element
4. Set K: = K+ 1. // Increase counter
[End of Step 2 loop]
5. Exit.
 Insertion in array
 Insertion at end is done very easily.
 To insert an element in the middle of the array, the elements must be moved
downward to new locations to accommodate the new element and keep the
order of the other elements.
 Algorithm: INSERT(LA, N,K,ITEM) - Here LA is a linear array with N elements
and K is a positive integer such that K N. This algorithm inserts an elements
ITEM into the Kth position in LA.
1. Set J = N //Initialize counter
2. Repeat Steps 3 and 4 while J =K.
3. Set LA[J+1]: = LA[J] // Move Jth element downward
4. Set: J=J-1. // Decrease counter [End of step 2 loop.]
5. Set LA [k]: = ITEM. // Insert element
6. Set N: = N+1 // Reset N
7. Exit.
 Deletion in array
 Deleting an element at the “end” of an array presents no difficulties, 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: DELETE (LA,N,K,ITEM) - Here LA is a linear array with N elements
and K is a positive integer such that K<N. This algorithm deletes the Kth
elements from LA.
1. Set ITEM: = LA[K].
2. Repeat for J = K to N-1:
Set LA [J]:=LA[J+1] //Move J+1st element upward
[End of loop.]
3. Set N:=N-1 //Reset the number N of elements in LA
4. Exit.
Bubble Sort
• Let A be a list of n numbers.

• Sorting A refers to the operation of rearranging the elements of A so

they are in increasing order. That is,

A[1]<A[2]<A[3]<.............<A[N].

• Example: 5,4,7,9,2,3; the sorted elements are 2,3,4,5,7,9

Bubble Sort : Algorithm
SORT ( DATA , N )
1. Repeat step 2 and 3 for K = 1 to N-1.
2. Set PTR:=1 //Initialize pass pointer PTR
3. Repeat while PTR <= N-K. //Execute pass
a) If DATA [PTR]> DATA [PTR+1],then
Interchange DATA [PTR] and DATA [PTR+1]
[End of If structure]
b) Set PTR:= PTR+1.
[End of inner loop.]
[End of step 1 outer loop]
4. Exit.
Bubble Sort : Example
 Linear Search
LINEAR (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements and ITEM is given element. This algorithm finds the
location LOC of ITEM in DATA or sets LOC = 0, if search is successful.
Step 1: [Insert ITEM at the end of DATA]
Set DATA[N+1] : = ITEM
Step 2: [Initialize counter]
Set LOC : = 1
Step 3: [Search for item]
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
BINARY (DATA, LB, UB, ITEM,LOC) :This algorithm finds the location LOC of ITEM in DATA or sets
LOC = NULL.
1. [Initialize segment variables.] Set BEG=LB, END=UB and MID=INT(BEG+END/2)
2. Repeat step 3&4 [while BEG <= END and DATA [MID] ≠ITEM]
3. If ITEM<DATA [MID], then:
Set END=MID-1.
Else:
Set BEG=MID+1. [End of If structure]
4. Set MID=INT((BEG+END)/2) [End of step 2 loop]
If DATA [MID]= =ITEM, then:
Set LOC=MID
Else:
Set LOC=NULL [End of If structure]
5. Exit.
 Binary Search
Let DATA be the following sorted 13-element array:
DATA: 11,22,30,33,40,44,55,60,66,77,80,88,99
Suppose we are searching ITEM=40 So, it will be like Initially,
BEG=1 and END=13.
Hence
MID = INT(1+13)/2=7 & so DATA[MID]=55
Since 40<55, END has its value changed by
END=MID-1 =6.
Hence,
MID=INT[(1+6)/2] =3 & so DATA [MID] = 30
Since 40>30, BEG has its value changed by BEG=MID+1 = 4 Hence
MID=INT [(4+6)/2] =5 & so DATA[MID] =40
We have found ITEM in location LOC=MID=5.
Linear Search Vs Binary Search
 Definition and Example
 An array whose each element is a pointer is called pointer array.
 Example:
 What is record ?
• A record is collection of related data items.
• Each data item is termed a field.
• File is collection of similar records.
• Each data item may be a group item composed of sub item.
• Example: Suppose a college keeps a record of each student such as : Name, City,
Pincode, and Phone No.
• Item in record is accessed using dot operator as follows: Student.name
• Representation of records in memory: A file is stored in memory as collection of arrays.
 How record differs from a linear array?

• A record may contain non-homogeneous data i.e. data elements may be of

different data types. An array always contains homogeneous data.

• In a record, natural ordering of elements is not possible. Array elements

can be naturally ordered.

• Elements of record are referenced by level number, while those of array can
be referenced by an index set consisting of n consecutive numbers.
 Linked List
• A 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: the first part contains the information of the element,
and the second part, called the link field or next pointer field, contains the address of the
next node in the list.

Info Link
• The diagram below of a linked list contains 6 nodes.
 Memory Representation of Linked List
• Let LIST be a linked list.
• LIST requires two linear arrays-called as INFO and LINK.
• Example:
 START =9, so INFO[9] = N is the first character.
 LINK [9]=3, so INFO [3] = 0 is the second character.
 LINK [3] = 6, so INFO [6] = (blank) is the third character.
 LINK [6] = 11, so INFO [1] = E is the fourth character.
 LINK [11] = 7, so INFO [7] = X is the fifth character.
 LINK [7] = 10, so INFO [10] = I is the sixth character.
 LINK[10]= 4, so INFO [4] = T is the seventh character.
 LINK [4] = 0, the NULL value, so the list has ended.
 In other words, NO EXIT is the character string.
 Trees
• Tree is an hierarchical structure of collected data items.
• It is non-linear structure.
• Terminology:

• Types of Tress:
Tree can be classified according to node structure such as:
1. Null Tree: A tree without node.
2. Binary Tree: A tree which has left and right tree.
3. Ordered Tree: Children of each node are ordered from left to right.
4. Non-ordered Tree: Children of each node are not ordered.
 Binary Tree
A binary tree T is defined as a finite set of elements, called nodes, such that:
a) T is empty (called the null tree or empty tree),or
b) T contains a distinguished node R, called the root of T and the remaining nodes of T form
an ordered pair of binary trees T1 and T2.
c) If T is non-empty, then its root is called the left successor of R; similarly if T is non-empty,
then its root is called the right successor of R.
 Expression Tree
Example: 3+((5+9)*2)
 Memory Representation of Trees
• Let T be a binary.
• There are two ways for representing binary tree in
memory.
1. Sequential Representation
2. Linked Representation
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. If node N occupies TREE[k] then left child is stored in
TREE[2*k] and its right child is stored in TREE[2*k+1].
3. If TREE[1] = NULL then it is empty.
 Memory Representation of Trees
Linked Representation:
• A tree T can be maintained in memory be means of a linked representation which uses
three parallel arrays INFO , LEFT and RIGHT and a pointer variable ROOT.
• Each node N of T will correspond to a location K such that:
1. INFO[K] contains the data at the node N.
2. LEFT[K] contains the location of the left child of node N.
3. RIGHT[K] contains the location of the right child of node N.
4. ROOT will contain the location of root R of T. it is a pointer variable.
5. if any subtree is empty then corresponding pointer will contain a null value.
 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.
 It is referred as LIFO (Last In First Out).
 Two basic operations associated with stack are:
1. Push : To insert an element into a stack. 2.Pop: To delete an element from a stack.
 Example:
1. Suppose 11,12,43,24 ; is a set of data elements.
2. Inserting element 65.
3. To delete 43 from the stack, first delete the top element i.e. 65, then the second, then third.

1 2 3
 Queue
 A queue is a linear data structure in which data elements can be inserted from one end and
deleted from the other end.

 The element which is inserted first is deleted first and the element which has entered in the end
will be deleted last, so the term FIFO.

 The element is inserted from the “rear” and delete the element from the “front”.

 Example:

1. Suppose, 11,12,43,24 is a set of data elements

2. Inserting element 65.

3. To delete the element 11.