1

[Link]. IV SEMESTER

II YEAR IV SEMESTER
Paper-IV: DATA STRUCTURES
UNIT I
Concept of Abstract Data Types (ADTs)- Data Types, Data Structures, Storage Structures, and
File Structures, Primitive and Non-primitive Data Structures, Linear and Non-linear Data
Structures.
Linear Lists – ADT, Array and Linked representations, Pointers.
Arrays – ADT, Mappings, Representations, Sparse Matrices Linked Lists: Single Linked List,
Double Linked List, Circular Linked List , applications
UNIT II
Stacks: Definition, ADT, Array and Linked representations, Implementations and Applications
Queues: Definition, ADT, Array and Linked representations, Circular Queues, Dequeues,
Priority Queues, Implementations and Applications.
UNIT III
Trees: Binary Tree, Definition, Properties, ADT, Array and Linked representations,
Implementations and Applications. Binary Search Trees (BST) – Definition, ADT, Operations
and Implementations,

UNIT IV
Graphs – Graph and its Representation, Graph Traversals, Connected Components, Basic
Searching Techniques, Minimal Spanning Trees
UNIT- V
Sorting and Searching: Selection, Insertion, Bubble, Merge, Quick, sort, Sequential and Binary
Searching.

Data Structures Prepared by Mahesh MCA

 2
[Link]. IV SEMESTER

UNIT I

Concept of Abstract Data Types (ADTs)

1. Define data structures. List various types of data structures. (OR)

Write short notes on Primitive and Non-primitive data structures.
Data may be organized in many different ways. The logical (or) mathematical model of a
particular organization of a data is called data structure. It is a collection of values and
possible operations.
Structural representation of data items, storage & retrieval operations efficiently.

Primitive Data Structures

 Primitive Data Structures are the basic data structures that directly operate upon
the machine instructions.
 Primitive data structures have different representations on different computers.
 Integers, Floating point numbers, Character constants, String constants and Pointers come
under this category.
 These data types are available in most programming languages as built in type.
o Integer: It is a data type which allows all values without fraction part. We can use it
for whole numbers.
o Float : It is a data type which use for storing fractional numbers.
o Character: It is a data type which is used for character values.
o Pointer : Pointer is a variable which holds memory address of another variable.

Non – Primitive data structures: Non-primitive data structures are more

shopisticated data structures.

Data Structures Prepared by Mahesh MCA

 3
[Link]. IV SEMESTER

 These are derived from primitive data structures. But extending the size and ranges of
basic data type
 They focus on grouping same or different data items with relationship between each
data item.
 Arrays, Lists and Files come under this category.
 Array: An array is a collection of memory locations which can share same data name
and same data type values.
 List: An order set containing variable number of elements is called as lists.
o The list is a sequential data structure.
o Lists are a way to store many different values under a single variable.
o Every item in this list is numbered with an index.
 File: A file is a collection of logically releated inforation. It can be viewed as large
list of records consisting of various fields.
 A Non- primitive data type is further divided into linear and Non- linear data
strucutre.
 Linera data stucture: A data structure is said to be linear if its elements form a
sequence or a linear list. Example: array, stacks, queues and linked lists come under
this category.
 Non- Linear data strucutres: A data structure is said to be non linear if its elements
form a hierarchical classification where, data items appear at various [Link] and
Graphs are widely used non-linear data structures.

Write a detail note on 1. ADT [Link] types 3. Primitive types

Data Type: Data type defines what type of value to stored on a variable.(or)A data type
defines a set of values and the allowable operations on those values. Different data types
include:
1. Abstract data types (ADT )
2. Composite types
3. Primitive types
Abstract data types (ADT ) : Abstract data types are mathematical models of
a set of data values or information that share similar behaviors. Abstract data
types are used in algorithms and also data items.(OR)
ADT is a user defined data type which encapsulates a range of data values and
their functions. (OR)

An abstract data type is a definition of new type, describes its properties and
operations.
Ex: ―Stack‖ is a ADT which contains push( ), pop( ) operations.
―Linked List‖ is a ADT which contains insert( ), delete( ) operations etc.
In an ADT, we encapsulate the data and the operations on data and we hide
them from the [Link] abstract data type consists of

Data Structures Prepared by Mahesh MCA

 4
[Link]. IV SEMESTER

i) Declaration of data
ii) Declaration of operations
Advantages:
 Code is easier to understand.
 Implementations of ADTs can be changed without requiring changes to
the program that uses the ADTs.
 ADTs can be reused in future programs.
Composite types: Composite data type is any data type which can be
constructed in a program using the programming languages like primitive data
types and other data types.
Example : Structures, unions in ‗c‘.
struct Account
{
int account_number;
char first_name;
char last_name;
float balance;
};
Primitive types:
Primitive types are data types provided by a programming language. Primitive
types are also known as built-in types or basic types.
primitive types may include:
1. Character (character, char);
2. Integer (integer, int, short, long, byte) with a variety of precisions;
3. Floating-point number (float, double, real, double precision);
4. Boolean having the values true and false.
Basic primitive types :
SIZE NAME SIGNED INTEGER UNSIGNED
RANGE INTEGER RANGE
8 bits Byte -128 to + 127 0 to 255
16 bits Integer -32,768 to +32,767 0 to 65,535
-2,147,483,648
Double to
32 bits Long +2,147,483,648 0 to 4,294,967,295
integer
64 bits Long(JAV -9,223,372,036,854,775,808 0 to
A) to 18,446,744,073,709,551,
+9,223,372,036,854,775,808 615

Integer numbers
An integer number can hold a whole number, but no fraction. Integers may be
either signed (allowing Negative values) or unsigned (non negative values only).

Floating-point numbers

Data Structures Prepared by Mahesh MCA

 5
[Link]. IV SEMESTER

A floating-point number represents a real number that may have a fractional

part. These numbers are stored internally in scientific notation, they also called
decimal number. Floating point number contains integer, decimal point(.) and
exponent notation(‗e‘).
Examples of floating-point literals are: 20.0005 , 99.9 , −5000.12 , 6.02e23
Boolean: A boolean type is a single-bit type that can be either true (1) or false
(0).
Characters and strings: A character type (typically called "char") may contain
a single letter, digit, punctuation mark, or control [Link] may be
combined into strings. The string data can include numbers and other
numerical symbols but will be treated as text.
Examples: ‘G‘ ‗M‘, "gminformatics" ,…
Write a details note on storage structures & Fie structures :
Storage Structures
The representation of a particular data structure in the memory of a computer
is called a storage structure. The storage structures are classified into:
[Link] storage(temporary)
[Link]-Volatile storage(parmanent)
Contents available even when power is switched off. includes secondary and
tertiary storage, as well as battery backed up main memory.
Storage Hierarchy

Cache memory: Fastest and most costly form of storage, volatile, managed by
the computer system hardware. Cache memory is an intermediate storage between
the CPU Registers and Main [Link] is small and fastest [Link] memories
are accessed much faster than RAM.
Main memory: Main memory also called as primary memory. Primary memory is
the only type memory that is directly accessed by the CPU. Any data operated by the
CPU, is stored in primary memory. Contents of main memory are usually lost if a
power failure or system crash occurs.

Data Structures Prepared by Mahesh MCA

 6
[Link]. IV SEMESTER

Flash Memory:
Data can be written at a location only once, but location can be erased and
written to [Link] support only a limited number (10K – 1M) of write/erase
[Link] writes are slow (few microseconds), erase is slower.
Optical storage
The Optical Drives are latest technology devices, that uses ―Light Sensors‖ to store the
[Link] Light Sensors are called ―Lasers‖.Optical drives are most widely used
and reliable storage [Link] most popular optical storage devices are:
a) CD-ROM
b) DVD-ROM
c) CD-R
d) CD-RW
Magnetic Disk
Data is stored on spinning disk, and read/written [Link]
medium for the long-term storage of [Link] must be moved from disk to
main memory for access, and written back for [Link] access i.e.
possible to read data on disk in any order, unlike magnetic tape.
Magnetic Tapes
Hold large volumes of data and provide high transfer [Link] slow access
time in comparison to magnetic disks and optical disks limited to sequential
[Link] mainly for backup, for storage of infrequently used information.
FILE STRUCTURES
A storage structure representation in auxiliary memory is often called a file
structure.A file is a collection of data stored on mass storage (e.g., disk or
tape).Advantages of mass storage
 Too big to fit in main memory
 Share data between programs
 Backup (disks and tapes are less volatile than main memory)
The data is subdivided into records. Each record contains a number of fields.
One or more field is the key field (e.g., address).
Files

Sequential Access Random Access

SEQUENTIAL ACCESS
A sequential file is one in which records can only be accessed one after another
from beginning to end. Records are stored one after another in auxiliary
storage, such as tape or disk, and there is an EOF (end-of-file) marker after the
last record. The operating system has no information about the record

Data Structures Prepared by Mahesh MCA

 7
[Link]. IV SEMESTER

addresses, it only knows where the whole file is stored. The only thing known
to the operating system is that the records are sequential.

Random access
If we need to access a specific record without having to retrieve all records
before it, we use a file structure that allows random access. Two file structures
allow this: indexed files and hashed files
INDEXED FILES
To access a record in a file randomly, we need to know the address of the
record.

HASHED FILES
A hashed file uses a mathematical function to accomplish this mapping. The
user gives the key, the function maps the key to the address and passes it to
the operating system, and the record is retrieved.

Data Structures Prepared by Mahesh MCA

 8
[Link]. IV SEMESTER

Discuss about linear and Non linear data structures.

Linear data structures:

 A data structures is said to be linear, if its elements are connected in linear
fashion by means of logically or in sequence memory locations.
 A Linear data structure is a sequential representation of several data items
with one starting point and one ending point. That is a linear data structure
will have only one starting point and only one ending point.

 There are two ways to represent a linear data structure in memory,

o Static memory allocation
o Dynamic memory allocation
 The possible operations on the linear data structure are Traversal, Insertion,
Deletion, Sorting and Merging.
 Example of linear data structure One Dimensional Array, Linear Linked List,
Stack, Linear Queue.
 Array: An array is a collection of memory locations which can share same
data name and same data type values.
 Stack: Stack is a data structure in which insertion and deletion operations
on performed at one end only.
o The Insertion operation is refered to as ‗PUSH‘ and deletion oepration
is referred to as ‗POP‘ Operation.
o Stack is also called as Last in Fist Out( LIFO) data structure.
 Queue: The data structure which permits the insertion at one end and
deletion at another end, known as Queue.
o End at which deletion is occurs is known as FRONT end and another
end at which insertion occurs is known as REAR end.
o Queue is also called as First in First out data structure.
Non linear data structures:
 Non linear data structures are those data structure in which data items are
not arranged in a sequence.
 A non-linear data structure is a non-sequential representation of several
data items with several starting points and several ending points or no
definite starting and ending points.
 Example of non linear data structure are Hierarchical Structures, Circular
Structures, Topographical Structures tree and Graph.

Topographical Structures:

Diplom
a
Data Structures Prepared by Mahesh MCA
 9
[Link]. IV SEMESTER

Circular structure:

 Tree: a tree can be defined as finite set of data items(nodes) in which data
items are arranged in branches and sub branches according to requirement.
 Trees consist of nodes connected by edge, the node presented by circle and
edge lives connecting to circle.
 Graph: Graph is a collection of nodes (information) and connecting edges(
Logical relation) between nodes.
 A tree can be viewed as a restricted graph.
 Graphs have many types.
o Un- directed graph
o Directed graph
o Mixed graph
o Multi graph
o Simple graph
o Null graph
o Weighted graph

Diference between linear and Non linear data structures:

Linear Data structure Non Linear data structure
Every item is related to the previous Every item is attached with many
and time other items.
Data is arrange is linear sequence Data is not arranged in sequence
Data items can be traversed in a Data cannot be traversed in single run.
single run.
Eg. Array, stacks, linked list, queue [Link], graph
Implementation is easy Implementation is difficult.

Data Structures Prepared by Mahesh MCA

 10
[Link]. IV SEMESTER

Arrays
Definition:
An array is a finite, ordered and collection of homogeneous data elements. An
array is finite because it contains only a limited number of elements, ordered
as all the elements are stored one by one in contiguous locations of the
computer memory in a linear order. As homogeneous all the elements of an
array are of the same data type.
Basic Terminology:
Size: The number of elements in an array is called the size or length of the
array.
Type: The type of an array represents the kind of data type .
Base: The base of an array is the address of the memory location where the
first element of the array is located.
Element − Each item stored in an array is called an element.
Index: All the elements in an array can be referenced by a subscript like A[i],
this subscript is known as index. The index value is always an integer value.
Range of Indices: Indices of arrays elements may range from a lower bound to
an upper bound called boundaries of an array.
Word: Word ‗w’ denotes the size of an element i.e., the amount memory that is
required to store an element of the array.

One-Dimensional arrays and their address mapping and operations

Definition:An array is a finite, ordered and collection of homogeneous data
elements. An array is finite because it contains only a limited number of
elements, ordered as all the elements are stored one by one in
contiguous/consecutive locations of the computer memory in a linear order. As
homogeneous all the elements of an array are of the same data type.

One-Dimensional Array:If only one subtype/index is required to refer an

element in an array, then the array is called as ―One-Dimensional Array‖.

Memory Allocation:All the indexed variables of an array are allocated

contiguous memory locations in computer‘s memory. So memory
representation of an array is simple. Suppose, we have an array with
n indexed variables, let the memory location of the first element is M.
If each element requires one word, then the location of any element
in the array can be calculated by using the following
[Link] (A[i]) =M+(i x w)

Physical Representation

Eg: Let M=4560 and w=1,calculate the address of A[0], A[2], A[7]

Address (A[0]) = 4560+(0)x1 = 4560

Data Structures Prepared by Mahesh MCA

 11
[Link]. IV SEMESTER

Address (A[2]) = 4560 +(2)x1 = 4562

Address (A[7]) = 4560 +(7)x1 = 4567

Operations: Various operations that can be performed on an array are like

Traversing, Sorting, Searching, Insertion, Deletion and Merging.

Following operations can be performed on arrays:

Traversing: It is used to access each data item exactly once so that it can be
processed.
Searching: It is used to find out the location of the data item if it exists in the
given collection of data items.
Insertion: It is used to add a new data item in the given collection of data
items.
Deletion: It is used to delete an existing data item from the given collection of
data items.
Sorting: It is used to arrange the data items in some order i.e. in ascending or
descending order in case of numerical data and in dictionary order in case of
alphanumeric data.
Merging: It is used to combine the data items of two sorted files into single file
in the sorted.
Multi-Dimensional arrays and their address mapping and operations
Definition:An array is a finite, ordered and collection of homogeneous data
elements. An array is finite because it contains only a limited number of
elements, ordered as all the elements are stored one by one in contiguous
locations of the computer memory in a linear order. As homogeneous all the
elements of an array are of the same data type.

Multi-Dimensional Array:If elements are represented using more than one

index/subscript, then the array is called as ―Multi-Dimensional Array‖. Two
dimensional arrays are a collection of homogeneous elements in which
elements are ordered in rows and columns.

Eg: Consider an array of size mxn, here m is the [Link] rows and n is the [Link]
columns as follows.

a11 a12 a13 . . . . a1n

a21 a22 a23 . . . . a2n mXn
. . . ……………………
....
am1 am2 am3 . . . .
amn

Data Structures Prepared by Mahesh MCA

 12
[Link]. IV SEMESTER

Memory Representation: Like one-dimensional arrays, two-dimensional

arrays are also stored in contiguous memory locations. There are two
conventions of storing two-dimensional array elements in the memory.

1. Row-Major Order

2. Column-Major Order

Row-Major Order:The elements of a two-dimensional array are stored in row-

by-row basis, that is all the elements in the first row, then in the second row
and so on.

Column-Major Order:The elements of a two-dimensional array are stored in

column-by-column basis, that is all the elements in the first column are stored
in their order of rows, then in the second column and so on.

Eg:
a11 a12 a13
a21 a22 a23
a31 a32 a33
3X3

Memory Representation

Referencing an element: To refer an element in a two-dimensional structure,

we need two index values one for row another for column. The indexing formula
of row-major order is different from columnmajor [Link] us assume that we
have an array with mxn elements.

Row-Major Order:

Address(aij) = (i-1)xn+j

Eg: Address(a32) = ((3-1)x3)+2 = 2x3+2 = 8

If the base address is M, then the above formula can be modified as follows.

Data Structures Prepared by Mahesh MCA

 13
[Link]. IV SEMESTER

Address(aij) = M+(i-1)xn+j-1

Eg: Address(a32) = 4560+((3-1)x3)+2-1

= 4560+2x3+2-1

=4560+6+2-1 = 4567

Column-Major Order:

Address(aij) = (j-1)xm+j

Eg: Address(a32) = ((2-1)x3)+2 = 2x3+2 = 6

If the base address is M, then the above formula can be modified as follows.

Address(aij) = M+(j-1)xm+i-1

Eg: Address(a32) = 4560+((2-1)x3)+3-1

= 4560+3+3-1

=4560+3+2 = 4565

Sparse Matrix and representation of Sparse Matrix

A sparse matrix is a two – dimensional array where the majority of the elements have
the value null.

Input : An array a with two- Another array spm with two multiplied by 3.`

Output : Representation of Sparse Matrix in a Triplet Form.

SparseMatrix:Two columns mxn . There may be situation in ins Non-Zero values.

Such matrix is non-zero values, that is majority of values non-zero values. So, to
represent those 6 values, we are we can represent the sparse matrix by using Triplet -
dimensions containing elements, most of the elements are zeros two-dimensions
whose size is equal to [Link] non-dimensional array.

The above matrix contains 5 rows and 6 columns. Then the total number of
elements are 5x6=30. If each element requires 4 Bytes of memory, then we
need totally 120 Bytes of memory. But if we observe the matrix, it has very few
non-zero values, that is majority of values are zeros. We have only 6 non-zero

Data Structures Prepared by Mahesh MCA

 14
[Link]. IV SEMESTER

values. So, to represent those 6 values, we are wasting 120-(6x4) = 120-24 = 96

Bytes of memory. (6x4) = 120-24 = 96 Bytes of memory.

An array a with two-dimensions containing elements, most of the elements are

zeros Another array spm with two-dimensions whose size is equal to [Link] non-
null values multiplied by 3. Representation of Sparse Matrix in a Triplet Form.

Sparse matrices are used by scientists and engineers when solving partial
differential equations. For example, a measurement of a matrix's sparsity can
be useful when developing theories about the connectivity of
computer networks. When using large sparse matrices in a computer program,
it is important to optimize the data structures and algorithms to take
advantage of the fact that most of the values will be zero.

Data Structures Prepared by Mahesh MCA

 15
[Link]. IV SEMESTER

Discuss about the list implementation concepts.

Linked List is a linear data structure and it is very common data structure
which consists of group of nodes in a sequence which is divided in two
[Link] node consists of its own data and the address of the next node and
forms a [Link] Lists are used to create trees and graphs.

Advantages of Linked Lists

 They are a dynamic in nature which allocates the memory when
required.
 Insertion and deletion operations can be easily implemented.
 Stacks and queues can be easily executed.
 Linked List reduces the access time.
Disadvantages of Linked Lists
 The memory is wasted as pointers require extra memory for storage.
 No element can be accessed randomly.
 it has to access each node sequentially.
 Reverse Traversing is difficult in linked list.

Applications of Linked Lists

 Memory management: linked list are useful in managing memory as
dynamic i.e., DMA.
 Polynomial manipulations: the operations on polynomial such as
addition, subtraction,multiplication etc are easily implemented using
linked lists.
 Insertions and deletions in graphs of data: the insertions and
deletions are efficiently performed when linked lists are used to maintain
the group of data.
 Linked lists are used to implement stacks, queues, graphs, etc.
 Linked lists let you insert elements at the beginning and end of the list.
 In Linked Lists we don‘t need to know the size in advance.

Data Structures Prepared by Mahesh MCA

 16
[Link]. IV SEMESTER

Types of Linked Lists

Singly Linked List : Singly linked lists contain nodes which have a data part
as well as an address part i.e. next, which points to the next node in sequence
of nodes. The operations we can perform on singly linked lists are insertion,
deletion and traversal.

Doubly Linked List : In a doubly linked list, each node contains two links the
first link points to the previous node and the next link points to the next node
in the sequence.

Circular Linked List : In the circular linked list the last node of the list
contains the address of the first node and forms a circular chain.

Data Structures Prepared by Mahesh MCA

 17
[Link]. IV SEMESTER

Linked List & Single Linked Linear List

A linked list is an ordered collection of finite, homogeneous data elements

called nodes. Unlike arrays, linked lists are dynamic structures as nodes are
created whenever we require. The amount of memory required can be varied
during its use. In Linked Lists, the adjacency is maintained by using links or
pointers. A link or pointer is the address of the subsequent(next/previous)
element in the list. So, we need to maintain both data and link in a node. Thus,
a node consists of two parts Data and [Link] part of a node holds the user's
data and Link part of the node holds the address value of its next/previous
node in the list. Link

DATA Link to the next node

Single Linked List: In single linked list, each node contains only one link
which points to the next node in the list. We maintain a pointer called Headptr
to point the very first node of the list.

In the above example, we have five nodes from N1 to N5. The first node is called
as Head Node and last node is called as Tail Node. First node points to second,
second points to third and so on. Tail Node always points to null which
indicates there no more node in the list. In single-linked list, we can travel only
in direction that is from Head Node to Tail Node. We can move only to the next
node not to the previous node of the list. That is why it is called as one way list.

Operations:

addNewNode (data): This operation adds a new node to the list with the given
data.

delete (index): This operation deletes an existing node from the list at given
index position.

size(): This operation gives the size i.e., how many nodes are there in the list.

insert (index, data):This operation inserts a new node to the list at a given
index position with a given data value.

traversal():This operation gathers data from each node in the list starting from
head to tail node and displays the data.

Data Structures Prepared by Mahesh MCA

 18
[Link]. IV SEMESTER

Define linked list. Explain how to insert and delete an element at the
beginnning of the list.

Linked List is a linear data structure and it is very common data structure
which consists of group of nodes in a sequence which is divided in two parts.

Each node consists of its own data and the address of the next node and forms
a [Link] Lists are used to create trees and graphs.

Insertion: : Insertion is used to add a new data item. A node can be inserted
in various positions.
i. Inserting at the front ( as a first element)
ii. Inserting at end ( as a last element)
iii. Inserting at any position.
Steps for inserting an element in the beginning of a list
1. Create a new node
2. Make the next part of new node point to the first node
3. Make the START pointer point to new node
Algorithm

new_nodenext=START;

START =new_node;

Data Structures Prepared by Mahesh MCA

 19
[Link]. IV SEMESTER

Steps for inserting an element in the end

1. Create a new node
2. Make the next of new node point to NULL
3. Make the previous node point to new node.
Algorithm for Insert a node at the end of a single linked list:

while(pnext!=NULL)
{
p=pnext;
}
pnext=new_node;
new_nodenext=NULL;

Steps for inserting an element in the middle

1. Create a new node
2. Make the next part of new node point to the next of previous node
3. Make the previous node point to new node

Algorithm for Insert a node at the middle of a single linked list:

while(p!=insert_position)
{
P=pnext;
}
store_next=pnext;
pnext=new_node;
new_nodenext=store_next;

Data Structures Prepared by Mahesh MCA

 20
[Link]. IV SEMESTER

Deleting a node from a list: It is used to delete an existing data item from the
given collection of data items. There three ways to delete element.

i. Deleting from the front of the list

ii. Deleting from the end of the list
iii. Deleting from any position in the list

Steps for deleting a node in the beginning

1. Store the node to be deleted in a temporary pointer
2. Make START point to next node in the list
3. Delete the node pointed by temporary pointer

Steps for deleting a node from the middle / end

1. Store the node to be deleted in a temporary pointer
2. Make the previous node‘s next point to the next of the node that is being deleted
3. Delete the node pointed by temporary pointer

Steps for deleting a node from the middle / end

1. Store the node to be deleted in a temporary pointer

2. Make the previous node’s next point to the next of the node that is being deleted
3. Delete the node pointed by temporary pointer

Data Structures Prepared by Mahesh MCA

 21
[Link]. IV SEMESTER

Algorithm for deleting a node in single linked list

node *delete(node *head, char d)

{
node *p, *q;
q=head;
p=headnext;
if(qdata==d) //start node
{
head=p;
delete(q);
}
else //internal node
while(pdata!=d) Last node
{
p=pnext;
q=qnext;
}
if(pnext==NULL)
{
qnext=NULL;
delete(p);
}
else
{
qnext=p—next;
delete (p);
}
return head;
}

Data Structures Prepared by Mahesh MCA

 22
[Link]. IV SEMESTER

Discuss about Double Linked Linear List

A linked list is an ordered collection of finite, homogeneous data elements

called nodes. Unlike arrays, linked lists are dynamic structures as nodes are
created whenever we require. The amount of memory required can be varied
during its use.

In Linked Lists, the adjacency is maintained by using links or pointers. A link

or pointer is the address of the subsequent(next/previous) element in the list.
So, we need to maintain both data and link in a node. Thus, a node consists of
two parts Data and Link. Data part of a node holds the user's data and Link
part of the node holds the address value of its next/previous node in the list.

Double Linked List:

In double linked list, each node contains two links one points to the next node
another points to the previous node in the list. We maintain a pointer called
Headptr to point the very first node of the list.

Example:

In the above example, we have four nodes from N1 to N4. The first node is
called as Head Node and last node is called as Tail Node. First node points to
second, second points to third and so on. The left link of head node and right
link of tail node points to null. It indicates that there is no previous node to
head and no next node to tail node. In double-linked list, we can travel in
either directions that is from Head Node to Tail Node and Tail Node to Head
Node. That is why it is called as two-way list.

Memory Organization Of A Doubly Linked List

Data Structures Prepared by Mahesh MCA

 23
[Link]. IV SEMESTER

Operations:
addNewNode (data):This operation adds a new node to the list with the given
data.
delete (index):This operation deletes an existing node from the list at given
index position.
size():This operation gives the size i.e., how many nodes are there in the list.
insert (index, data):This operation inserts a new node to the list at a given
index position with a given data value.
traversal():This operation gathers data from each node in the list starting from
head to tail node and displays the data.
Define double linked list. Explain how to insert and delete an element at
the end of the list.
In double linked list, each node contains two links one points to the next node
another points to the previous node in the list. We maintain a pointer called
Headptr to point the very first node of the list.
Steps for inserting in the beginning of a doubly linked list
1. Create a new node
2. Make the next part of new node equal to START
3. Make the previous part of new node equal to NULL
4. Make the previous part of the node pointed by START to new node
5. Make START point to new node
Algorithm for insert a node at the start
new_nodenext=head;
headprev=new_node;
new_nodeprev=NULL;
head=new_node;

Steps for inserting an element in the middle of a doubly linked list

1. Create a new node
2. Make the next part of new node equal to next part of the previous node
3. Make the previous part of new node equal to previous part of next node
4. Make the next part of previous node point to new node
5. Make the previous part of next node point to new node

Data Structures Prepared by Mahesh MCA

 24
[Link]. IV SEMESTER

Algorithm for insert internal node.

while(p!=insert_position)
{
p=pnext
}
store_next=pnext
pnext=new_node;
new_nodenext=store_next;
store_nextprev=new_node;

Steps for inserting an element at the end of a doubly linked list

1. Create a new node
2. Make the next part of the new node equal to NULL
3. Make the previous part of the new node equal to TAIL
4. Make the next part of the previous node equal to new node
5. Make TAIL equal to new node
Algorithm:
while(pnext!=NULL)
{
p=pnext;
}
pnext=new_node;
new_nodeprev=p;
new_nodenext=NULL;

Data Structures Prepared by Mahesh MCA

 25
[Link]. IV SEMESTER

Deleting an element from a doubly linked list

Deleting a node from a list is as simple as changing the links. Hence deleting a
node from a list is much faster when compared to arrays. Like insertion the
deletion logic also varies depending on from where in the list we are going to
delete the node.

1. Deletion at beginnning

2. Deletion at middle

3. Deletion at end

Deletion in the beginning of a doubly linked list

1. Make the temporary pointer point to the node to be deleted
2. Make the START point to the next node of START
3. Make the previous of the next node equal to previous of the node to be deleted
4. Delete the node pointed to by temporary pointer.

Algorithm:

p=head;

head=headnext;

headprev=NULL;

delete(p);

Deletion in the middle of a doubly linked list

1. Make the temporary pointer point to the node to be deleted
2. Make the next part of the previous node equal to next of the node to be deleted
3. Make the previous part of the next node equal to previous part of the node to be
deleted
4. Delete the node pointed to by temporary pointer
Algorithm:
While(p!=delete_position)
{

Data Structures Prepared by Mahesh MCA

 26
[Link]. IV SEMESTER

P=pnext;
}
store_next=pnext;
store_prev=pprev;
store_nextprev=store_prev;
store_prevnext=store_next;
delete(p);

Deletion at the end of a doubly linked list

1. Make the temporary pointer point to the node to be deleted

2. Make the next part of the previous node equal to next of the node to be deleted

3. Make the TAIL equal to the previous part of the node to be deleted

4. Delete the node pointed to by temporary pointer.

Algorithm:

store_prev=pprev;

store_prevnext=NULL;

delete(p);

Data Structures Prepared by Mahesh MCA

 27
[Link]. IV SEMESTER

Write a detiled note on Circular Linked List .

A linked list is an ordered collection of finite, homogeneous data elements

called [Link] arrays, linked lists are dynamic structures as nodes are
created whenever we require. The amount of memory required can be varied
during its use. In Linked Lists, the adjacency is maintained by using links or
pointers. A link or pointer is the address of the subsequent(next) element in the
list. So, we need to maintain both data and link in a node. Thus, a node
consists of two parts Data and Link. Data part of a node holds the user's data
and Link part of the node holds the address value of its next/previous node in
the list.

CircularLinked List: A linked list where the last node points the header node
is called the ‗Circular Linked List‘. A circular list doesn't have definite head and
definite tail nodes. Any Node in the list can be chosen as Head and node before
that as Tail. If there are more than one Node in the list, then every Node will
have next Node. If there is only one Node in the list that itself is the head and
tail. The tail Node in the circular list points to the head Node.

Operations:
addNewNode (data):This operation adds a new node to the list with the given data.
delete (index):This operation deletes an existing node from the list at given index
position.
size():This operation gives the size i.e., how many nodes are there in the list.
insert (index, data):This operation inserts a new node to the list at a given index
position with a givendata value.
traversal():This operation gathers data from each node in the list starting from head to
tail node and displays the data.

Data Structures Prepared by Mahesh MCA

 28
[Link]. IV SEMESTER

Differences between single linked list and double linked list

SINGLE LINKED LIST DOUBLE LINKED LIST

[Link] SLL the list will be traversed in 1. In DLL the list will be traversed in
only one way i.e., in forward two ways either in forward (or)
direction. Backward directions.

[Link] SLL the node contains only one 2. In DLL each node contains two Link
link field. fields.

[Link] conceptual view (a logical 3. The conceptual view (a logical

organisation) of SLL is: organization) of a DLL is:

[Link] node contains the address of 4. Every node contains the address of
next node. next node as well as the address of the
previous node.

[Link] node structure of DLL is as

[Link] node structure SLL is as follows:
follows

[Link] SLL the first node address is 6. In DLL the first node address is
stored in a special pointer variable stored in ―left end‖ and last node
―START‖. address is stored in ―right end‖ pointer
variables.

7. Three linear arrays are required to

[Link] linear arrays are required to represent a double linked list in
represent a single linked list in memory.
memory.

Data Structures Prepared by Mahesh MCA

 29
[Link]. IV SEMESTER

UNIT-II
What is stack? Explain its Applications
A Stack is a linear list in which insertions and deletions take place at the same
end. The end through which items are added and deleted is called the Top End.
The other end of the list is called the Bottom End.

 A stack is a last-in-first-out ( LIFO ) structure.

 Insertion operation is referred as ―PUSH‖ and deletion operation is
referred as ―POP‖.
 The most accessible element in the stack is the element at the position
―TOP‖.

We can implement the stack ADT either with array or linked list.

 Stack overflow happens when we try to push one more item onto our stack than
it can actually hold.
 Stack underflow happens when we try to pop (remove) an item from the stack,
when nothing is actually there to remove.
 To use a stack efficiently, we need to check the status of stack as well. For
the same purpose, the following functionality is added to stacks –
o peek() − get the top data element of the stack, without removing it.
o isFull() − check if stack is full.
o isEmpty() − check if stack is empty.
Applications of stack:
 Paranthesis matching: Stacks can be used to find out whether the given
equation is balanced or not. It mainly checks for the matching of left and
right parenthesis in an equation.
Example:
(A+B(x+y)+C is not a valid expression because it miss right paranthesis
(A+B(x+y)+C) is a valid expression
 Convert from infix to postfix: Stacks are used to convert an infix to
postfix expression.

Data Structures Prepared by Mahesh MCA

 30
[Link]. IV SEMESTER

Infix expression: (a+b)*c

Postfix expression : ab+c*
Prefix expression: *+abc
 To evaluate postfix forms: To evaluate postfix expression, stacks can be
used. While evaluating, operands are stored onto a stack and popped
when an operator occurs.
The postfix expression ―2 3 *6 +‖ get executed as ―12‖
 Recusrsion: Recursive functions are implemented using stacks. The
copies of variables at each level of recursion are stored in stack.
Example
Fact(3)=3*fact(2)
= 3*2*Fact(1)
= 3*2*1
= 3*2
=6
 Comuter applications that use undo feature: undo is cancel the
previous action. To rememeber these in LIFO order computer
applications use stack.
 Compilers use stacks in syntax analysis phase to check whether a
particular statement in a program is syntactically correct or not.
 Computers use stack during interrupts and function calls. The
information regarding actual parameters return values, return addresses
and machine status is stored in stack.
 Stacks are used in tree traversal techniques
 Stacks are used in depth first search of a graph.
 Keeping track of function calls: To keep track of function calls, stack
can be used to return to the point where it is called after executing the
function. When a function is called the control transfers to the function
and executes all the statements there. But, to return to the pointer where
it is called a stack is used to remember the address of the calling
statement.

Main()
{
fun();
…………
…………
}
fun()
{
………..

Data Structures Prepared by Mahesh MCA

 31
[Link]. IV SEMESTER

What is stack ? Explain basic operations of stack data structures.

A Stack is a linear list in which insertions and deletions take place at the same
end. The end through which items are added and deleted is called the Top End.
The other end of the list is called the Bottom End.
Basic Operations
Stack operations may involve initializing the stack, using it and then de-
initializing it. Apart from these, a stack is used for the following two primary
operations.
push( ) − Pushing (storing) an element on the stack.

pop( ) − Removing (accessing) an element from the stack.

When data is PUSHed onto stack, To use a stack efficiently, we need to check
the status of stack as well. For the same purpose, the following functionality is
added to stacks.

peek( ) − get the top data element of the stack, without removing it.

isFull( ) − check if stack is full.

isEmpty( ) − check if stack is empty.

Stack is said to be in Overflow state when it is completely full and is said to be

in Underflow state if it is completely empty.
Push Operation
The process of putting a new data element onto stack is known as a Push
Operation. Push operation involves a series of steps.
Step 1 − Checks if the stack is full.
Step 2 − If the stack is full, produces an error and exit.
Step 3 − If the stack is not full, increments top to point next empty space.
Step 4 − Adds data element to the stack location, where top is pointing.
Step 5 − Returns success.
Algorithm for Push operation
1. Begin procedure push: stack, data

2. if stack is full return null end if

3. top = top + 1

4. stack[top] = data

5. end procedure

Data Structures Prepared by Mahesh MCA

 32
[Link]. IV SEMESTER

Pop Operation
Accessing the content while removing it from the stack, is known as a POP
Operation. A POP operation may involve the following steps.
Step 1 − Checks if the stack is empty.
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is
pointing.
Step 4 − Decreases the value of top by 1.
Step 5 − Returns success.
Algorithm for Pop operation
1. begin procedure pop: stack
2. if stack is empty return null
3. end if 4. data = stack[top]
5. top = top - 1
6. return data
7. end procedure

Peek( ):
This operation returns the most accessible element from stack.

begin procedure peek

Data Structures Prepared by Mahesh MCA

 33
[Link]. IV SEMESTER

return stack[top]

end procedure

isFull( ):
This operation is performed to know whether the stack is full or not. If the TOP
value reaches to MAXSIZE then the stack is full.

begin procedure isfull

if top equals to MAXSIZE
return true
else
return false
endif
end procedure
isEmpty( )
This operation is used to check whether the stack is empty or not begin
procedure isempty.
if top less than 1
return true
else
return false
endif
end procedure

What is stack? Discuss about aray and linked representation of a stack.

A Stack is a linear list in which insertions and deletions take place at the same
end. The end through which items are added and deleted is called the Top End.
The other end of the list is called the Bottom [Link] two basic operations
associated with stacks are:
Push: is the term used to insert an element into a stack.
Pop: is the term used to delete an element from a stack.
A stack may be represented in the memory in various ways. Mainly there are
two ways. They are:
1. Using one dimensional arrays(Static Implementation)
2. Using linked lists(Dynamic Implementation)
Stack Representation using Arrays :
A Stack data structure can be represented using arrays. We perform stack
operations Push and POP by maintaining the top value to point to the topmost
element position of the stack.

Data Structures Prepared by Mahesh MCA

 34
[Link]. IV SEMESTER

Abstract Class :

AbstractDataType Stack
{
Instances
Linear list of elements: one end is called the bottom the other is the top.
Operations
isEmpty() : Return True if stack is empty, return False otherwise.
isFull() : Return True if stack is full, return False otherwise
push(x) : Add element x to the stack
pop(x) : Delete top element from stack and put it in x.
}

Operations:
push(x) : Adding items to the stack is called as Push operation. Here x is the
data item that is being added onto the stack.

Data Structures Prepared by Mahesh MCA

 35
[Link]. IV SEMESTER

pop(x) : Deleting items from the stack is called as Pop operation. Here x is the
data item that is being deleted from the stack.
isFull( ) :This function verifies whether the stack is full or not. If stack is full, it
returns true, otherwise return false.
isEmpty(): This function verifies whether the stack is empty or not. If stack is
empty, it returns true, otherwise it returns false.
Algorithm
Stack Operations: Basically, there are two operations performed on the
stack.
Push: Push is the term used to insert the element on the top of stack.
Pop: Pop is the term used to delete the elements from top of the stack.
Algorithm: push(s, top, x):[This algorithm inserts the elements.]
Step: 1 [check for the stack over flow]
If (top > = max-1) then write (―stack over flow‖)
Return;
Step: 2 [increment top by 1]
top top+1;
Step: 3 [insert element]
s[top] x;
Step: 4 [finished]
Return;
Algorithm pop(s, top): [this algorithm deletes the top element from the stack]
Step: 1 [check for the stack under flow]
if (top= = -1) then write (―stack underflow‖)
Return;
Step: 2 [assign top element to x]
X s[top];
Step: 3 [decrement top by 1]
top top-1;
Step: 4 [finished]
Return;
Algorithm isEmpty(s, top): [this algorithm checks the stack is empty ]
Step: 1 [check for the stack is empty()]
if (top= = -1) then write (―stack Empty‖)
Step: 2.[finished]
Return;
Algorithm: isFull(s, top):[This algorithm checks the stack is full]
Step: 1 [check for the stack is full]
If (top > = max-1) then write (―stack is Full‖)
Step: 2 [finished]
Return;
Stack Representation using Linked List:
Array representation of stacks is very easy, but it allows only fixed sized stacks.
In several applications, the size of the stack may vary during program
execution. In such cases we may use linked list. A single linked list structure is

Data Structures Prepared by Mahesh MCA

 36
[Link]. IV SEMESTER

sufficient to represent to any stack. Here data field is users data and link field
is as usual point to next item.
We can use either single linked or double linked list to represent a stack data
structure. But it is easy to use single linked list to represent a stack data
structure.

Example :

In the linked list representation, first node on the list is the current item that is
the item at the top of the stack and the last node is the node containing bottom
most item. So PUSH operation will perform at the front and POP operation will
perform at front. SIZE of the stack is not important here because dynamic
representation.

The implementation of isFull() method is not necessary because the only way to
know whether we can add an element on to the stack or not is to see whether
enough space exists to create a node of type Node. This check can be done by
invoking new.
Abstraction of Stack:
Data Objects:
Node :-consisting of two parts data and address.
headptr :-always points to the address of first node in the list
next :- used to store next node address
Methods :
isEmpty(): This method verifies that the stack is empty or not. If the stack is
empty it returns true, otherwise it returns false.
push(x): This method adds a data item x onto the stack. If the operation
executed successfully it returns true, otherwise it returns false.

Data Structures Prepared by Mahesh MCA

 37
[Link]. IV SEMESTER

pop(x): This method pops a data item from the stack and places it in x. If the
operation executed successfully it returns true, otherwise it returns
false.
peek(): To access the top element of the stack without removing it.

Algorithms
Algorithm: push_LL (s, top, x):[This algorithm inserts the elements.]
Step: 1[Create new node ]
New=Getnew(Node);
Step: 2 [inserting Values]
New Data=Item
Step3: [palcing reference]
New link=top
Top=new
Step: 4 [top is assigns to stack head]
Stack_Headlink=top
Step:5 [Finish]
Return;
Algorithm pop_LL(s, top): [this algorithm deletes the top element from the
stack]
Step: 1 [check for the stack under flow]
PTR= Stack_Headlink;
if (PTR=NULL) then write (―stack underflow‖)
Return;
Step: 2 [assign top element to x]
X PTR[top]; [Display x]
Step: 3 [Assign top to next node]
top = ptr link;
Step: 4[Assign head_ptr to top]
Stack_Head=top;
Step: 5 [finished]
Return;
Algorithm isEmpty(s, top): [this algorithm checks the stack is empty ]
Step: 1 [check for the stack is empty()]
if (top= = null) then write (―stack Empty‖)
Step: 2.[finished]
Return;

Data Structures Prepared by Mahesh MCA

 38
[Link]. IV SEMESTER

What is an arithmetic expression? Explain their notations?

An algebraic expression is a legal combination of operators and operands.
Operand may be a variable like x, y, z or a constant like 5, 4, 6 etc. Operator is
a symbol which signifies a mathematical or logical operation between the
operands. Examples of familiar operators include +, -, *, /, ^ etc. An algebraic
expression can be represented using three different notations. They are infix,
postfix and prefix notations:

Infix: It is the form of an arithmetic expression in which we fix (place) the

arithmetic operator in between the two operands.

Example: (A + B) * (C - D)

Prefix: It is the form of an arithmetic notation in which we fix (place) the

arithmetic operator before (pre) its two operands. The prefix notation is called as
polish notation

Example: * + A B – C D

Postfix: It is the form of an arithmetic expression in which we fix (place) the

arithmetic operator after (post) its two operands. The postfix notation is called
as suffix notation and is also referred to reverse polish notation.

Example: A B + C D - *

The three important features of postfix expression are:

 The operands maintain the same order as in the equivalent infix

expression.
 The parentheses are not needed to designate the expression
unambiguously.
 While evaluating the postfix expression the priority of the operators is no
longer relevant.

Data Structures Prepared by Mahesh MCA

 39
[Link]. IV SEMESTER

Convert the following infix expression A + B * C – D / E * H into its equivalent

postfix expression.

Convert ((A – (B + C)) * D) ↑ (E + F) infix expression to postfix form:

Data Structures Prepared by Mahesh MCA

 40
[Link]. IV SEMESTER

What is a Queue ? Explain its operations?

A queue is a leaner list, which has two ends, where items are inserted at one end
called the rear and deleted at the other end called the front. Another name for a queue
is a ―FIFO‖ or ―First-in-first-out‖ list. Unlike stacks, a queue is open at both its ends.
One end is always used to insert data (enqueue) and the other is used to remove data
(dequeue). We can implement the queue by using Arrays and linked list.

Arrays

Linked list representation

Queue operations :
Enqueue:
The process of adding an element into the queue is known as Enqueue. The
following steps are perform queue operations.

Step 1 − Check if the queue is full.

Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − Return success
Procedure enqueue(data)
if queue is full
return overflow
end if
rear = rear + 1
queue[rear] = data
return true
End procedure
Dequeue Operation

Data Structures Prepared by Mahesh MCA

 41
[Link]. IV SEMESTER

Accessing data from the queue is a process of two tasks − access the data
where front is pointing and remove the data after access. The following steps
are taken to perform dequeue operation:
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front = front + 1
return true
end procedure
peek( )
This function helps to see the data at the front of the queue. The algorithm of
peek() function is as follows
begin procedure peek
return queue[front]
end procedure
isFull:
As we are using single dimension array to implement queue, we just check for
the rear pointer to reach at MAXSIZE to determine that the queue is full.
Begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
end if
end procedure
Applications of Queue:
Printing using the computer: When several documents are to be printed, the
printer prints the documents in FIFO method only. i.e. to keep track of
documents in FIFO order, a queue is used.
Reservation system: Reservations such as air ticket or railway reservation
systems, use to issue reservations on first come first serve basis i.e. FIFO
method.

Data Structures Prepared by Mahesh MCA

 42
[Link]. IV SEMESTER

Computer networks: Computer networks use queue to give access from server
to several clients, who are connected to the server in FIFO method.

BFS: Breadth first search uses a queue data structure to find an element from
a graph.

What is a queue? Explain types of queue.

 Queue is a Linear Data Structure that works on First-in-First-Out (FIFO)

principle.
 It has two pointers, ―Front‖ that point to the beginning of the queue and
―Rear‖ that points to the end of the queue.
 The ―Front‖ and ―Rear‖ pointers are manipulated constantly to always
point to the beginning and end of queue.

Different types of queues:

1. Simple queue
2. Circular queue
3. Priority queue
4. Dequeue (Double ended queue)
[Link] or linear queue
 Simple or standard Queue is a linear data structure in which the
insertion and deletion operations are performed at two different ends.
 In a simple queue data structure, the insertion operation is performed at
a position which is known as 'rear' and the deletion operation is
performed at a position which is known as 'front'.

2. Circular queue:
 Circular queue is a linear data structure. It follows FIFO principle. In
circular queue the last node is connected back to the first node to make
a circle.
 Elements are added at the rear end and the elements are deleted at front
end of the queue
 It is also called as ―Ring buffer‖.

Data Structures Prepared by Mahesh MCA

 43
[Link]. IV SEMESTER

Applications of circular queue:

Adding large integers: large integers can be added very easily using circular
queues. Here the right most digit is placed in the front node and left most digit
is placed in rear node.

Memory management: The unused memory locations in the case of ordinary

queues can be utilised in circular queues.

Computer controlled traffic system: In computer controlled traffic system,

circular queues are used to switch on the traffic lights one by one repeatedly as
per the time set.

3. Priority queue:
A priority queue is a queue that contains items that have some preset
[Link] an element ha to be removed from a priority queue, the item with
the highest pririty is removed first.

 An element of higher priority is processed before any element of lower

priority.
 Two elements with same priority are processed according to the order in
which they were added to the queue.

4. Double ended Queue

Double Ended Queue is also a Queue data structure in which the insertion and
deletion operations are performed at both the ends (front and rear). That
means, we can insert at both front and rear positions and can delete from both
front and rear positions.

Double Ended Queue can be represented in TWO ways, those are as follows...

 Input Restricted Double Ended Queue

 Output Restricted Double Ended Queue

Input Restricted Double Ended Queue

In input restricted double ended queue, the insertion operation is performed at
only one end and deletion operation is performed at both the ends.

Data Structures Prepared by Mahesh MCA

 44
[Link]. IV SEMESTER

Output Restricted Double Ended Queue

In output restricted double ended queue, the deletion operation is performed at
only one end and insertion operation is performed at both the ends.

What is a circular queue ? explain its operations ?

 In a standard queue data structure re-buffering problem occurs for each

dequeue operation. To solve this problem by joining the front and rear ends
of a queue to make the queue as a circular queue
 Circular queue is a linear data structure. It follows FIFO principle. In
circular queue the last node is connected back to the first node to make a
circle.
 Elements are added at the rear end and the elements are deleted at front
end of the queue
 It is also called as ―Ring buffer‖.

Limitations:
The drawback of circular queue is , difficult to distinguished the full and empty cases.
It is also known as boundary case problem.

Circular Queue can be created in three ways they are

 Using single linked list
 Using double linked list
 Using arrays

Data Structures Prepared by Mahesh MCA

 45
[Link]. IV SEMESTER

Algorithm for Enqueue operation using array

Step 1: start
Step2: if (front == (rear+1)%max) Print error ―circular queue overflow ―
Step3: else
{ rear = (rear+1)%max
Q[rear] = element;
If (front == -1 ) f = 0;
}
Step 4 :stop
Algorithm for Dequeue operation using array
Step 1: start
Step2: if ((front == rear) && (rear == -1)) print error “circular queue underflow “
Step3: else
{ element = Q[front]
if (front == rear)
front=rear = -1
else
front = (front + 1) % max }
Step 4: stop

What is queue ? Explain Array and linked representation of Queues.

 Queue is a Linear Data Structure that works on First-in-First-Out (FIFO)

principle.
 It has two pointers, ―Front‖ that point to the beginning of the queue and
―Rear‖ that points to the end of the queue.
 The ―Front‖ and ―Rear‖ pointers are manipulated constantly to always
point to the beginning and end of queue.

There are two ways to represent a queue in memory.

1. Using an array
2. Using a linked list

Data Structures Prepared by Mahesh MCA

 46
[Link]. IV SEMESTER

The first kind of representation uses a one dimensional array and it is a better
a choice where a queue of fixed size is required. The other representation uses
double linked list and provides queue whose size can vary during processing.
Represntation of Queue using an array:
A one dimensional array, say q[1…N], can beused to represent a queue.

In the above representation, two pointers namely FRONT and REAR are used to indicate
the two ends of the queue. For the insertion of the next element, the pointer REAR will be
the consultant and for the pointer FRONT will be the consultant. Three states of a queue
with this representation are given below.

Queue is empty:
FRONT =0,
REAR=0
Queue is full
REAR=N
FRONT=1
Queue contains elements >=1
Number of elelnts = REAR-FRONT+1
Representation of a Queue using linked list:
A Linear Queue can be represented as a Linked List. For this we need two
variables front and rear to keep track of the two ends of the Queue. There are
two possibilities for binding these two variables to the ends of the Linked list.
The nodes can be linked from front to rear or rear to front. But linking the
nodes from front to rear is more efficient for deletions.
Queue is empty
FRONT =REAR=HEADER
HEADERRLINK=NULL
QUEUE contains at least one element
HEADER RLINK ≠ NULL

Data Structures Prepared by Mahesh MCA

 47
[Link]. IV SEMESTER

UNIT –III
TREES

Write a short notes on Trees.

Tree
A tree is a nonlinear data structure and is generally defined as a nonempty finite set of elements,
called nodes such that:
 Tree contains a distinguished node called root of the tree.
 The remaining elements of tree form an ordered collection of zero or more disjoint
subsets called sub tree.

Path: The sequence of lines which connect node to node of tree is called path.
Root: The node at the top of a tree is called the root. There is only one root in a tree.
Parent: Any node (except root) that has at least one node as a child node, is called parent.
Child: All the nodes except root are child nodes.
Leaf: A node that has no child node can be called leaf node.
Sub-tree: A sub-tree constitutes of a node and all its decendants.
Visiting: Visiting means reaching a particular node to either print it or perform some operation
on it.
Traversing: traversing means to visit all the nodes in some specified order.
Level: The level refers to number generations from the root of a tree ( it is also called depth of
atree)
Keys: Key refers to a value ( data field) of a node.
Depth of a node we will call the length of the path from the root to certain node.
Height of tree: is the maximum depth of all its nodes.
Degree of node we call the number of direct children of the given node.
Branching factor is the maximum of the degrees of all nodes in the tree.

Data Structures Prepared by Mahesh MCA

 48
[Link]. IV SEMESTER

What is binary Tree? Write the properties and applications of binary Trees. ?

A binary tree is defined as a finite set of elements, called nodes, such that:

 Tree is empty (called the null tree or empty tree) or

 Tree contains a distinguished node called root node, and the remaining
nodes form an ordered pair of disjoint binary trees.

In the above tree ―A‖ is the root node and ―B‖ and ―C‖ are called subtrees. B
and C are left and right successor of A. The node A is called parent node and B
and C are called children. All lower level nodes are called descendants and
upper level nodes are called ancestors of their descendants. The line drawn
between parent and child is called an edge or arc whereas the line(s) between
and ancestor and descendant is called path. A node without any children is
called a terminal or leaf node and all others are called nonterminal or non-leaf
node. A path ending with a leaf is called a branch.
Properties of binary trees
 The depth of a binary tree containing N nodes is at most N-1.
 The depth of a binary tree containing N leaves is at least [log2(N)].
 A binary tree of depth d has at most 2d leaves.
 The number of nodes in a binary tree of depth d is at most 2d-1-1.
 The average depth of a binary tree containing N nodes is O( 𝑁 )
 The maximum number of nodes on level i of a binary tree is 2i-1, i ≥1
 The maximum number of nodes in a binary tree of depth k is 2k – 1, k ≥1
 If a complete binary tree with n nodes (depth = ˪ log2n +1˩ ) is represented
sequentially, then for any node with index i, 1 ≤ i ≤ n, we have:

Data Structures Prepared by Mahesh MCA

 49
[Link]. IV SEMESTER

Binary Tree Applications

 Binary Search Tree Used in many search applications where data is

constantly entering/leaving, such as the map and set objects in many
languages' libraries.
 Binary Space Partition Used in almost every 3D video game to determine
what objects need to be rendered.
 Binary Tries Used in almost every high-bandwidth router for storing router-
tables.
 Hash Trees Used in p2p programs and specialized image-signatures in
which a hash needs to be verified, but the whole file is not available.
 Heaps Used in implementing efficient priority-queues, which in turn are
used for scheduling processes in many operating systems, also used in
heap-sort.
 Huffman Coding Tree (Chip Uni) Used in compression algorithms, such as
those used by the .jpeg and .mp3 file-formats
 GGM Trees Used in cryptographic applications to generate a tree of pseudo-
random numbers.
 Syntax Tree Constructed by compilers and (implicitly) calculators to parse
expressions. (7+3) *(5-2) can be represented by

 Heap is a tree data structure which is implemented using arrays and used
to implement priority queues.
 B-Tree and B+ Tree : They are used to implement indexing in databases.
 Syntax Tree: Used in Compilers.
 K-D Tree: A space partitioning tree used to organize points in K dimensional
space.
 Trie : Used to implement dictionaries with prefix lookup.
 Suffix Tree : For quick pattern searching in a fixed text.
 One reason to use trees might be because you want to store information
that naturally forms a hierarchy. For example, the file system on a
computer: file system.

Data Structures Prepared by Mahesh MCA

 50
[Link]. IV SEMESTER

Explain Binary Tree Types?

Complete Binary Tree:

A binary tree is said to be complete if all its level except possibly
the last, have maximum number of possible nodes, and if all the
nodes at the last level appear as far left as possible.

Full binary tree:

A binary tree said to be full if all its level have maximum
number of possible node.

Extended Binary Tree (Strictly Binary Tree or 2-tree):

A binary tree is said to be Extended binary tree if each node
has either 0 or 2 children. In this case the leaf nodes are
called external nodes and the node with two children are
called internal nodes.

Skewed Tree:
A tree is called Skew if all the nodes of a tree are attached to one
side only. i.e A left skew will not have any right children in its each
node and right skew will not have any left child in its each node.

Data Structures Prepared by Mahesh MCA

 51
[Link]. IV SEMESTER

Explain Binary tree representation?

Array Representation
The numbering scheme used in it suggests out first representation of a binary
tree in memory. Since the nodes are numbered from 1 to n, we can use a one-
dimensional array to store the nodes. (We do not use the 0th position of the
array.) Using the node numbering easily determine the locations of the parent,
left child, and right child of any node, i, in the binary tree.

Advantages:
This method benefits from more compact storage and better locality of
reference, particularly during a preorder traversal.

Limitations:
 Wastage of space for some types of binary tree.
 Insertion and deletions require potential changes in the array.

Linked Representation
We can easily overcome the problems arise due to array representation by
using a linked representation. Each node has three fields, left_child, data, and
right_child as two pictures show the node representation of the binary tree
below:

Data Structures Prepared by Mahesh MCA

 52
[Link]. IV SEMESTER

Advantages:
 Insertion and deletion involve no data movement and no movement of
nodes except the rearrangement of pointers.

Limitations:
 Given a node structure, it is difficult to determine its parent node.
 Memory spaces are wasted for storing NULL pointers for the nodes,
which have no subtrees.

Explain various methods of traversing of a binary tree with examples:

There are many operations that we can perform on tree, but one that arises
frequently is traversing a tree, that is, visiting each node in the tree exactly
once. A full traversal produces a linear order for the information in a tree.

Binary Tree Traversals Types

 Inorder Traversal (Left, Root, Right)

 Preorder Traversal (Root, Left, Right)
 Postorder Traversal (Left, Right, Root)
 Level Order Traversal (Top to Bottom, Left to Right)

Inorder Traversal:

In the case of inorder traversal, the root of each subtree is visited after its left
subtree has been traversed but before the traversal of its right subtree begins.
The steps for traversing a binary tree in inorder traversal are:

1. Visit the left subtree, using inorder.

2. Visit the root.

3. Visit the right subtree, using inorder.

The algorithm for inorder traversal is as follows:

void inorder(node root)
{
if(root != NULL)
{
inorder(root . lchild);
print root . data;
inorder(root . rchild);
}
}

Data Structures Prepared by Mahesh MCA

 53
[Link]. IV SEMESTER

Preorder Traversal:
In a preorder traversal, each root node is visited before its left and right
subtrees are traversed. Preorder search is also called backtracking. The steps
for traversing a binary tree in preorder traversal are:
1. Visit the root.
2. Visit the left subtree, using preorder.
3. Visit the right subtree, using preorder.
Algorithm for preorder traversal
void preorder(node root)
{
if( root != NULL )
{
print root . data; preorder (root . lchild);
preorder (root . rchild);
}
}

Postorder Traversal:
In a postorder traversal, each root is visited after its left and right subtrees
have been traversed. The steps for traversing a binary tree in postorder
traversal are:
Visit the left subtree, using postorder.
Visit the right subtree, using postorder
Visit the root.
Algorithm for postorder traversal
void postorder(node root)
{
if( root != NULL )
{
postorder (root . lchild);
postorder (root . rchild);
print (root . data);
}
}

Level order Traversal:

In a level order traversal, the nodes are visited level by level starting from the
root, and going from left to right. The level order traversal requires a queue
data structure. So, it is not possible to develop a recursive procedure to

Data Structures Prepared by Mahesh MCA

 54
[Link]. IV SEMESTER

traverse the binary tree in level order. This is nothing but a breadth first search
technique.

Algorithm for level order traversal

void levelorder( )
{
int j; for(j = 0; j < ctr; j++)
{
if(tree[j] != NULL) print tree[j] . data;
}
}

Data Structures Prepared by Mahesh MCA

 55
[Link]. IV SEMESTER

Explain various operations on BST with an example.

A binary search tree is a binary tree. It may be empty. If it is not empty then it
satisfies the following properties:
 Every element has a key and no two elements have the same key.
 The keys in the left subtree are smaller than the key in the root.
 The keys in the right subtree are larger than the key in the root.
 The left and right subtrees are also binary search trees.

BST Operations
The basic operations that can be performed on a binary search tree data
structure, are the following
1. Insert node
2. Searching
3. Delete a node
4. Traversal
Insert Operation
The very first insertion creates the tree. Afterwards, whenever an element is to
be inserted, first locate its proper location. Start searching from the root node,
then if the data is less than the key value, search for the empty location in the
left subtree and insert the data. Otherwise, search for the empty location in the
right subtree and insert the data.
Algorithm:
Step1: Compare item with the root( N) of the tree as
If ( item<N )proceed to the left child of N.
If( item>N) proceed to the right child of N
Step2: Repeat step1 until one of the following occurs.
We meet a node N such that item = N. in this case the search is successful.
We meet an empty sub tree, which indicates the search is unsuccessful. Insert item
in place of the empty sub tree.
Step 3: exit
Search Operation
Whenever an element is to be searched, start searching from the root node,
then if the data is less than the key value, search for the element in the left
subtree. Otherwise, search for the element in the right subtree. Follow the
same algorithm for each node.

Data Structures Prepared by Mahesh MCA

 56
[Link]. IV SEMESTER

Algorithm
If [Link] is equal to [Link]
return root
else
while data not found
If data is greater than [Link]
goto right subtree
else
goto left subtree
If data found
return node
endwhile
return data not found
end if
Binary Search Tree Traversal
Traversal is a process to visit all the nodes of a tree and may print their values
too. Because, all nodes are connected via edges (links) we always start from the
root (head) node. That is, we cannot randomly access a node in a tree. There
are three ways which we use to traverse a tree
 In-order Traversal
 Pre-order Traversal
 Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree
or to print all the values it contains.
In-order Traversal
In this traversal method, the left subtree is visited first, then the root and later
the right sub-tree. We should always remember that every node may represent
a subtree itself.

If a binary tree is traversed in-order, the output will

produce sorted key values in an ascending order.
We start from A, and following in-order traversal, we
move to its left subtree B. B is also traversed in-order.
The process goes on until all the nodes are visited. The
output of inorder traversal of this tree will be −
D → B → E → A → F → C → G.
Pre-order Traversal
In this traversal method, the root node is visited first, then
the left subtree and finally the right subtree. We start
from A, and following pre-order traversal, we first
visit Aitself and then move to its left subtree B. B is also
traversed pre-order. The process goes on until all the
nodes are visited. The output of pre-order traversal of this
tree will be −
A→B→D→E→C→F→G

Data Structures Prepared by Mahesh MCA

 57
[Link]. IV SEMESTER

Post-order Traversal
In this traversal method, the root node is visited last,
hence the name. First we traverse the left subtree, then
the right subtree and finally the root node.
We start from A, and following pre-order traversal, we
first visit the left subtree B. B is also traversed post-
order. The process goes on until all the nodes are visited.
The output of post-order traversal of this tree will be −
D→E→B→F→G→C→A
DELETING A NODE
Removing is the most complicated operation from the basic binary search Tree
operations. After it the tree must keep its order.

The firsrt step before we remove an element from the tree is to find it. We have
three cases.

Deleting a node with no children

Deleting a node with one sub tree
Deleting a node with two sub trees

1. if the tree ‗null‘ print the message accordingly.

2. First, search for that starting from the root. i.e. move to left the element is
less than parent or right till the elementis encountered or empty node is
encountered.

3. if empty node is encountered, print no element.

4. otherwise, if the node has no children, delete it directly.

5. if the node has only left child, parent node must be linked to its left before
deleting the node.

6. if the node has only right child, parent node must be linked to its right
before deleting the node.

7. if a node to be deleted has two children, find minimum value in its right sub
tree. Replace the element to be deleted with the minimum element and repeat
the same process to delete the node containing minimum element.

Data Structures Prepared by Mahesh MCA

 58
[Link]. IV SEMESTER

UNIT – IV

GRAPHS

What is Graph? Explain terminology of Graphs.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Generally, a graph G is represented as G = (V, E), where V is set of vertices and

E is set of edges.
G=(V,E)
V(G)={v0,v1,v2…..vn-1}
E(G)={e1,e2….en)
Example
The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = (V, E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}

Graph Terminology (or ) Graph Components

We use the following terms in graph data Components
Vertex
A individual data element of a graph is called as Vertex. Vertex is also known
as node. In above example graph, A, B, C, D & E are known as vertices.
Edge
An edge is a connecting link between two vertices. Edge is also known as Arc.
An edge is represented as (startingVertex, ending Vertex).
Example: In the above graph, the link between vertices A and B is represented
as (A, B). In above example graph, there are 7 edges (i.e., (A, B), (A, C), (A, D),
(B,D), (B,E), (C,D), (D,E)).
Undirected Graph
A graph with only undirected edges is said to be undirected graph.

Data Structures Prepared by Mahesh MCA

 59
[Link]. IV SEMESTER

Directed Graph
A graph with only directed edges is said to be directed graph.

Degree
Total number of edges connected to a vertex is said to be degree of that vertex.
In-degree
Total number of incoming edges connected to a vertex is said to be in-degree of
that vertex.
Out-degree
Total number of outgoing edges connected to a vertex is said to be out-degree of
that vertex.
Path
A path is a sequence of alternating vertices and edges that starts at a vertex
and ends at a vertex such that each edge is incident to its predecessor and
successor vertex.
Adjacent
If there is an edge between vertices A and B then both A and B are said to be
adjacent. In other words, Two vertices A and B are said to be adjacent if there
is an edge whose end vertices are A and B.
Mixed Graph
A graph with undirected and directed edges is said to be mixed graph.
Origin
If an edge is directed, its first endpoint is said to be origin of it.
Destination
If an edge is directed, its first endpoint is said to be origin of it and the other
endpoint is said to be the destination of the edge.
Cyclic graph:- A graph that has cycles is called cyclic graph.
Acyclic graph:- a graph that has no cycles is called an acyclic graph.
Isolated graph:- if a node has no edges connected with any other node then it‘s
degree will be o and it will be called isolated graph.
Self-loop
An edge (undirected or directed) is a self-loop if its two endpoints coincide.
Multigraph:- a graph which has loop or multiple edges can be described as
multigraph.

Data Structures Prepared by Mahesh MCA

 60
[Link]. IV SEMESTER

Explain different types of Graphs.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Generally, a graph G is represented as G = (V, E), where V is set of vertices and

E is set of edges.
G=(V,E)
Types of Graphs:

1. Directed graph

2. Undirected Graph

3. Weighted Graph

Directed Graph:
A directed graph G is defined as an ordered pair (V, E) where, V is a set of
vertices and the ordered pairs in E are called edges on V. A directed graph can
be represented geometrically as a set of marked points (called vertices) V with a
set of arrows (called edges) E between pairs of points (or vertex or nodes) so
that there is at most one arrow from one vertex to another vertex. For example,
in the figure shows a directed graph, where G = {a, b, c, d }, {(a, b), (a, d), (d, b),
(d, d), (c, c)}

An edge (a, b), in said to the incident with the vertices it joints, i.e., a, b. We
can also say that the edge (a, b) is incident from a to b. The vertex a is called
the initial vertex and the vertex b is called the terminal vertex of the edge (a, b).
If an edge that is incident from and into the same vertex, say (d, d) of (c, c) in
the above Fig , is called a loop.

Undirected Graph:
An undirected graph G is defined abstractly as an ordered pair (V, E), where V
is a set of vertices and the E is a set at edges. An undirected graph can be

Data Structures Prepared by Mahesh MCA

 61
[Link]. IV SEMESTER

represented geometrically as a set of marked points (called vertices) V with a

set at lines (called edges) E between the points. An undirected graph G is
shown in Fig.

Weighted Graph:
A graph G is said to be weighted graph if every edge and/or vertices in the
graph is assigned with some weight or value. A weighted graph can be defined
as G = (V, E, We, Wv) where V is the set of vertices, E is the set at edges and
We is a weights of the edges whose domain is E and Wv is a weight to the
vertices whose domain is V. Consider a graph In Fig, which shows the distance
in km between four metropolitan cities in India. Here V = {N, K, M, C,} E = {(N,
K), (N,M,), (M,K), (M,C), (K,C)} We = {55,47, 39, 27, 113} and Wv = {N, K, M, C}
The weight at the vertices is not necessary to maintain have become the set Wv
and V are same.

Complete Graph:
A graph G is said to complete (or fully connected or strongly connected) if there
is a path from every vertex to every other vertex. Let a and b are two vertices in
the directed graph, then it is a complete graph if there is a path from a to b as
well as a path from b to a. A complete graph with n vertices will have n (n –
1)/2 edges.

Data Structures Prepared by Mahesh MCA

 62
[Link]. IV SEMESTER

Write a short note on path of a graph.

Path and Circuit:

In a directed graph, a path is a sequence of edges (e1, e2, e3, ...... en) such that
the edges are connected with each other (i.e., terminal vertex en coincides with
the initial vertex e1). A path is said to be elementary if it does not meet the
same vertex twice. A path is said to be simple if it does not meet the same
edges twice. Consider a graph in Fig.

Where (e1, e2, d3, e4, e5) is a path; (e1, e3, e4, e5, e12, e9, e11, e6, e7, e8,
e11) is a path but not a simple one; (e1, e3, e4, e5, e6, e7, e8, e11, e12) is a
simple path but not elementary one; (e1, e3, e4, e5, e6, e7, e8) is an elementary
path.

A circuit is a path (e1, e2, .... en) in which terminal vertex of en coincides with
initial vertex of e1. A circuit is said to be simple if it does not include (or visit)
the same edge twice. A circuit is said to be elementary if it does not visit the
same vertex twice. In Fig. (e1, e3, e4, e5, e12, e9, e10) is a simple circuit but
not a elementary one; (e1, e3, e4, e5, e6, e7, e8, e10) is an elementary circuit.

Data Structures Prepared by Mahesh MCA

 63
[Link]. IV SEMESTER

Write the Applications of Graphs

Since they are powerful abstractions, graphs can be very important in modeling
data.

Social network graphs: Graphs that represent who knows whom, who
communicates with whom or other relationships in social structures

Transportation networks: Graph networks are used by many map programs

such as Google maps, Bing maps and now Apple IOS 6 maps to find the best
routes between locations.

Utility graphs. The power grid, the Internet, and the water network are all
examples of graphs where vertices represent connection points, and edges the
wires or pipes between them.

Document link graphs. The best known example is the link graph of the web,
where each web page is a vertex, and each hyperlink a directed edge.

Network packet traffic graphs. Vertices are IP (Internet protocol) addresses

and edges are the packets that flow between them.

Robot planning. Vertices represent states the robot can be in and the edges
the possible transitions between the states.

Neural networks. Vertices represent neurons and edges the synapses between
them. Neural networks are used to understand how our brain works and how
connections change when we learn.

Semantic networks. Vertices represent words or concepts and edges represent

the relationships among the words or concepts.

Graphs in compilers. Graphs are used extensively in compilers. They can be

used for type inference, for so called data flow analysis, register allocation and
many other purposes.

Data Structures Prepared by Mahesh MCA

 64
[Link]. IV SEMESTER

Explain squential representation of a graph with example.

Graph is a non linear data structure which contains a set of points known as
nodes (or vertices) and set of links known as edges (or Arcs) which connects the
vertices.

Graph data structure is represented using following representations:

Adjacency Matrix( sequential )
Adjacency List(linked)
Adjacency Matrix(Sequential Representation)

In this representation, graph can be represented using a matrix of size total

number of vertices by total number of vertices. Adjacency matrix is the matrix,
which keeps the information of adjacency nodes. The adjacency matrix A of a
graph G=(V,E) with n nodes is an MXN matrix such that,
A[i][j]= { 1 If there is an edge from node i to node j
0 if there is no edge from node I to node j }

Example:
For a Undirected graph representation the adjacency matrix representation is

For a Directed graph representation the adjacency matrix representation is

That means if a graph with 4 vertices can be represented using a matrix of 4X4
class. In this matrix, rows and columns both represent vertices. This matrix is
filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to
column vertex and 0 represents there is no edge from row vertex to column
vertex.

Data Structures Prepared by Mahesh MCA

 65
[Link]. IV SEMESTER

Explain Linked representation of a graph with example.

In adjacency list representation of graph, we will maintain two lists. First list
will keep track of an nodes in the graph and second list will maintain a list of
adjacent nodes for each node. It is more efficiency of than adjacency matrix.
Example: Consider the following directed graph representation implemented
using linked list

Explain various graph traversals with examples.

Many application of graph requires a structured system to examine the vertices

and edges of a graph G. That is a graph traversal, which means visiting all the
nodes of the graph. There are two graph traversal methods.

Breadth First Search (BFS)

Depth First Search (DFS)

Breadth First Search (BFS):

In breadth first search we start at a vertex v and mark it as having reached

(visited). The vertex v is at this time said to be unexplored. A vertex is said to
have been explored by an algorithm has visited all vertices adjacent from it. All
unvisited vertices adjacent from v are visited next and so on.

A complete traversal of the graph can be made by repeatedly calling BFS each
time with a new unvisited starting vertex.

Step-1: Initialize all nodes to the ready state (status-1)

Step-2: Put the starting node A in QUEUE and change its status to the waiting
state (status-2)

Step-3: Repeat steps 4 and 5 until queue is empty.

Step-4: Remove the front node N of queue, process N and change the status of
N to the processes state (status-3).

Data Structures Prepared by Mahesh MCA

 66
[Link]. IV SEMESTER

Step-5; Add to the rear of queue all the neighbors of N that are in the ready
state (status- 1) and change their status to the waiting state (status-2).

Step-6: Exit

Depth First Search: (DFS)

Depth first search (DFS) of undirected graph proceeds as follows. The start
vertex ―V‖ is visited. Next an unvisited vertex ―W‖ adjacent to ―V‖ is selected
and a depth first search from ―w‖initiated. When a vertex ―v‖ reached such that
all its adjacent vertices have been visited, we back up to the last vertex visited
which was an unvisited vertex ‟w‖ adjacent to its and initiate a depth search
vertex can be reached from any of the visited ones.

Algorithm:
Step-1: Initialize all nodes to the ready state (status-1).
Step-2: Push the starting node A onto the Stack and change its status to the
waiting state (status-2). Step-3: Repeat step 4 and 5 until stack is empty.
Step-4: Pop the top node N of stack . process N and change its status to the
processed state (STATUS-3).
Step-5: Push onto stack all the neighbor of N that are still in the ready state
(status-1) and change their status to the waiting state (status-2).
Step-5: Exit.

The depth first search of the above graph is

Data Structures Prepared by Mahesh MCA

 67
[Link]. IV SEMESTER

Discuss about Spanning Trees.

A spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Hence, a spanning tree does not have
cycles and it cannot be disconnected. Every connected and undirected Graph G
has at least one spanning tree. A disconnected graph does not have any
spanning tree, as it cannot be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected
graph can have maximum nn-2 number of spanning trees, where n is the
number of nodes. In the above addressed example, 33−2 = 3 spanning trees are
possible.

General Properties of Spanning Tree

Following are a few properties of the spanning tree connected to graph G –
A connected graph G can have more than one spanning tree.
All possible spanning trees of graph G, have the same number of edges
and vertices.
The spanning tree does not have any cycle (loops).
Removing one edge from the spanning tree will make the graph
disconnected, i.e. the spanning tree is minimally connected.
Adding one edge to the spanning tree will create a circuit or loop, i.e. the
spanning tree is maximally acyclic.

Data Structures Prepared by Mahesh MCA

 68
[Link]. IV SEMESTER

Mathematical Properties of Spanning Tree

Spanning tree has n-1 edges, where n is the number of nodes (vertices).
From a complete graph, by removing maximum e - n + 1 edges, we can
construct a spanning tree.
A complete graph can have maximum nn-2 number of spanning trees.

Application of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in
a graph. Common applications of spanning trees are –
Civil Network Planning
Computer Network Routing Protocol
Cluster Analysis
Minimal Spanning tree Algorithms
There are two algorithms for finding Minimum spanning tree
1) Prim‘s algorithm
2) Kruskal‘s algorithm
1) Prim’s algorithm
Prim's algorithm to find minimum cost spanning tree uses the greedy
approach. Prim's algorithm shares a similarity with the shortest path
first algorithms.
Algorithm
1) One node is picked as a root node (u) from the given connected graph.
2) At each stage choose a new vertex v from u, by considering an edge (u, v)
with minimum cost among all the edges from u, where u is already in the tree
and v is not in the tree.
3) The Prim‘s algorithm table is constructed with three parameters. They are:
Known – Vertex is added in the tree or not.
dv –Weight of the shortest arc connecting v to a known vertex.
Pv – last vertex which causes a change in dv
4) After selecting the vertex v, update rule is applied for each unknown w
adjacent to v. The rule is dw=Min (dw, Cw,v) that is if more than one path exist
between v to w, then dw is updated with minimum cost.
Example:
For the following graph construct Minimum spanning tree using Prim‘s
algorithm.

Data Structures Prepared by Mahesh MCA

 69
[Link]. IV SEMESTER

2) Kruskal’s algorithm
Kruskal's algorithm is an algorithm in graph theory that finds a minimum
spanning tree for a connected weighted graph. This means it finds a subset of
the edges that forms a tree that includes every vertex, where the total weight of
all the edges in the tree is minimized. If the graph is not connected, then it
finds a minimum spanning forest (a minimum spanning tree for each
connected component). Kruskal's algorithm is an example of a greedy
algorithm.

Algorithm:
1) Start by selecting the two nodes with the minimal costing link.
2) Select any two nodes with the minimal costing link. Your selection is not
bound by any requirement to
select nodes connected to previously selected nodes. Any two nodes we can
select, as long as it the minimal cost.
3) Repeat steps 1 and 2 until all nodes have been selected / connected.
Example:

Solution:

Data Structures Prepared by Mahesh MCA

 70
[Link]. IV SEMESTER

Data Structures Prepared by Mahesh MCA

 71
[Link]. IV SEMESTER

UNIT – V
Sortings & Searching

Sorting terminology and Sorting techniques:

Sorting is one of the most important and fundamental operations performed in
computer science. It is the task of rearranging data in an order such as
Ascending, Descending or Lexicographic order. Here the data may be of any
type like numerical, alphabetical or [Link] task sorting is done
more requently in the world of computer science. Sorting is important for the
following reasons.
1. How to rearrange a given set of data?
2. What kind of data structures are suitable to store data prior to their sorting?
3. How fast can the sorting be achieved?
4. How to sort various types of data values?
Basic Terminology
Internal Sorting:When a set of data to be stored in small enough such that the
entire sorting can be performed in a computer‘s internal storage(primary
memory) then the sorting is called ‗Internal Sort‘.
External Sort:Sorting of a large set of data, which is stored in external
memory(such as hard disk) is called ‗External Sorting‘.
Ascending Order:An arrangement of data is in increasing order of elements is
called ascending order . if Ai and Aj are two data items and Ai proceeds Aj then
Ai<= Aj.
Eg: {1, 2, 3, 4, 5, 6, 7, 8}
Descending Order:An arrangement of data is in decreasing order of elements
is called descending order . if Ai and Aj are two data items and Ai proceeds Aj
then Ai>= Aj.
Eg: {8, 7, 6, 5, 4, 3, 2, 1}
Lexicographic Order:Arranging character or string data values into dictionary
order is known lexicographic order. Eg: {Ant, Bat, Cat, Doll, Egg}
Swap:
Swap between two data storages implies the interchange of their contents.
Eg: Before Swap a[1] = 10 a[2] = 20
After Swap a[1] = 20 a[2] = 10.
Sorting Methods:
There are several sorting methods/strategies available to sort data in computer
data
processing. Each method follows a different strategy/algorithm to sort data.
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Merge Sort
5. Quick Sort

Data Structures Prepared by Mahesh MCA

 72
[Link]. IV SEMESTER

Explain in detail about sorting and different types of sorting techniques

Sorting is a technique to rearrange the elements of a list in ascending or

descending order, which can be numerical, or any user-defined order. Sorting
can be classified in two types;
Internal Sorts
This method uses only the primary memory during sorting process. All data
items are held in main memory and no secondary memory is required this
sorting process. If all the data that is to be sorted can be accommodated at a
time in memory is called internal sorting. There is a limitation for internal
sorts; they can only process relatively small lists due to memory constraints.
There are 3 types of internal sorts.

SELECTION SORT :- Ex:- Selection sort algorithm, Heap Sort algorithm

INSERTION SORT :- Ex:- Insertion sort algorithm, Shell Sort algorithm

EXCHANGE SORT :- Ex:- Bubble Sort Algorithm, Quick sort algorithm

External Sorts

Sorting large amount of data requires external or secondary memory. This

process uses external memory such as HDD, to store the data which is not fit
into the main memory. So, primary memory holds the currently being sorted
data only. All external sorts are based on process of merging. Different parts of
data are sorted separately and merged together.

Ex:- Merge Sort

Explain the algorithm for selection sort and give a suitable example.
In selection sort the list is divided into two sub-lists sorted and unsorted.
These two lists are divided by imaginary wall. We find a smallest element from
unsorted sub-list and swap it to the beginning. And the wall moves one
element ahead, as the sorted list is increases and unsorted list is decreases.

Assume that we have a list on ―n‖ elements. By applying selection sort, the first
element is compared with all remaining (n-1) elements. The smallest element is
placed at the first location. Again, the second element is compared with
remaining (n-1) elements. At the time of comparison, the smaller element is
swapped with larger element. Similarly, entire array is checked for smallest
element and then swapping is done accordingly. Here we need n-1 passes or
iterations to completely rearrange the data.

Data Structures Prepared by Mahesh MCA

 73
[Link]. IV SEMESTER

Algorithm:
The idea of algorithm is quite simple. Array is imaginary divided into two parts
- sorted one and unsorted one. At the beginning, sorted part is empty, while
unsorted one contains whole array. At every step, algorithm finds minimal
element in the unsorted part and adds it to the end of the sorted one. When
unsorted part becomes empty, algorithm stops.

When algorithm sorts an array, it swaps first element of unsorted part with
minimal element and then it is included to the sorted part.

Selection_Sort ( A [ ] , N )
Step 1 : Repeat For K = 0 to N – 2 Begin
Step 2 : Set POS = K
Step 3 : Repeat for J = K + 1 to N – 1 Begin
If A[ J ] < A [ POS ]
Set POS = J
End For
Step 4 : Swap A [ K ] with A [ POS ]
End For
Step 5 : Exit
A list of unsorted elements are: 23 78 45 8 32 56

A list of sorted elements now : 8 23 32 45 56 78

Data Structures Prepared by Mahesh MCA

 74
[Link]. IV SEMESTER

Example

public class SelectionSort

{
public static void main(String a[])
{
int[] arr = {9,14,3,2,43,11,58,22};
int index,i,j;
[Link]("List Before Sorting ");
for(int x:arr){
[Link](x+" ");
}
[Link]();
for (i = 0; i < [Link] - 1; i++)
{
index = i; for (j = i + 1; j < [Link]; j++)
{
if (arr[j] < arr[index])
{
index = j; //searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
[Link]("After Selection Sort");
for(int x:arr){
[Link](x+" ");
}
}
}

Data Structures Prepared by Mahesh MCA

 75
[Link]. IV SEMESTER

Explain the algorithm for insertion sort and give a suitable example.

Both the selection and bubble sorts exchange elements. But insertion sort does
not exchange elements. In insertion sort the element is inserted at an
appropriate place similar to card insertion. Here the list is divided into two
parts sorted and unsorted sub-lists. In each pass, the first element of unsorted
sub list is picked up and moved into the sorted sub list by inserting it in
suitable position. Suppose we have „n‟ elements, we need n-1 passes to sort
the elements.

Insertion sort works this way:

It works the way you might sort a hand of playing cards:

We start with an empty left hand [sorted array] and the cards face down
on the table [unsorted array].
Then remove one card [key] at a time from the table [unsorted array], and
insert it into the correct position in the left hand [sorted array].
To find the correct position for the card, we compare it with each of the
cards already in the hand, from right to left.

Advantages of Insertion Sort:

It is very simple.
It is very efficient for small data sets.
It is stable; i.e., it does not change the relative order of elements with
equal keys.
In-place; i.e., only requires a constant amount O(1) of additional memory
space.
Algorithm
INSERTION_SORT (A)

1. FOR j ← 2 TO length[A]
2. DO key ← A[j]
3. {Put A[j] into the sorted sequence A[1 . . j − 1]}
4. i ← j − 1
5. WHILE i > 0 and A[i] > key
6. DO A[i +1] ← A[i]
7. i ← i – 1
8. A[i + 1] ← key

Data Structures Prepared by Mahesh MCA

 76
[Link]. IV SEMESTER

A list of unsorted elements are: 78 23 45 8 32 36 . The results of insertion

sort for each pass is as follows:-

A list of sorted elements now : 8 23 32 36 45 78

Example:

public class InsertionSort {

public static void main(String a[]){
int[] arr = {9,14,3,2,43,11,58,22};
int n,key,j,i ;
[Link]("List Before Sorting");
for(int x:arr){
[Link](x+" "); }
[Link]();
n = [Link];
for ( j = 1; j < n; j++) {
key = arr[j];
i = j-1;
while ( (i > -1) && ( arr [i] > key ) ) {
arr [i+1] = arr [i];
i--;
}
arr[i+1] = key;
}
[Link]("List After Sorting");

Data Structures Prepared by Mahesh MCA

 77
[Link]. IV SEMESTER

for(int x:arr){
[Link](x+" "); }
}
}

Explain the algorithm for bubble sort and give a suitable example.
In bubble sort method the list is divided into two sub-lists sorted and unsorted.
The smallest element is bubbled from unsorted sub-list. After moving the
smallest element the imaginary wall moves one element ahead. The bubble sort
was originally written to bubble up the highest element in the list. But there is
no difference whether highest / lowest element is bubbled. This method is easy
to understand but time consuming. In this type, two successive elements are
compared and swapping is done. Thus, step-by-step entire array elements are
checked. Given a list of „n‟ elements the bubble sort requires up to n-1 passes
to sort the data.

Algorithm for Bubble Sort:

1. Compare each pair of adjacent elements from the beginning of an array and,
if they are in reversed order, swap them.

2. If at least one swap has been done, repeat step 1.

Bubble_Sort ( A [ ] , N )

Step 1 : Repeat For P = 1 to N – 1 Begin

Step 2 : Repeat For J = 1 to N – P Begin

Step 3 : If ( A [ J ] < A [ J – 1 ] )

Swap ( A [ J ] , A [ J – 1 ] )

End For End For

Step 4 : Exit

Data Structures Prepared by Mahesh MCA

 78
[Link]. IV SEMESTER

A list of unsorted elements are: 10 47 12 54 19 23

(Bubble up for highest value shown here)

Example

public class BubbleSort { public static void main(String[ ] args) {

int arr[ ] ={3,60,35,2,45,320,5};

int n , temp ,i , j;

[Link]("Array Before Bubble Sort");

for(i=0; i < [Link]; i++){

[Link](arr[i] + " ");

[Link]( );

n = [Link]; temp = 0;

for( i=0; i < n; i++){

for( j=1; j < (n-i); j++){

if(arr[j-1] > arr[j]){

//swap elements

Data Structures Prepared by Mahesh MCA

 79
[Link]. IV SEMESTER

temp = arr[j-1];

arr[j-1] = arr[j];

arr[j] = temp;

[Link]("Array After Bubble Sort");

for( i=0; i < [Link]; i++){

[Link](arr[i] + " ");

Explain the algorithm for QUICK sort ( partition exchange sort) and give a
suitable example.
Quick sort is based on partition. It is also known as partition exchange sorting.
It was invented by CAR Hoare. The basic concept of quick sort process is pick
one element from an array and rearranges the remaining elements around it.
This element divides the main list into two sub lists. This chosen element is
called pivot. Once pivot is chosen, then it shifts all the elements less than pivot
to left of value pivot and all the elements greater than pivot are shifted to the
right side. This procedure of choosing pivot and partition the list is applied
recursively until sub-lists consisting of only one element.

Ex:- A list of unsorted elements are: 8 3 2 11 5 14 0 2 9 4 20

Data Structures Prepared by Mahesh MCA

 80
[Link]. IV SEMESTER

Algorithm for quick sort:

quicksort(q)

varlist less, pivotList, greater

if length(q) ≤ 1

return q

select a pivot value pivot from q

for each x in q except the pivot element

if x < pivot then add x to less

if x ≥ pivot then add x to greater

add pivot to pivotList

return concatenate(quicksort(less), pivotList, quicksort(greater))

Time Complexity of Quick sort:

Best case : O (n log n)

Average case : O (n log n)

Data Structures Prepared by Mahesh MCA

 81
[Link]. IV SEMESTER

Worst case : O (n2)

Advantages of quick sort

This is faster sorting method among all.
Its efficiency is also relatively good.
It requires relatively small amount of memory.
Disadvantages of quick sort:
It is complex method of sorting so, it is little hard to implement than other
sorting methods.
Example:
public class MyQuickSort {
private int array[ ];
private int length; public void sort (int[ ] inputArr) {
if (inputArr == null || [Link] == 0) {
return;
}
[Link] = inputArr;
length = [Link]; quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
while (i <= j) {
while (array[i] < pivot) { i++;
}
while (array[j] > pivot) { j--;
}
if (i <= j) {
exchangeNumbers(i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(lowerIndex, j); if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];

Data Structures Prepared by Mahesh MCA

 82
[Link]. IV SEMESTER

array[i] = array[j];
array[j] = temp;
}
public static void main(String a[ ]){
MyQuickSort sorter = new MyQuickSort();
int[] arr = {24,2,45,20,56,75,2,56,99,53,12};
[Link]("List before sort ");
for(int x :arr)
[Link](x+" ");
[Link](arr);
[Link]("\nList after sort");
for(int x:arr){
[Link](x+ " ");
[Link](" ");
}
}
}

Explain the algorithm for Merge sort and give a suitable example.
The basic concept of merge sort is divides the list into two smaller sub-lists of
approximately equal size. Recursively repeat this procedure till only one
element is left in the sub-list. After this, various sorted sub-lists are merged to
form sorted parent list. This process goes on recursively till the original sorted
list arrived.

Algorithm for merge sort:

Merge sort is based on the divide-and-conquer paradigm. Its worst-case
running time has a lower order of growth than insertion sort. Since we are
dealing with sub-problems, we state each sub-problem as sorting a sub-array
A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse
through sub-problems.

To sort A[p .. r]:

1. Divide Step

If a given array A has zero or one element, simply return; it is already sorted.
Otherwise, split A[p .. r] into two sub-arrays A[p .. q] and A[q + 1 .. r], each

Data Structures Prepared by Mahesh MCA

 83
[Link]. IV SEMESTER

containing about half of the elements of A[p .. r]. That is, q is the halfway point
of A[p .. r].

2. Conquer Step

Conquer by recursively sorting the two sub-arrays A[p .. q] and A[q + 1 .. r].

3. Combine Step

Combine the elements back in A[p .. r] by merging the two sorted sub-arrays
A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we
will define a procedure MERGE (A, p, q, r).

Note that the recursion bottoms out when the sub-array has just one element,
so that it is sorted. To sort the entire sequence A[1 .. n], make the initial call to
the procedure MERGE-SORT (A, 1, n).

Properties
It is a Stable algorithm i.e does not change the relative order of elements
with equal keys
It does not require random access to data

Data Structures Prepared by Mahesh MCA

 84
[Link]. IV SEMESTER

Time Complexity of merge sort:

Best case : O (n log n)

Average case : O (n log n)

Worst case : O (n log n)

Example:

public class MyMergeSort {

private int[ ] array;

private int[ ] tempMergArr;

private int length;

public static void main(String a[ ]){

int[ ] inputArr = {45,23,11,89,77,98,4,28,65,43};

MyMergeSort mms = new MyMergeSort( );

[Link]("Before sorting ");

for(int i:inputArr)

[Link](i +" ");

[Link](inputArr);

[Link]("\nAfter sorting ");

for(int i:inputArr)

[Link](i +" ");

public void sort(int inputArr[ ]) {

[Link] = inputArr;

[Link] = [Link];

[Link] = new int[length];

doMergeSort(0, length - 1);

Data Structures Prepared by Mahesh MCA

 85
[Link]. IV SEMESTER

private void doMergeSort(int lowerIndex, int higherIndex) {

if (lowerIndex < higherIndex) {

int middle = lowerIndex + (higherIndex - lowerIndex) / 2;

// Below step sorts the left side of the array

doMergeSort(lowerIndex, middle);

// Below step sorts the right side of the array

doMergeSort(middle + 1, higherIndex);

// Now merge both sides

mergeParts(lowerIndex, middle, higherIndex);

private void mergeParts(int lowerIndex, int middle, int higherIndex) {

for (int i = lowerIndex; i <= higherIndex; i++) {

tempMergArr[i] = array[i];

int i = lowerIndex;

int j = middle + 1;

int k = lowerIndex;

while (i <= middle && j <= higherIndex) {

if (tempMergArr[i] <= tempMergArr[j]) {

array[k] = tempMergArr[i];

i++;

else {

Data Structures Prepared by Mahesh MCA

 86
[Link]. IV SEMESTER

array[k] = tempMergArr[j];

j++;

k++;

while (i <= middle) {

array[k] = tempMergArr[i];

k++;

i++;

Write a short notes on SEARCHING

Searching refers to the operation of finding the location of a given item in list of
items. Consider an array is given with ‗n‘ elements. A specific element ‗item‘ is
given to search. Now, we want to find whether the item is available in the list
of n elements or not. If the search item is exist, then it refers to successful
search; otherwise, it refers to unsuccessful search.

Most important techniques used for search operation are:

1. Linear search
2. Binary search
1. LINEAR SEARCH
Consider an array K with n elements as K[1], K[2], . . . K[n]. Suppose an item
of information is given to search.

Data Structures Prepared by Mahesh MCA

 87
[Link]. IV SEMESTER

In this technique, compare item value with each element of K form index 1 to
index n. At any position i, if K[i]=item, then return index i value refers to
successful search; otherwise, return -1 refers to unsuccessful search.

Example: Search an element 19 from the list of elements: 18 35 78 23

19 709

item = 19

i=1 K[1]=item → 18 = 19 FALSE

i=2 K[2]=item → 35 = 19 FALSE

i=3 K[3]=item → 78 = 19 FALSE

i=4 K[4]=item → 23 = 19 FALSE

i=5 K[5]=item → 19 = 19 TRUE

ELEMENT FOUND

Algorithm NonRecLSearch(K, n, item):

Suppose K is an array that contains ‗n‘ elements. Search element is given in
the variable ‗item‘.

This function returns an index position ‗i' if the element is found; otherwise,
return -1.

Step 1: Repeat for i ← 1 to n

If K[i]=item Then
Return i
EndIf
EndRepeat
Step 2: Return -1
Algorithm RecLSearch(K, n,item):
Step 1: If n = 0 Then
Return -1
ElseIf K[n]=item Then
Return n
Else
Return RecLSearch(K, n-1, item)
EndIf

Data Structures Prepared by Mahesh MCA

 88
[Link]. IV SEMESTER

// PROGRAM TO SEARCH A GIVEN ELEMENT USING LINEAR SEARCH

public class LinearSearchExample

{
public static int linearSearch(int[] arr, int key)
{
for(int i=0;i<[Link];i++)
{
if(arr[i] == key)
{
return i;
}
}
[Link]("searching element was not found in the array");
return -1;
}
public static void main(String a[ ])
{
int a1[ ]= {10,20,30,50,70,90};
int key = 70;
[Link](key+" is found at index: "+linearSearch(a1, key));
}
}

Time Complexity:

The worst-case and average-case time complexity of linear search is O(n).

2. Binary Search :
Binary search is another searching algorithm, that takes less time complexity
compared with the linear search. Binary search can be applied only on the
array which is available in sorted order.

Consider K is an with n elements as K[1]≤K[2]≤. . . . ≤K[n]. Suppose an item of

information is given to search in the variable ITEM.
In binary search technique, first compute
Mid = (Low+High) / 2
Where, Low refers to the first index and High refers to last index of the array in
the initial call. Now, the process falls into any one of the following three cases.

Case 1: If ITEM = K[Mid]; Then the search is successful search.

Data Structures Prepared by Mahesh MCA

 89
[Link]. IV SEMESTER

Case 2: If ITEM > K[Mid]; Then the ITEM can appear only in the right half
of the array. So, we reset the Low value as Low = Mid+1 and begin
search again.

Case 3: If ITEM < K[Mid]; Then the ITEM can appear only in the left half of
the array. So, we reset the High value as High = Mid-1 and begin
search again.

This procedure is repeated upto we reach Low > High. When we obtain this
condition, it indicates that the search is unsuccessful search.

Example 1: Search an element 44 from the list

11 22 30 33 41 44 55

Low = 1 High = 7 Mid = (1+7) / 2 = 4

ITEM = K[Mid] 44 = 33 FALSE
ITEM > K[Mid] 44 > 33 TRUE
Reset Low = 4+1 = 5

Low = 5 High = 7 Mid = (5+7)/2 = 6

ITEM = K[Mid] 44 = 44 TRUE

SUCCESSFUL SEARCH, ITEM FOUND

Algorithm Non-Recursive BSearch(K, Low, High, ITEM):

Consider K is a sorted array and ITEM of information is given to search. Low,
High and Mid variables refers to beginning, ending and middle locations of the
given array K.
This function is used to find the location of the search ITEM and returns index
value if found; otherwise, it return -1.

Step 1: Repeat while Low ≤ High

Mid ← (Low+High)/2
If ITEM < K[Mid] Then
High ← Mid-1
ElseIf ITEM > K[Mid] Then
Low ← Mid+1
Else
Return Mid
EndIf
EndRepeat
Step 2: Return -1

Data Structures Prepared by Mahesh MCA

 90
[Link]. IV SEMESTER

Algorithm Recursive BSearch(K, Low, High, ITEM):

Step 1: If Low ≤ High Then

Mid ← (Low+High)/2
If ITEM = K[Mid] Then
Return Mid
ElseIf ITEM < K[Mid] Then
Return RBsearch(K, Low, Mid-1, ITEM)
Else
Return RBsearch(K,Mid+1,High,ITEM)
EndIf
EndIf
Step 2: Return -1

Java program for implementation of Binary Search

class BinarySearchExample
{
public static void binarySearch(int arr[ ], int first, int last, int key)
{
int mid = (first + last)/2;
while( first <= last )
{
if ( arr[mid] < key )
{
first = mid + 1;
}
else if (arr[mid] == key)
{
[Link]("Element is found at index: " + mid);
break;
}
else
{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last )
{
[Link]("Element is not found!");

Data Structures Prepared by Mahesh MCA

 91
[Link]. IV SEMESTER

}
}
public static void main(String args[ ])
{
int arr[ ] = {10,20,30,40,50};
int key = 40;
int last=[Link]-1;
binarySearch(arr,0,last,key);
}
}

Data Structures Prepared by Mahesh MCA

 92
[Link]. IV SEMESTER

DATA STRUCTURES USING JAVA LAB

/*[Link] a Program to implement the Linked List operations?*/
import [Link].*;
public class LinkedListDemo
{
public static void main(String args[])
{
LinkedList ll = new LinkedList();// Here ll is a object to LinkedList class
[Link]("Virat");
[Link]("Dhoni");
[Link]("Rahane");
[Link]("Jadeja");
[Link]("Vijay");
[Link]("Linked List Content: \n" +ll);
[Link]("Ashwin");
[Link]("Zaheer");
[Link]("LinkedList Content after addition: \n" +ll);

[Link]();
[Link]();
[Link]("LinkedList after deletion of first and last element: \n" +ll);
[Link](1, "Karan");
[Link](2);
[Link]("Final Content: \n" +ll);
}
}

Save this program with [Link].

At command prompt:
D:\JDS Programs>javac -Xlint [Link]
D:\JDS Programs>java LinkedListDemo
OUTPUT:
Linked List Content:
[Virat, Dhoni, Rahane, Jadeja, Vijay]
LinkedList Content after addition:
[Ashwin, Virat, Dhoni, Rahane, Jadeja, Vijay, Zaheer]
LinkedList after deletion of first and last element:
[Virat, Dhoni, Rahane, Jadeja, Vijay]
Final Content:
[Virat, Karan, Rahane, Jadeja, Vijay]

Data Structures Prepared by Mahesh MCA

 93
[Link]. IV SEMESTER

//2) Write a Program to implement the Stack operations using an Array?

import [Link].*;
import [Link].*;
class MyStack
{
private int top;
private int item[ ];

MyStack(int size)
{
top = -1;
item = new int[size];
}

void pushItem(int data)

{
if (top == [Link] - 1)
{
[Link]("Stack is Full");
}
else
{
item[++top] = data;
[Link]("Pushed Item :" + item[top]);
}
}

void popItem( )
{
if (top < 0)
{
[Link]("Stack is Empty");
}
else
{
top--;
[Link]("Pop Item : " + item[top+1]);
}
}

public void display( )

{
for(int i =top; i>=0;i--)
[Link](item[i]);
}

Data Structures Prepared by Mahesh MCA

 94
[Link]. IV SEMESTER

}
class StackExample
{
public static void main(String[] args) throws IOException
{
MyStack stk = new MyStack(10);
boolean yes=true;
int choice;
Scanner sc = new Scanner([Link]);
//BufferedReader is = new BufferedReader(new InputStreamReader([Link]));

do{
[Link]("_________________");
[Link]("Menu:");
[Link]("_________________");
[Link]("[Link]\[Link]\[Link]\[Link]\n\nEnter Choice");
choice = [Link]();
switch(choice)
{
case 1: [Link]("Enter Push Item: ");
[Link]([Link]());
break;
case 2: [Link]( );break;
case 3: [Link]("Stack elements:");
[Link]( ); break;
case 4: yes = false;break;
default: [Link]("Invalid Choice");
}
}while(yes==true);
}
}

Save this program with [Link].

At command prompt:
D:\JDS Programs>javac [Link]
D:\JDS Programs>java StackExample
Output:
___________________

Menu:
___________________
[Link]
[Link]
[Link]
[Link]
Enter Choice
1
Enter Push Item :
77
Pushed Item : 77

Data Structures Prepared by Mahesh MCA

 95
[Link]. IV SEMESTER

___________________
Menu:
___________________
[Link]
[Link]
[Link]
[Link]
Enter Choice
1
Enter Push Item :
66
Pushed Item : 66
___________________
Menu:
___________________
[Link]
[Link]
[Link]
[Link]
Enter Choice
3
Stack element
66 77
77
___________________
Menu:
___________________
[Link]
[Link]
[Link]
[Link]
Enter Choice
2
Pop item:66

___________________
Menu:
___________________
[Link]
[Link]
[Link]
[Link]
Enter Choice
4

//[Link] a Program to implement the Queue operations using an array?

class MyQueue
{
int front;
int item[ ];
int rear;
int temp;
MyQueue(int size)
{

Data Structures Prepared by Mahesh MCA

 96
[Link]. IV SEMESTER

front=-1;
rear=-1;
item=new int[size];
}
void eQ(int data)
{
if (rear==[Link]-1)
{
[Link]("Queue is full");
}
else
{
if (rear==-1)
{
front = 0;
rear = 0;
item[rear] = data;
}
else if (rear+1<[Link])
item[++rear] = data;
[Link]("Element " + data + " is entered into the Queue ");
display();
}
}
public void dQ( )
{
if(front<0)
{
[Link]("Queue is Empty");
}
else
{
temp=front;
front++;
[Link]("Deleted element from the queue is:"+item[temp]);
display( );
}
}
public void display( )
{
if(rear >= front)
{
[Link]("Elements in the Queue :");
for(int i=front;i<=rear;i++)
{
[Link](item[i]);

Data Structures Prepared by Mahesh MCA

 97
[Link]. IV SEMESTER

}
}
}

public static void main(String[ ] args)

{
MyQueue q=new MyQueue(5);
[Link](5);
[Link](10);
[Link](15);
[Link](22);
[Link]();
[Link]();
[Link](30);

}
}

Save this program with [Link].

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java MyQueue
Output:
Element 5 is entered into the Queue
Elements in the Queue :
5
Element 10 is entered into the Queue
Elements in the Queue :
5
10
Element 15 is entered into the Queue
Elements in the Queue :
5
10
15
Element 22 is entered into the Queue
Elements in the Queue :
5
10
15
22
Deleted element from the queue is:5
Elements in the Queue :
10
15
22
Deleted element from the queue is:10
Elements in the Queue :
15
22
Element 30 is entered into the Queue
Elements in the Queue :
15
22
30

Data Structures Prepared by Mahesh MCA

 98
[Link]. IV SEMESTER

//[Link] Programs to implement the Stack operations using a single linked list

import [Link].*;
class MyNode
{
int item;
MyNode next;
MyNode(int val)
{
item = val;
}
public void displayNode()
{
[Link](item );
}
}

class MyLinkedList
{
MyNode first;
boolean isEmpty()
{
return (first==null);
}
void insert(int val)
{
MyNode newNode = new MyNode(val);
[Link] = first;
first = newNode;
}
MyNode delete()
{
MyNode temp = first;
first = [Link];
return temp;
}
void display()
{
[Link]("Elements from top to bottom");
MyNode current = first;
while(current != null)
{
[Link]();
current = [Link];
}
[Link]("");
}

Data Structures Prepared by Mahesh MCA

 99
[Link]. IV SEMESTER

class MyStack
{
MyLinkedList list;
MyStack()
{
list = new MyLinkedList();
}
void push(int num)
{
[Link](num);
}
MyNode pop()
{
return [Link]();
}
boolean isEmpty()
{
return [Link]();
}
void displayStack()
{
[Link]("Stack : ");
[Link]();
}
}

class StackLinkedList
{
public static void main(String[] args) throws IOException
{
MyStack s= new MyStack();
[Link](10);
[Link](20);
[Link]();
[Link](30);
[Link](40);
[Link]();
[Link]();
[Link]();
[Link]("Two elements are popped");
[Link]();
}
}

Save this program with [Link].

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java StackLinkedList
Output:
Stack : Elements from top to bottom

Data Structures Prepared by Mahesh MCA

 100
[Link]. IV SEMESTER

20
10

Stack : Elements from top to bottom

40
30
20
10

Two elements are popped

Stack : Elements from top to bottom
20
10

//[Link] Programs to implement the Queue operations using a singly linked list
import [Link].*;
class MyNode
{
int item;
MyNode next;
MyNode(int val)
{
item = val;
}
void displayNode( )
{
[Link](item+" " );
}
}
class MyLinkedList
{
MyNode start;
MyNode end;
boolean isEmpty( )
{
return start==null;
}
void insertEnd(int val)
{
MyNode newNode = new MyNode(val);
if( isEmpty( ) )
start = newNode;
else
[Link] = newNode;
end = newNode;
}
int deleteStart( )
{
int temp = [Link];
if([Link] == null)

Data Structures Prepared by Mahesh MCA

 101
[Link]. IV SEMESTER

end = null;
start = [Link];
return temp;
}
void displayList( )
{
MyNode current = start;
while(current != null)
{
[Link]();
current = [Link];
}
[Link](" ");
}
}
class MyQueue
{
MyLinkedList list;
MyQueue( )
{
list= new MyLinkedList( );
}
boolean isEmpty( )
{
return [Link]( );
}
void insert(int k)
{
[Link](k);
}
int delete( )
{
return [Link]( );
}
void display( )
{
[Link]("Queue [start to end]: ");
[Link]( );
}
}
class QueueLinkedList
{
public static void main(String[ ] args)
{
MyQueue demo = new MyQueue( );
[Link]("Inserting two elements into the queue");
[Link](10);
[Link](20);
[Link]( );
[Link]("Inserting one more element into the queue at the end");

Data Structures Prepared by Mahesh MCA

 102
[Link]. IV SEMESTER

[Link](30);
[Link]( );
[Link]("Deleting one element from the front");
[Link]( );
[Link]( );
}
}

Save this program with [Link].

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java QueueLinkedList

Output:
Inserting two elements into the queue
Queue [start to end]: 10 20
Inserting one more element into the queue at the end
Queue [start to end]: 10 20 30
Deleting one element from the front
Queue [start to end]: 20 30

//6) Write a Java program for implementation of QuickSort?

class QuickSort
{
/* This function takes last element as pivot, places the pivot element at its correct
position in sorted array, and places all smaller (smaller than pivot) to left of
pivot and all greater elements to right of pivot */

int partition(int arr[ ], int low, int high)

{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or equal to pivot
if (arr[ j] <= pivot)
{
i++;
// swap arr[ i] and arr[ j]
int temp = arr[i];
arr[i] = arr[ j];
arr[ j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;

Data Structures Prepared by Mahesh MCA

 103
[Link]. IV SEMESTER

}
/* The main function that implements QuickSort( )
arr[ ] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[ ], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

/* A utility function to print array of size n */

static void printArray(int arr[ ])
{
int n = [Link];
for (int i=0; i<n; ++i)
[Link](arr[i]+" ");
[Link]( );
}

public static void main(String args[])

{
int arr[ ] = {10, 7, 8, 9, 1, 5};
int n = [Link];

QuickSort ob = new QuickSort( );

[Link](arr, 0, n-1);

[Link]("Sorted Array:");
printArray(arr);
}
}

Save this program with [Link]

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java QuickSort
Press enter key
Output:
Sorted Array:
1 5 7 8 9 10

Data Structures Prepared by Mahesh MCA

 104
[Link]. IV SEMESTER

//7) Write a Java program for implementation of Binary Search

class BinarySearchExample
{
public static void binarySearch(int arr[ ], int first, int last, int key)
{
int mid = (first + last)/2;
while( first <= last )
{
if ( arr[mid] < key )
{
first = mid + 1;
}
else if (arr[mid] == key)
{
[Link]("Element is found at index: " + mid);
break;
}
else
{
last = mid - 1;
}
mid = (first + last)/2;
}
if ( first > last )
{
[Link]("Element is not found!");
}
}
public static void main(String args[ ])
{
int arr[ ] = {10,20,30,40,50};
int key = 40;
int last=[Link]-1;
binarySearch(arr,0,last,key);
}
}

Save this program with [Link]

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java BinarySearchExample
Press enter key
Output:

Element is found at index: 3

Data Structures Prepared by Mahesh MCA

 105
[Link]. IV SEMESTER

//8) Write a Java program for implementation of Linear Search (or) Sequential
public class LinearSearchExample
{
public static int linearSearch(int[] arr, int key)
{
for(int i=0;i<[Link];i++)
{
if(arr[i] == key)
{
return i;
}
}
[Link]("searching element was not found in the array");
return -1;
}
public static void main(String a[ ])
{
int a1[ ]= {10,20,30,50,70,90};
int key = 70;
[Link](key+" is found at index: "+linearSearch(a1, key));
}
}

Save this program with [Link].

At command prompt:
D:\ JDS Programs>javac [Link]
D:\JDS Programs>java LinearSearchExample

Output:
70 is found at index: 4

//9) Write a Java program to implement the Selection Sort?

/* Following Java Program ask to the user to enter the array size and array elements, then it will sort the
array in ascending order and display the sorted array: */
/* Java Program Example - Selection Sort */

import [Link];

public class JavaProgram

{
public static void main(String args[])
{
int size, i, j, temp;
int arr[] = new int[50];
Scanner scan = new Scanner([Link]);

[Link]("Enter Array Size : ");

size = [Link]();

[Link]("Enter Array Elements : ");

for(i=0; i<size; i++)

Data Structures Prepared by Mahesh MCA

 106
[Link]. IV SEMESTER

{
arr[i] = [Link]();
}

[Link]("Sorting Array using Selection Sort Technique:\n");

for(i=0; i<size; i++)
{
for(j=i+1; j<size; j++)
{
if(arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}

[Link]("Now the Array after Sorting is :\n");

for(i=0; i<size; i++)
{
[Link](arr[i]+ " ");
}
}
}

Output:
Enter Array Size : 6
Enter Array Elements : 12
98
23
87
45
76
Sorting Array using Selection Sort Technique:
Now the Array after Sorting is:
12 23 45 76 87 98

//10) Write a Java program to implement the Insertion Sort?

/*Following Java Program ask to the user to enter array size and array elements to sort the array using the
insertion sort technique, then display the sorted array on the screen:*/
/* Java Program Example - Insertion Sort */

import [Link];

public class JavaProgramIns

{
public static void main(String args[])
{

Data Structures Prepared by Mahesh MCA

 107
[Link]. IV SEMESTER

int size, i, j, temp;

int arr[] = new int[50];
Scanner scan = new Scanner([Link]);

[Link]("Enter Array Size : ");

size = [Link]();

[Link]("Enter Array Elements : ");

for(i=0; i<size; i++)
{
arr[i] = [Link]();
}

[Link]("Sorting Array using Insertion Sort Technique:\n");

for(i=1; i<size; i++)
{
temp = arr[i];
j = i - 1;
while((temp < arr[j]) && (j >= 0))
{
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = temp;
}

[Link]("Array after Sorting is : \n");

for(i=0; i<size; i++)
{
[Link](arr[i] + " ");
}
}
}

Output:
Enter Array Size : 6
Enter Array Elements : 12
98
23
87
45
76
Sorting Array using Insertion Sort Technique:
Now the Array after Sorting is:
12 23 45 76 87 98

Data Structures Prepared by Mahesh MCA

 108
[Link]. IV SEMESTER

//11) Write a Java program to implement the Bubble Sort?

import [Link];
class BubbleSort
{
public static void main(String args[ ])
{
int n, i, j, swap;
Scanner in = new Scanner([Link]);
[Link]("Enter number of integers to sort:");
n = [Link]();
int array[ ] = new int[n];
[Link]("Enter " + n + " elements:");

for (i = 0; i < n; i++)

{
array[i] = [Link]( );
}
for (i = 0; i < ( n - 1 ); i++)
{
for (j = 0; j < n - i - 1; j++)
{
if (array[ j] > array[ j+1]) /* For descending order use < */
{
swap = array[j];
array[ j] = array[j+1];
array[ j+1] = swap;
}
}
}
[Link]("Sorted list of numbers:");
for (i = 0; i < n; i++)
[Link](" "+array[i]);
}
}

Output:
Enter number of integers to sort:
6
Enter 6 elements:
8
4
6
11
3
10
Sorted list of numbers:
3 4 6 8 10 11

Data Structures Prepared by Mahesh MCA