2-1 R18 - Data Structures Unit-1
Uploaded by
bsoundarya662-1 R18 - Data Structures Unit-1
Uploaded by
bsoundarya66DATA STRUCTURES @UNIT-1 M.
NAGARANI
UNIT – I
Introduction to Data Structures, abstract data types, Linear list – singly linked list
implementation, insertion, deletion and searching operations on linear list, Stacks-Operations,
array and linked representations of stacks, stack applications, Queues-operations, array and
linked representations.
1
DATA STRUCTURES @UNIT-1 [Link]
Data structure A data structure is a specialized format for
organizing and storing data. General data structure types include
the array, the file, the record, the table, the tree, and so on. Any
data structure is designed to organize data to suit a specific
purpose so that it can be accessed and worked with in appropriate
ways.
A data structure is a group of data elements that provides the
easiest way to store and perform different actions on the data of
the computer. A data structure is a particular way of organizing
data in a computer so that it can be used effectively. The idea is to
reduce the space and time complexities of different tasks.
A data structure is also defined an instance of ADT (ABSTRACT DATA TYPE).
It is formally defined as a triplet:
[D,S,A], where
D: Set of the domain.
S: the set of operations.
A: the set of axioms.
Need of Data structure
The structure of the data and the synthesis of the algorithm are relative to each other. Data
presentation must be easy to understand so the developer, as well as the user, can make an
efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and storing data.
Here is a list of the needs for data.
1. Data structure modification is easy.
2. It requires less time.
3. Save storage memory space.
4. Data representation is easy.
2
DATA STRUCTURES @UNIT-1 [Link]
5. Easy access to the large database
Abstract Data Type
In computer science, an abstract data type (ADT) is a
mathematical model for data types where a data type is defined by
its behavior (semantics) from the point of view of a user of
the data, specifically in terms of possible values, possible
operations on data of this type, and the behavior of these
operations.
When a class is used as a type, it is an abstract type that
refers to a hidden representation.
In this model an ADT is typically implemented as a class,
and each instance of the ADT is usually a n object of that class.
In ADT all the implementation details are hidden
BUILT IN DATA STRUCTURES
These data structures are also called as a primitive data structure where
the data is directly supported by the programming language.
These are classified into four types. They are namely integer , float,
character, double
Integer is defined with a keyword “int” where it occupies 2 bytes of
3
DATA STRUCTURES @UNIT-1 [Link]
memory and the format specifier is %d.
Float is defined with a keyword “float” where it occupies 4 bytes of memory
and the format specifier is %f.
Character is defined with a keyword “char” where it occupies 1 bytes of
memory and the format specifier is %c.
double is defined with a keyword “double” where it occupies 8 bytes of
memory and the format specifier is %ld.
USER DEFINED DATA STRUCTURES
These data structures are also called as a non primitive data
structure where the data is not directly supported by the programming
language but it depends on the primitive data structures.
These are classified into two types. They are namely
Linear data structures are the data structures in
which data is arranged in a list or in a sequence.
Non linear data structures are the data structures in
which data may be arranged in a hierarchic al
manner.
Linear Data Structure
Data structure in which data elements are arranged sequentially or linearly, where each
element is attached to its previous and next adjacent elements is called a linear data
structure. Elements are arranged in one dimension, also known as linear dimension.
Example: linear data structures are array, stack, queue, linked list, etc.
Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
An example of this data structure is an array.
Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be
randomly updated during the runtime which may be considered efficient concerning
the memory (space) complexity of the code.
4
DATA STRUCTURES @UNIT-1 [Link]
Examples of this data structure are queue, stack, etc.
Non-Linear Data Structure
Elements are arranged in one-many, many-one and many-many dimensions.
Example: tree, graph, table, etc.
Applications of Data Structures
Data structures are used in various fields such as:
Operating system
Graphics
Computer Design
Blockchain
Genetics
Image Processing
Simulation,
etc.
How Data Structure varies from Data Type:
We already have learned about data structure. Many times, what happens is that people get
confused between data type and data structure. So let’s see a few differences between data
type and data structure to make it clear.
5
DATA STRUCTURES @UNIT-1 [Link]
Data Type Data Structure
The data type is the form of a variable to Data structure is a collection of different kinds of
which a value can be assigned. It defines data. That entire data can be represented using
that the particular variable will assign the an object and can be used throughout the
values of the given data type only. program.
It can hold value but not data. Therefore, It can hold multiple types of data within a single
it is dataless. object.
The implementation of a data type is Data structure implementation is known as
known as abstract implementation. concrete implementation.
There is no time complexity in the case of In data structure objects, time complexity plays
data types. an important role.
While in the case of data structures, the data and
its value acquire the space in the computer’s
In the case of data types, the value of data main memory. Also, a data structure can hold
is not stored because it only represents different kinds and types of data within one
the type of data that can be stored. single object.
Data type examples are int, float, double, Data structure examples are stack, queue, tree,
etc. etc.
6
DATA STRUCTURES @UNIT-1 [Link]
ARRAYS
An array is a group of elements consisting of similar type of data. Array is
the variable that holds the multiple data with same type or array is the homogeneous
data collection.
An array is a fixed size sequenced collection of elements of the same data type.
An array is a collection of items stored at contiguous memory locations. The idea is to
store multiple items of the same type together. This makes it easier to calculate the
position of each element by simply adding an offset to a base value, i.e., the memory
location of the first element of the array (generally denoted by the name of the array).
All the element values are identified by a single variable name along with the index.
These array elements are allotted memory locations in continuous manner, and so, it is
easy to retrieve them.
The use of an array reduces the usage of so many variables in the program.
Notation of array is [ ] (square bracket).
Arrays can be declared in various ways in different languages. For better illustration,
below are some language-specific array declarations.
int arr[5]; // This array will store integer type element
char arr[10]; // This array will store char type element
float arr[20]; // This array will store float type element
7
DATA STRUCTURES @UNIT-1 [Link]
Basic terminologies of array
Array Index: In an array, elements are identified by their indexes. Array index starts
from 0.
Array element: Elements are items stored in an array and can be accessed by their index.
Array Length: The length of an array is determined by the number of elements it can
contain.
What is the need of Arrays in Data Structures
Assume there is a class of five students and if we have to keep records of their marks in
examination then, we can do this by declaring five variables individual and keeping track of
records but what if the number of students becomes very large, it would be challenging to
manipulate and maintain the data.
What it means is that, we can use normal variables (v1, v2, v3, ..) when we have a small
number of objects. But if we want to store a large number of instances, it becomes difficult to
manage them with normal variables. The idea of an array is to represent many instances in
one variable..
8
DATA STRUCTURES @UNIT-1 [Link]
Arrays are classified into 2 types as follows:
(a) Single Dimensional arrays
(b) Multi Dimensional arrays.
SINGLE DIMENSIONAL ARRAYS:- In this type of array, we give only one
dimension. The dimension is the no. of elements that we want to have in an array.
9
DATA STRUCTURES @UNIT-1 [Link]
Each element in the array is identified by its array name and its subscript or index.
The index of an array starts from 0 and lasts till size-1.
Syntax:
datatype array_name[size];
Data type is the type of data we want to store in an array, size indicates the no. of
values that can be stored in the array and array_name indicates the name of the
array.
Example:
int b[10] // declaration shows , a variable "b" will hold 10 integer data.
float c[4] // declaration shows , a variable "c" will hold 4 float data.
Comparison between Simple variable & Array Variable:
int x; // Declaration of simple variable
int y[10]; // Declaration of Array variable x will hold a single integer data but y
will hold 10 integer data.
10
DATA STRUCTURES @UNIT-1 [Link]
In Array variable, index number is always start with 0 and go up to the (Size-1).
In above example y is the array variable hold 10 integer data on appropriate location
i,e
First on y[0] ,
second on y[1] ,
third on y[2] and so on
.....
last data on y[9] location address.
y[i] for any values of i, called subscript y[i] for i
Example:
int score[7];
Assigning values to an array:- We can assign the values to an array in the following
ways.
i) We can assign values into an array while declaring the array itself.
Eg: int a[5]={23,5,6,7,10};.
ii) We can also assign the values after declaring a variable.
eg: int a[5];
a[0]=5;
a[1]=12;
11
DATA STRUCTURES @UNIT-1 [Link]
a[2]=4;
a[3]=10;
a[4]=55;
iii) We can assign the values to an array without specifying the size also. Here, the
compiler automatically assigns the size depending on the no. of values.
Eg: int a[ ]={4,8,12,16,18};
iv) We can also assign the values into an array during runtime also by using scanf.
In this we give the address of each and every element in which the value should
Be stored. This makes the statement too long.
Eg: int a[5];
scanf(“%d%d%d%d%d”,&a[0],&a[1],&a[2],&a[3],&a[4]);
The above problem can be overcome by using loops in the program while
accepting and displaying as shown in the program below.
Eg: /*to accept array values and display them*/
main()
{
int a[5], i;
clrscr();
printf(“\nEnter the values :”);
for(i=0;i<5;i++)
scanf(“%d”,&a[i]);
printf(“\nThe values are :”);
for(i=0;i<5;i++)
printf(“\n%d”,a[i]);
getch();
}
12
DATA STRUCTURES @UNIT-1 [Link]
Two dimensional arrays (2D arrays):- When we want values to be stored in the form of a
row
and column i.e., like a matrix form, we have to use 2D arrays. In this type of array, we have to
specify the no. of rows and columns required and all the elements are allocated memory in
continuous locations.
Example:
Syntax to declare a 2D arrays:
datatype array_name[row_size][column_size];
13
DATA STRUCTURES @UNIT-1 [Link]
Eg: int a[3][3];
The data type indicates the type of data, array_name indicates the name for the array, row_size
indicates the no. of rows and column_size indicates the no. of columns. Each and every element
is identified with its index number showing the row and column position. The first element
index is [0][0] and the last index is [row_size-1][column_size-1]. For the array in the example
above, the elements are identified as a[0][0], a[0][1], a[0][2], a[1][0], a[1][1] ,a[1][2], a[2][0],
a[2][1] and a[2][2]. These elements are allocated memory in continuous locations only, even
though they are identified as separate rows.
Assigning values to a 2D arrays: We can assign values to a two dimensional array same way
as
the single dimensional array as shown below.
i) We can assign the values into an array while declaring the array itself.
Eg: int a[2][2]={ 10,14,23,56}
ii) We can also assign the values by separating each row values in braces as shown below.
Eg: int a[3][3]={{3,4,7},{6,7,2},{10,12,11}};
iii) We can also values without specifying the row size also.
Eg: int a[ ][3]={2,4,6,8,10,12,14,16,18};
Here the row size is automatically taken as 3 depending on the no. of values given.
iv) We can also assign the values during the runtime by using scanf() and loops as shown
below.
Eg: int a[2][3],i,j;
for(i=0;i<2;i++)
for(j=0;j<3;j++)
scanf(“%d”,&a[i][j]);
In the above example, an array ‘a’ of size 2 rows and 3 columns is declared. The variables ‘i’
and ‘j’ are used for identifying the row index and column index respectively. We have to use
two for loops, the outer loop for row indexing and inner loop for column indexing.
14
DATA STRUCTURES @UNIT-1 [Link]
Eg: /*multiplication of matrices*/
#include<stdio.h>
#include<conio.h>
main()
{
int a[10][10],b[10][10],i,j,m,n,p,q,k,c[10][10];
clrscr();
printf("\nEnter no. of rows and columns for first matrix a");
scanf("%d%d",&m,&n);
printf("\nEnter no. of rows and columns for second matrix b");
scanf("%d%d",&p,&q);
printf("\nEnter %d elements for a",m*n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf("\nEnter %d elements for b",p*q);
for(i=0;i<p;i++)
for(j=0;j<q;j++)
scanf("%d",&b[i][j]);
if(n= =p)
{
for(i=0;i<m;i++)
{
for(j=0;j<q;j++)
{
c[i][j]=0;
for(k=0;k<q;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
15
DATA STRUCTURES @UNIT-1 [Link]
printf("\nThe product of 2 matrices is\n");
for(i=0;i<m;i++)
{
for(j=0;j<q;j++)
printf(" %d",c[i][j]);
printf("\n");
}
}
else
printf("\nCannot multiply");
getch();
}
Three-dimensional array: A 3-D Multidimensional array contains three dimensions, so it
can be considered an array of two-dimensional arrays.
MULTI DIMENSIONAL ARRAYS:- Arrays having more than one dimension are called multi
dimensional arrays. These are of 2 types and they are two dimensional arrays (2D arrays) and
three dimensional arrays (3D arrays).
Types of Array operations
Traversal: Traverse through the elements of an array.
Insertion: Inserting a new element in an array.
16
DATA STRUCTURES @UNIT-1 [Link]
Deletion: Deleting element from the array.
Searching: Search for an element in the array.
Sorting: Maintaining the order of elements in the array.
Advantages of using Arrays
Arrays allow random access to elements. This makes accessing elements by position
faster.
Arrays have better cache locality which makes a pretty big difference in performance.
Arrays represent multiple data items of the same type using a single name.
Arrays store multiple data of similar types with the same name.
Array data structures are used to implement the other data structures like linked lists,
stacks, queues, trees, graphs, etc.
Disadvantages of Array
As arrays have a fixed size, once the memory is allocated to them, it cannot be increased
or decreased, making it impossible to store extra data if required. An array of fixed size is
referred to as a static array.
Allocating less memory than required to an array leads to loss of data.
An array is homogeneous in nature so, a single array cannot store values of different data
types.
Arrays store data in contiguous memory locations, which makes deletion and insertion
very difficult to implement. This problem is overcome by implementing linked lists, which
allow elements to be accessed sequentially.
Application of Array
They are used in the implementation of other data structures such as array lists, heaps,
hash tables, vectors, and matrices.
Database records are usually implemented as arrays.
It is used in lookup tables by computer.
It is used for different sorting algorithms such as bubble sort insertion sort,
17
DATA STRUCTURES @UNIT-1 [Link]
merge sort, and quick sort.
OPERATIONS ON DATA STRUCTURES
Different operations that can be performed on the various data structures are
1. Insertion: It is used to add new items to the given list of data items.
Example: to add the details of a new student who has recently joined the course.
2. Deletion: It is used to remove a particular data items from the given collection
of data items.
Example: to delete the name of a student who has left the course.
3. Searching: It is used to locate (find) the location of one or more data items that
satisfy the given constraint. Such a data item may or may not be present in the
given collection of data items.
Example: to find the names of all the students who secured 100 marks.
4. Sorting: Data items can be arranged in some order like ascending order or
descending order depending on the type of application.
Example: Arranging the names of students in a class in an alphabetical order.
5. Traversing: Accessing (visiting) each data exactly once so that it can be
processed.
Example: printing the names of all the students in a class
6. Merging: lists of two sorted items can be combined to form a single list of sorted
data items.
18
DATA STRUCTURES @UNIT-1 [Link]
LIST ADT
List is basically the collection of elements arranged in a sequential
manner. In memory we can store the list in two ways: one way is we can store
the elements in sequential memory locations. That means we can store the list
in arrays.
The other way is we can use pointers or links to associate elements
sequentially. This is known as linked list.
LINKED LISTS
The linked list is very different type of collection from an array. Using such
lists, we can store collections of information limited only by the total amount of
memory that the OS will allow us to use. Furthermore; there is no need to specify
our needs in advance. The linked list is very flexible dynamic data structure:
items may be added to it or deleted from it at will. A programmer need not worry
about how many items a program will have to accommodate in advance. This
allows us o write robust programs which require much less maintenance.
A linked list is a linear data structure, in which the elements are not stored at
contiguous memory locations. The elements in a linked list are linked using pointers as
shown in the below image:
A linked list consists of nodes where each node contains a data field and a reference(link) to the
next node in the list.
19
DATA STRUCTURES @UNIT-1 [Link]
Why Linked List?
Arrays can be used to store linear data of similar types, but arrays have the following
limitations:
The size of the arrays is fixed: So we must know the upper limit on the number of elements
in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of
the usage.
Insertion of a new element / Deletion of a existing element in an array of elements is
expensive: The room has to be created for the new elements and to create room existing
elements have to be shifted but in Linked list if we have the head node then we can traverse
to any node through it and insert new node at the required position.
Example:
In a system, if we maintain a sorted list of IDs in an array id[] = [1000, 1010, 1050, 2000,
2040].
If we want to insert a new ID 1005, then to maintain the sorted order, we have to move all
the elements after 1000 (excluding 1000).
Deletion is also expensive with arrays until unless some special techniques are used. For
example, to delete 1010 in id[], everything after 1010 has to be moved due to this so much
work is being done which affects the efficiency of the code.
Structure of a Linked List:
Every element in a linked list is called a node and consists of two parts, the data part, and the
pointer part. The data part stores the value, while the pointer part stores the pointer pointing
to the address of the next node.
Implementations
Linked lists are implemented in C language using a structure. You can refer to the snippet
below.
Understanding the snippet below:
20
DATA STRUCTURES @UNIT-1 [Link]
1. We construct a structure named Node.
2. Define two of its members, an integer data, which holds the node's data, and a structure
pointer, next, which points to the address of the next structure node.
struct Node
int data;
struct Node *next; // Self referencing structure
};
Advantages of Linked Lists over arrays
Dynamic Array.
Ease of Insertion/Deletion.
Drawbacks of Linked Lists
Random access is not allowed. We have to access elements sequentially starting from the
first node(head node). So we cannot do a binary search with linked lists efficiently with
its default implementation.
Extra memory space for a pointer is required with each element of the list.
Not cache-friendly. Since array elements are contiguous locations, there is the locality of
reference which is not there in the case of linked lists.
It takes a lot of time in traversing and changing the pointers.
Reverse traversing is not possible in singly linked lists.
It will be confusing when we work with pointers.
Direct access to an element is not possible in a linked list as in an array by index.
Searching for an element is costly and requires O(n) time complexity.
Sorting of linked lists is very complex and costly.
No direct access to a particular element.
21
DATA STRUCTURES @UNIT-1 [Link]
Additional memory required for pointers.
Types of Linked Lists
Simple Linked List – In this type of linked list, one can move or traverse the linked list in
only one direction. where the next pointer of each node points to other nodes but the next
pointer of the last node points to NULL. It is also called “Singly Linked List”.
Doubly Linked List – In this type of linked list, one can move or traverse the linked list in
both directions (Forward and Backward)
Circular Linked List – In this type of linked list, the last node of the linked list contains
the link of the first/head node of the linked list in its next pointer.
Doubly Circular Linked List – A Doubly Circular linked list or a circular two-way linked
list is a more complex type of linked list that contains a pointer to the next as well as the
previous node in the sequence. The difference between the doubly linked and circular
doubly list is the same as that between a singly linked list and a circular linked list. The
circular doubly linked list does not contain null in the previous field of the first node.
SINGLY LINKED LIST
A singly linked list, or simply a linked list, is a linear collection of data items. The linear order is
given by means of POINTERS. These types of lists are often referred to as linear linked list.
A linked list is represented by a pointer to the first node of the linked list. The first node is
called the head of the linked list. If the linked list is empty, then the value of the head points
to NULL.
Each item in the list is called a node.
Each node of the list has two fields:
Information- contains the item being stored in the list. A Data Item (we can store integers,
strings, or any type of data).
Next address- contains the address of the next item in the list. Pointer (Or Reference) to
the next node (connects one node to another) or An address of another node.
The last node in the list contains NULL pointer to indicate that it is the end of the list.
22
DATA STRUCTURES @UNIT-1 [Link]
Conceptual view of Singly Linked List
Representation of Singly Linked Lists
Each node in a list consists of at least two parts:
We can represent a node using structures. Below is an example of a linked list node with
integer data.
Linked List can be represented as a class and a Node as a separate class. The Linked List class
contains a reference of Node class type.
The element can be inserted into the linked list by considering the following three factors
1. Allocating a node.
2. Assigning the data.
3. Adjusting the pointers.
Basic operations on Linked Lists
a. Creation.
b. Deletion
c. Insertion
d. Search.
e. Display.
Creation
It is used to create a list if the list is empty. Initially
START==NULL
Else
The existing list is pointed to start pointer and the last element is
pointed to the last pointer.
Insertion
It is used to insert an element into the list and the elements van be inserted in the list
in three 3 cases :
1. At the beginning
23
DATA STRUCTURES @UNIT-1 [Link]
2. End of the list
3. At a given position
Case 1: Insert at the beginning
temp
head is the pointer variable which contains address of the
temp->link=head; head=temp;
first node and temp contains address of new node to be inserted then sample code is
After insertion:
STEPS FOR INSERTING A NODE AT THE BEGINNING
An algorithm for inserting a node at the beginning is:
Case 1:
Step 1: check whether the list is empty or not if it is empty it display the message the list
is empty
24
DATA STRUCTURES @UNIT-1 [Link]
STACK==NULL
Else
The entered element is the first element and the last element.
Case 2:
If linked list is full then
Step 2: Allocate the memory for the new node.
Step 3: Assign the value to the data field for the new node.
Step 4: Make the link field of the new node to point to the starting node of the linked list.
Step 5: Then set the external pointer to point it to the new node.
Code for insert at the beginning:-
Void insertatbegin(int item)
{
NODE *ptr;
Ptr=NEW NODE;
Ptrinfo=item;
If(start==null)
Ptrnext=NULL;
else
ptrnect=start;
start=ptr;
}
STEPS FOR INSERTING A NODE AT THE END
An algorithm for inserting a node at the end is:
Case 1:
Step 1: check whether the list is empty or not if it is empty it display the message the list
is empty
STACK==NULL
Else
The entered element is the first element and the last element.
Case 2:
25
DATA STRUCTURES @UNIT-1 [Link]
If linked list is full then .
Step 2: Allocate the memory for the new node.
Step 3: Assign the value to the data field for the new node.
Step 4: then go on traversing until the last node is reached and then insert the new node
after the last node.
Step 4: Make the link field of the new node to point it to the null in the linked list.
Inserting end of the list
temp
head is the pointer variable which contains address of the first
node and temp contains address of new node to be inserted
then sample code is
t=head;
while(t->link!=NULL)
{
t=t->link;
}
t->link=temp;
After insertion the linked list is
Code for insert a new node at the end
Void insertst end(int item)
{
NODE *ptr,*loc;
Ptr=New Node;
Ptrinfo=item;
Ptrnext=NULL;
26
DATA STRUCTURES @UNIT-1 [Link]
If(start==null)
{
Start=ptr;
}
Else
{
Loc=start;
While(locnext!=null)
{
Loc=locnext;
Locnext=ptr;
}
}
27
DATA STRUCTURES @UNIT-1 [Link]
case 3: Insert at a position
insert node at position 3
head is the pointer variable which contains address of the first node and temp
contains address of new node to be inserted then sample code is
c=1;
while(c<pos)
{
prev=cur; cur=cur->link; c++;
}
prev->link=temp; temp->link=cur;
Code for inserting a node at a given position:-
template <class T>
void list<T>::Insert_at_pos(int pos)
{struct
node<T>*
cur,*prev,
*temp; int
c=1;
cout<
<"Ent
er data
into
node:"
;
cin>>i
tem
temp=
create
28
DATA STRUCTURES @UNIT-1 [Link]
_node(
item);
if(hea
d==N
ULL)
head=temp;
else
{
p
r
e
v
=
c
u
r
=
h
e
a
d
;
i
f
(
p
o
s
=
=
1
)
{
temp->link=head;
29
DATA STRUCTURES @UNIT-1 [Link]
head=temp;
}
else
{
while(c<pos)
{ c++;
p
r
e
v
=
c
u
r
;
c
u
r
=
c
u
r
-
>
l
i
n
k
;
}
p
r
e
v
-
>
l
i
n
k
=
t
e
m
p
;
t
e
m
p
-
>
30
DATA STRUCTURES @UNIT-1 [Link]
l
i
n
k
=
c
u
r
;
}
}
}
Delete from a Linked List:-
You can delete an element in a list from:
Beginning
End
Middle
1) Delete from Beginning:
Point head to the next node i.e. second node
temp = head
head = head->next
Make sure to free unused memory
free(temp); or delete temp;
2) Delete from End:
Point head to the previous element i.e. last second element
Change next pointer to null
struct node *end = head;
struct node *prev = NULL;
while(end->next)
{
prev = end;
end = end->next;
}
prev->next = NULL;
31
DATA STRUCTURES @UNIT-1 [Link]
Make sure to free unused memory
free(end); or delete end;
3) Delete from Middle:
Keeps track of pointer before node to delete and pointer to node
to delete
temp = head;
prev = head;
for(int i = 0; i < position; i++)
{
if(i == 0 && position == 1)
head = head->next;
free(temp)
else
{
if (i == position - 1 && temp)
{
prev->next = temp->next;
free(temp);
}
else
{
prev = temp;
if(prev == NULL) // position was greater than
number of nodes in the list
break;
temp = temp->next;
}
}
}
Iterative Method to delete an element from the linked list:
32
DATA STRUCTURES @UNIT-1 [Link]
To delete a node from the linked list, we need to do the following steps:
Find the previous node of the node to be deleted.
Change the next of the previous node.
Free memory for the node to be deleted.
Below is the implementation to delete a node from the list at some position:
// C code to delete a node from linked list
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int number;
struct Node* next;
} Node;
void Push(Node** head, int A)
{
Node* n = malloc(sizeof(Node));
n->number = A;
n->next = *head;
*head = n;
}
void deleteN(Node** head, int position)
{
Node* temp;
Node* prev;
temp = *head;
prev = *head;
for (int i = 0; i < position; i++) {
if (i == 0 && position == 1) {
*head = (*head)->next;
free(temp);
}
else {
33
DATA STRUCTURES @UNIT-1 [Link]
if (i == position - 1 && temp) {
prev->next = temp->next;
free(temp);
}
else {
prev = temp;
// Position was greater than
// number of nodes in the list
if (prev == NULL)
break;
temp = temp->next;
}
}
}
}
void printList(Node* head)
{
while (head) {
printf("[%i] [%p]->%p\n", head->number, head,
head->next);
head = head->next;
}
printf("\n\n");
}
// Drivers code
int main()
{
Node* list = malloc(sizeof(Node));
list->next = NULL;
Push(&list, 1);
34
DATA STRUCTURES @UNIT-1 [Link]
Push(&list, 2);
Push(&list, 3);
printList(list);
// Delete any position from list
deleteN(&list, 1);
printList(list);
return 0;
}
Insertion in Linked List
We have introduced Linked Lists in the previous post. We also created a simple
linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of the
linked list.
// A linked list node
struct Node
{
int data;
struct Node *next;
};
In this post, methods to insert a new node in the linked list are discussed. A node
can be added in three ways
At the front of the linked list
After a given node.
At the end of the linked list.
Add a node at the front: (4 steps process)
Approach: The new node is always added before the head of the given Linked
List. And newly added node becomes the new head of the Linked List. For
example, if the given Linked List is 10->15->20->25 and we add an item 5 at the
front, then the Linked List becomes 5->10->15->20->25. Let us call the function
that adds at the front of the list is push(). The push() must receive a pointer to the
head pointer because the push must change the head pointer to point to the new
node
35
DATA STRUCTURES @UNIT-1 [Link]
Operations on Singly linked list:
Insertion of a node
Deletions of a node
T
ra
ve
rsi
ng
th
eli
st
St
ru
ct
ur
e
of
a
n
od
36
DATA STRUCTURES @UNIT-1 [Link]
e:
M
et
ho
d
-
1:
struct node
Data link
{
int data;
struct node *link;
};
Method -2:
class node
{
public:
i
n
t
d
a
t
a
;
n
o
d
e
37
DATA STRUCTURES @UNIT-1 [Link]
*
l
i
n
k
;
};
38
DATA STRUCTURES @UNIT-1 [Link]
Deletions: Removing an element from the list, without destroying the
integrity of the list itself. To place an element from the list there are 3
cases :
1. Delete a node at beginning of the list
2. Delete a node at end of the list
3. Delete a node at a given position
Case 1: Delete a node at beginning of the list
head
head is the pointer variable which contains
address of the first node sample code is
t=head; head=head->link;
cout<<"node "<<t->data<<" Deletion is sucess"; delete(t);
head
code for deleting a node at front
template <class T>
void list<T>::delete_front()
{
struct node<T>*t;
if(head==NULL)
cout<<"List is Empty\n";
else
{ t=head;
39
DATA STRUCTURES @UNIT-1 [Link]
head=head->link;
cout<<"node "<<t-
>data<<" Deletion is
sucess"; delete(t);
}
}
Case 2. Delete a node at end of the list
head
To delete last node , find the node using following code
struct node<T>*cur,*prev; cur=prev=head;
while(cur->link!=NULL)
{prev=cur; cur=cur->link;
}
prev->link=NULL;
cout<<"node "<<cur->data<<" Deletion is sucess"; free(cur);
head
code for deleting a node at end of the list
template <class T>
void list<T>::delete_end()
{
struct
nod
e<T
>*c
ur,*
pre
v;
cur
=pr
ev=
hea
d;
if(h
40
DATA STRUCTURES @UNIT-1 [Link]
ead
==
NU
LL)
cout<<"List is Empty\n";
else
{
c
u
r
=
p
r
e
v
=
h
e
a
d
;
i
f
(
h
e
a
d
-
>
l
i
n
k
=
=
N
U
L
L
)
{
cout<<"node "<<cur-
>data<<" Deletion is
sucess"; free(cur);
head=NULL;
}
41
DATA STRUCTURES @UNIT-1 [Link]
else
{ while(cur->link!=NULL)
{
prev=cur; cur=cur->link;
}
prev->link=NULL;
cout<<"node "<<cur-
>data<<" Deletion is
sucess"; free(cur);
}
}
}
CASE 3. Delete a node at a given position
head
Delete node at position 3
head is the pointer variable which contains address of the first node.
Node to be deleted is node containing value 30.
Finding node at position 3
c=1;
while(c<pos)
{c++;
prev=cur; cur=cur->link;
}
prev cur
10 20 30 40
NULL
cur is the node to be deleted .
before deleting update links code to
prev->link=cur->link;
update links cout<<cur->data <<"is deleted successfully"; delete cur;
prev cur
10 20 30 40
NULL
42
DATA STRUCTURES @UNIT-1 [Link]
Traversing the list: Assuming we are given the pointer to the head of the
list, how do we get the end of the list.
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
v
o
i
d
l
i
s
t
<
T
>
:
:
d
i
s
p
l
a
y
(
)
{
struct node<T>*t;
if(head==NULL)
{
cout<<"List is Empty\n";
}
else
43
DATA STRUCTURES @UNIT-1 [Link]
{ t=head;
while(t!=NULL)
{
cout<<t->data<<"->"; t=t->link;
}
}
}
Dynamic Implementation of list ADT
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
#
i
n
c
l
u
d
e
<
s
t
d
l
i
b
.
h
>
t
e
m
p
44
DATA STRUCTURES @UNIT-1 [Link]
l
a
t
e
<
c
l
a
s
s
T
>
s
t
r
u
c
t
n
o
d
e
{
T data;
struct node<T> *link;
};
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
45
DATA STRUCTURES @UNIT-1 [Link]
l
i
s
t
{
int item;
s
t
r
u
c
t
n
o
d
e
<
T
>
*
h
e
a
d
;
p
u
b
l
i
c
:
list();
void display();
struct
node<T>*cr
eate_node(in
t n); void
insert_end();
void insert_front();
void
Inser
t_at_
pos(i
nt
pos);
void
delet
e_en
d();
46
DATA STRUCTURES @UNIT-1 [Link]
void delete_front();
void
Delet
e_at_
pos(i
nt
pos);
void
Node
_cou
nt();
};
47
DATA STRUCTURES @UNIT-1 [Link]
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
l
i
s
t
<
T
>
:
:
l
i
s
t
(
)
{
head=NULL;
}
t
e
m
p
l
a
t
e
<
c
l
a
s
s
48
DATA STRUCTURES @UNIT-1 [Link]
T
>
v
o
i
d
l
i
s
t
<
T
>
:
:
d
i
s
p
l
a
y
(
)
{
struct node<T>*t;
if(head==NULL)
{
cout<<"List is Empty\n";
}
else
{ t=head;
while(t!=NULL)
{
cout<<t->data<<"->"; t=t->link;
}
}
}
template <class T>
struct node<T>* list<T>::create_node(int n)
{struct node<T> *t;
t
=
n
e
w
s
t
r
49
DATA STRUCTURES @UNIT-1 [Link]
u
c
t
n
o
d
e
<
T
>
;
t
-
>
d
a
t
a
=
n
;
t
-
>
l
i
n
k
=
N
U
L
L
;
r
e
t
u
r
n
t
;
}
template <class T>
void list<T>::insert_end()
{str
uct
nod
e<T
>
*t,*
50
DATA STRUCTURES @UNIT-1 [Link]
tem
p;
int
n;
cout<<
"Enter
data
into
node:";
cin>>n;
temp=crea
te_node(n
);
if(head==
NULL)
head=temp;
else
{ t=head;
while(t-
>
l
i
n
k
!
=
N
U
L
L
)
t
=
t
-
>
l
i
n
k
;
t->link=temp;
}
}
51
DATA STRUCTURES @UNIT-1 [Link]
template <class T>
void list<T>::insert_front()
{
struct node <T>*t,*temp;
cout<<
"Enter
data
into
node:";
cin>>it
em;
temp=c
reate_n
ode(ite
m);
if(head
==NU
LL)
head=temp;
else
{
temp->link=head; head=temp;
}
}
template <class T>
void list<T>::delete_end()
{
struct
nod
e<T
>*c
ur,*
pre
v;
cur
=pr
ev=
hea
d;
if(h
ead
==
NU
LL)
cout<<"List is Empty\n";
else
{
c
u
r
=
52
DATA STRUCTURES @UNIT-1 [Link]
p
r
e
v
=
h
e
a
d
;
i
f
(
h
e
a
d
-
>
l
i
n
k
=
=
N
U
L
L
)
{
cout<<"node "<<cur->data<<"
Deletion is sucess"; free(cur);
head=NULL;
}
els
e
{ while(cur->link!=NULL)
{
prev=cur; cur=cur->link;
}
prev->link=NULL;
cout<<"node "<<cur-
>data<<" Deletion is
sucess"; free(cur);
}
}
}
template <class T>
void list<T>::delete_front()
{
struct node<T>*t;
if(head==NULL)
53
DATA STRUCTURES @UNIT-1 [Link]
cout<<"List is Empty\n";
else
{
t=head; head=head->link;
54
DATA STRUCTURES @UNIT-1 [Link]
cout<<"node "<<t-
>data<<" Deletion is
sucess"; delete(t);
}
}
template <class T>
void list<T>::Node_count()
{
s
t
r
u
c
t
n
o
d
e
<
T
>
*
t
;
i
n
t
c
=
0
;
t
=
h
e
a
d
;
i
f
(
h
e
a
d
=
=
N
55
DATA STRUCTURES @UNIT-1 [Link]
U
L
L
)
{
cout<<"List is Empty\n";
}
else
{ while(t!=NULL)
{ c++;
t=t->link;
}
cout<<"Node Count="<<c<<endl;
}
}
template <class T>
void list<T>::Insert_at_pos(int pos)
{struct
node<T>*c
ur,*prev,*te
mp; int c=1;
cout<<"Enter data into node:";
cin>>it
em
temp=c
reate_n
ode(ite
m);
if(head==NULL)
head=temp;
else
{ prev=cur=head;
if(pos==1)
{
t
e
} m
els p
e -
{ >
li
n
k
=
h
e
a
d
;
h
e
a
56
DATA STRUCTURES @UNIT-1 [Link]
d m
= p
t ;
e
while(c<pos)
{ c++;
p
r
e
v
=
c
u
r
;
c
u
r
=
c
u
r
-
>
l
i
n
k
;
}
p
r
e
v
-
>
l
i
n
k
=
t
e
m
p
;
t
e
m
p
-
>
57
DATA STRUCTURES @UNIT-1 [Link]
l
i
n
k
=
c
u
r
;
}
58
DATA STRUCTURES @UNIT-1 [Link]
}
}
template <class T>
void list<T>::Delete_at_pos(int pos)
{
struct
node<T>*
cur,*prev,
*temp; int
c=1;
if(head==NULL)
{
cout<<"List is Empty\n";
}
else
{ prev=cur=head;
if(pos==1)
{
head=head->link;
cout<<cur->data
<<"is deleted
sucesfully"; delete
cur;
}
else
{
while(c<pos)
{ c++;
p
r
e
v
=
c
u
r
;
c
u
r
=
c
u
r
-
>
l
i
n
k
59
DATA STRUCTURES @UNIT-1 [Link]
;
}
prev->link=cur->link;
cout<<cur->data
<<"is deleted
sucesfully"; delete
cur;
}
}
}
int main()
{
i
n
t
n
c
o
u
n
t
,
c
h
,
p
o
s
;
l
i
s
t
<
i
n
t
>
L
;
while(1)
{
cout<<"\n ***Operations on
Linked List***"<<endl;
cout<<"\[Link] node at
End"<<endl; cout<<"[Link]
node at Front"<<endl;
cout<<"[Link] node at
END"<<endl;
60
DATA STRUCTURES @UNIT-1 [Link]
cout<<"[Link] node at
Front"<<endl; cout<<"[Link]
at a position "<<endl;
cout<<"[Link] at a position
"<<endl; cout<<"[Link]
Count"<<endl;
cout<<"8.
Display
nodes
"<<endl;
cout<<"9.
Clear
Screen
"<<endl;
61
DATA STRUCTURES @UNIT-1 [Link]
cout<
<"10.
Exit
"<<en
dl;
cout<
<"Ent
er
Your
choic
e:";
cin>>
ch;
switch(ch)
{
case 1: L.insert_end();
b
r
e
a
k
;
c
a
s
e
2
:
L
.
i
n
s
e
r
t
_
f
r
o
n
t
(
)
;
b
r
e
a
k
;
62
DATA STRUCTURES @UNIT-1 [Link]
c
a
s
e
3
:
L
.
d
e
l
e
t
e
_
e
n
d
(
)
;
b
r
e
a
k
;
c
a
s
e
4
:
L
.
d
e
l
e
t
e
_
f
r
o
n
t
(
)
;
break;
case 5:
63
DATA STRUCTURES @UNIT-1 [Link]
c
o
ut
<
<
"
E
nt
er
p
o
si
ti
o
n
to
in
se
rt
";
ci
n
>
>
p
o
s;
L
.I
n
se
rt
_
at
_
p
o
s(
p
o
s)
;
br
e
a
k;
case 6:
c
o
ut
<
<
"
E
64
DATA STRUCTURES @UNIT-1 [Link]
nt
er
p
o
si
ti
o
n
to
in
se
rt
";
ci
n
>
>
p
o
s;
L
.
D
el
et
e
_
at
_
p
o
s(
p
o
s)
;
br
e
a
k;
case 7: L.Node_count();
b
r
e
a
k
;
c
a
s
e
65
DATA STRUCTURES @UNIT-1 [Link]
L
.
d
i
s
p
l
a
y
(
)
;
b
r
e
a
k
;
c
a
s
e
9
:
s
y
s
t
e
m
(
"
c
l
s
"
)
;
b
r
e
a
k
;
c
a
s
e
66
DATA STRUCTURES @UNIT-1 [Link]
1
0
:
e
x
i
t
(
0
)
;
default:cout<<"Invalid choice";
}
}
}
DOUBLY LINKED LIST
A singly linked list has the disadvantage that we can only traverse it in
one direction. Many applications require searching backwards and forwards
through sections of a list. A useful refinement that can be made to the singly
linked list is to create a doubly linked list. The distinction made between the
two list types is that while singly linked list have pointers going in one direction,
doubly linked list have pointer both to the next and to the previous element in
the list. The main advantage of a doubly linked list is that, they permit
traversing or searching of the list in both directions.
In this linked list each node contains three fields.
a) One to store data
b) Remaining are self referential pointers which points to previous and next nodes in
the list
prev data next
67
DATA STRUCTURES @UNIT-1 [Link]
Implementation of node using structure
Method -1:
struct node
{
int data;
s
t
r
u
c
t
n
o
d
e
*
p
r
e
v
;
s
t
r
u
c
t
n
o
d
e
n
e
x
t
;
};
Implementation of node using class
Method -2:
class node
{
68
DATA STRUCTURES @UNIT-1 [Link]
public:
i
n
t
d
a
t
a
;
n
o
d
e
*
p
r
e
v
;
n
o
d
e
n
e
x
t
;
};
NULL 10 20 30 NULL
Operations on Doubly linked list:
Insertion of a node
Deletions of a node
Traversing the list
Doubly linked list ADT:
t
e
m
p
l
a
t
69
DATA STRUCTURES @UNIT-1 [Link]
<
c
l
a
s
s
T
>
c
l
a
s
s
d
l
i
s
t
{
int data;
struct dnode<T>*head;
public:
dlist()
{
head=NULL;
}
void display();
struct
dnode<T>*cre
ate_dnode(int
n); void
insert_end();
v
o
i
d
i
n
s
e
r
t
_
f
r
o
n
t
70
DATA STRUCTURES @UNIT-1 [Link]
(
)
;
v
o
i
d
d
e
l
e
t
e
_
e
n
d
(
)
;
v
o
i
d
d
e
l
e
t
e
_
f
r
o
n
t
(
)
;
v
o
i
d
d
n
o
d
e
71
DATA STRUCTURES @UNIT-1 [Link]
_
c
o
u
n
t
(
)
;
72
DATA STRUCTURES @UNIT-1 [Link]
void
Insert
_at_p
os(int
pos);
void
Delet
e_at_
pos(i
nt
pos);
};
Insertions: To place an elements in the list there are 3 cases
1. At the beginning
2. End of the list
3. At a given position
case 1:Insert at the beginning
head
NULL 10 20 30 NULL
head is the pointer variable which contains address of the first node and temp
NULL
contains address of new
temp 40inserted then
node to be NULL
sample code is
temp->next=head; head->prev=temp; head=temp;
head
40 10 20 30 NULL
Code for insert front:-
template <class T>
void DLL<T>::insert_front()
{
struct dnode
<T>*t,
*temp;
cout<<
"Enter
data
into
node:";
73
DATA STRUCTURES @UNIT-1 [Link]
cin>>d
ata;
temp=c
reate_d
node(da
ta);
if(head
==NUL
L)
head=temp;
else
{ temp->next=head; head-
>
p
r
e
v
=
t
e
m
p
;
h
e
a
d
=
t
e
m
p
;
}
}
74
DATA STRUCTURES @UNIT-1 [Link]
case 2:Inserting end of the list
head
NULL 10 20 30 NULL
NULL 40 NULL
temp
head is the pointer variable which contains address of the first node and
temp contains address of new node to be inserted then sample code is
t=head;
while(t->next!=NULL) t=t->next;
t->next=temp; temp->prev=t;
head
NULL 10 20 30 NULL
NULL 40 NULL
Code to insert a node at End:-
template <class T>
void DLL<T>::insert_end()
{
stru
ct
dno
de<
T>
*t,*
tem
p;
int
n;
cout<<"
Enter
data into
dnode:";
cin>>n;
t
75
DATA STRUCTURES @UNIT-1 [Link]
e
m
p
=
c
r
e
a
t
e
_
d
n
o
d
e
(
n
)
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
head=temp;
else
{ t=head;
while(t-
>
n
e
x
t
!
=
N
U
L
L
)
t
=
t
76
DATA STRUCTURES @UNIT-1 [Link]
-
>
n
e
x
t
;
77
DATA STRUCTURES @UNIT-1 [Link]
t
-
>
n
e
x
t
=
t
e
m
p
;
t
e
m
p
-
>
p
r
e
v
=
t
;
}
}
case 3:Inserting at a give position
head
NULL 10 20 30 NULL
temp
40
insert 40 at position 2
head is the pointer variable which contains address of the first node and temp
contains address of new node to be inserted then sample code is
while(count<pos)
{count++; pr=cr;
cr=cr->next;
}
pr->next=temp; temp->prev=pr; temp->next=cr; cr->prev=temp;
78
DATA STRUCTURES @UNIT-1 [Link]
head pr cr
NULL 10 20 30 NULL
NULL 40 NULL
temp
79
DATA STRUCTURES @UNIT-1 [Link]
Code to insert a node at a position
template <class T>
void dlist<T>::Insert_at_pos(int pos)
{
struct
dnode<
T>*cr,*
pr,*tem
p; int
count=1
;
cout<<"
Enter
data into
dnode:";
cin>>dat
a;
temp=cr
eate_dno
de(data);
display()
;
if(head==NULL)
{//when list is empty
head=temp;
}
else
{
pr=cr=head; if(pos==1)
{
//inserting at pos=1 temp->next=head; head=temp;
}
else
{
while(count<pos)
count++; pr=cr;
cr=cr->next;
}
p
r
-
>
n
e
x
t
=
t
e
m
80
DATA STRUCTURES @UNIT-1 [Link]
p
;
t
e
m
p
-
>
p
r
e
v
=
p
r
;
t
e
m
p
-
>
n
e
x
t
=
c
r
;
c
r
-
>
p
r
e
v
=
t
e
m
p
;
}
}
}
Deletions: Removing an element from the list, without destroying the
integrity of the list itself. To place an element from the list there are 3
81
DATA STRUCTURES @UNIT-1 [Link]
cases :
1. Delete a node at beginning of the list
2. Delete a node at end of the list
3. Delete a node at a given position
Case 1: Delete a node at beginning of the list
head
NULL 10 20 30 NULL
82
DATA STRUCTURES @UNIT-1 [Link]
head is the pointer variable which contains
address of the first node sample code is
t=head; head=head->next;
head->prev=NULL;
cout<<"dnode "<<t->data<<" Deletion is sucess"; delete(t);
head
NULL 10 NULL 20 30 NULL
code for deleting a node at front
template <class T>
void dlist<T>:: delete_front()
{struct dnode<T>*t;
if(head==NULL)
cout<<"List is Empty\n";
else
{
t=head; head=head->next;
head->prev=NULL;
cout<<"dnode "<<t-
>data<<" Deletion is
sucess"; delete(t);
}
}
Case 2. Delete a node at end of the list
To deleted the last node find the last node. find the node using following code
struct dnode<T>*pr,*cr;
pr=cr=head; while(cr->next!=NULL)
{pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode "<<cr->data<<" Deletion is sucess"; delete(cr);
83
DATA STRUCTURES @UNIT-1 [Link]
head
NULL 10 20 NULL 30 NULL
pr cr
code for deleting a node at end of the list
template <class T>
void dlist<T>::delete_end()
{
struct dnode<T>*pr,*cr;
p
r
=
c
r
=
h
e
a
d
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
cout<<"List is Empty\n";
else
{ cr=pr=head;
if(head->next==NULL)
{
cout<<"dnode "<<cr->data<<"
Deletion is sucess"; delete(cr);
head=NULL;
}
els
e
{ while(cr->next!=NULL)
84
DATA STRUCTURES @UNIT-1 [Link]
{ pr=cr;
cr=cr->next;
}
pr->next=NULL;
cout<<"dnode "<<cr-
>data<<" Deletion is
sucess"; delete(cr);
}
}
}
CASE 3. Delete a node at a given position
head
NULL
Delete 10
node at position 2 30 20 NULL
head is the pointer variable which contains address of the first node.
Node to be deleted is node containing value 30.
Finding node at position 2.
85
DATA STRUCTURES @UNIT-1 [Link]
while(count<pos)
{pr=cr;
cr=cr->next; count++;
}
pr->next=cr->next; cr->next->prev=pr;
head
NULL 10 30 20 NULL
pr cr
code for deleting a node at a position
template <class T>
void dlist<T>::Delete_at_pos(int pos)
{
struct
dnode<
T>*cr,*
pr,*tem
p; int
count=1
;
d
i
s
p
l
a
y
(
)
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
86
DATA STRUCTURES @UNIT-1 [Link]
{
cout<<"List is Empty\n";
}
else
{ pr=cr=head;
if(pos==1)
{
hea
d=h
ead
-
} >ne
els xt;
e hea
{ d-
>pr
ev=
NU
LL;
cout<<cr->data <<"is
deleted sucesfully";
delete cr;
while(count<pos)
count++; pr=cr;
cr=cr->next;
}
p
r
-
>
n
e
x
t
=
c
r
-
>
n
e
x
t
;
c
r
-
>
n
87
DATA STRUCTURES @UNIT-1 [Link]
e
x
t
-
>
p
r
e
v
=
p
r
;
cout<<cr->data
<<"is deleted
sucesfully"; delete
cr;
}
}
}
88
DATA STRUCTURES @UNIT-1 [Link]
Dynamic Implementation of Doubly linked list ADT
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
s
t
r
u
c
t
d
n
89
DATA STRUCTURES @UNIT-1 [Link]
o
d
e
{
T data;
s
t
r
u
c
t
d
n
o
d
e
<
T
>
*
p
r
e
v
;
s
t
r
u
c
t
d
n
o
d
e
<
T
>
*
n
e
x
t
;
};
t
e
m
p
l
a
90
DATA STRUCTURES @UNIT-1 [Link]
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
d
l
i
s
t
{
int data;
struct dnode<T>*head;
pu
bl dlist();
ic: struct
dnode<T>*create_
dnode(int n); void
insert_front();
void insert_end();
void
Insert_at
_pos(int
pos);
void
delete_fr
}; ont();
void delete_end();
void
Delete_at
_pos(int
pos); void
dnode_co
unt();
void display();
t
e
m
p
91
DATA STRUCTURES @UNIT-1 [Link]
l
a
t
e
<
c
l
a
s
s
T
>
d
l
i
s
t
<
T
>
:
:
d
l
i
s
t
(
)
{
head=NULL;
}
template <class T>
struct dnode<T>*dlist<T>::create_dnode(int n)
{
struct dnode<T> *t;
t
=
n
e
w
s
t
r
u
c
t
d
92
DATA STRUCTURES @UNIT-1 [Link]
n
o
d
e
<
T
>
;
t
-
>
d
a
t
a
=
n
;
t
-
>
n
e
x
t
=
N
U
L
L
;
t
-
>
p
r
e
v
=
N
U
L
L
;
return t;
}
template <class T>
void dlist<T>::insert_front()
{
struct dnode
<T>*t,*t
emp;
cout<<"
93
DATA STRUCTURES @UNIT-1 [Link]
Enter
data into
dnode:";
94
DATA STRUCTURES @UNIT-1 [Link]
cin>>data
;
temp=crea
te_dnode(
data);
if(head==
NULL)
head=temp;
else
{ temp->next=head; head-
>
p
r
e
v
=
t
e
m
p
;
h
e
a
d
=
t
e
m
p
;
}
}
template <class T>
void dlist<T>::insert_end()
{
stru
ct
dno
de<
T>
*t,*
tem
p;
int
n;
cout<<"
Enter
data into
dnode:";
cin>>n;
temp=crea
95
DATA STRUCTURES @UNIT-1 [Link]
te_dnode(
n);
if(head==
NULL)
head=temp;
else
{ t=head;
while(t-
>
n
e
x
t
!
=
N
U
L
L
)
t
=
t
-
>
n
e
x
t
;
t
-
>
n
e
x
t
=
t
e
m
p
;
t
e
m
p
-
>
p
r
e
96
DATA STRUCTURES @UNIT-1 [Link]
v
=
t
;
}
}
template <class T>
void dlist<T>::Insert_at_pos(int pos)
{
struct
dnode<
T>*cr,*
pr,*tem
p; int
count=1
;
cout<<"
Enter
data into
dnode:";
cin>>dat
a;
temp=cr
eate_dno
de(data);
display()
;
if(head==NULL)
{//when list is empty
head=temp;
}
else
{
pr=cr=head; if(pos==1)
{
//inserting at pos=1 temp->next=head; head=temp;
}
else
97
DATA STRUCTURES @UNIT-1 [Link]
{
while(count<pos)
{
count++; pr=cr;
cr=cr->next;
}
p
r
-
>
n
e
x
t
=
t
e
m
p
;
t
e
m
p
-
>
p
r
e
v
=
p
r
;
t
e
m
p
-
>
n
e
x
t
=
c
r
;
c
r
98
DATA STRUCTURES @UNIT-1 [Link]
-
>
p
r
e
v
=
t
e
m
p
;
}
}
}
template <class T>
void dlist<T>:: delete_front()
{struct dnode<T>*t;
if(head==NULL)
cout<<"List is Empty\n";
else
{
display(); t=head;
h
e
a
d
=
h
e
a
d
-
>
n
e
x
t
;
h
e
a
d
-
>
p
r
e
v
=
N
99
DATA STRUCTURES @UNIT-1 [Link]
U
L
L
;
cout<<"dnode "<<t-
>data<<" Deletion is
sucess"; delete(t);
}
}
template <class T>
void dlist<T>::delete_end()
{
struct dnode<T>*pr,*cr;
p
r
=
c
r
=
h
e
a
d
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
cout<<"List is Empty\n";
else
{ cr=pr=head;
if(head->next==NULL)
{
cout<<"dnode "<<cr->data<<"
Deletion is sucess"; delete(cr);
head=NULL;
}
els
e
{ while(cr->next!=NULL)
{ pr=cr;
cr=cr->next;
100
DATA STRUCTURES @UNIT-1 [Link]
}
pr->next=NULL;
cout<<"dnode "<<cr-
>data<<" Deletion is
sucess"; delete(cr);
101
DATA STRUCTURES @UNIT-1 [Link]
}
}
}
template <class T>
void dlist<T>::Delete_at_pos(int pos)
{
struct
dnode<
T>*cr,*
pr,*tem
p; int
count=1
;
d
i
s
p
l
a
y
(
)
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
{
cout<<"List is Empty\n";
}
else
{ pr=cr=head;
if(pos==1)
{
hea
d=h
ead
-
} >ne
els xt;
e hea
{ d-
102
DATA STRUCTURES @UNIT-1 [Link]
> cout<<cr->data <<"is
p deleted sucesfully";
r delete cr;
e
v
=
N while(count<pos)
U
L count++; pr=cr;
L cr=cr->next;
;
}
p
r
-
>
n
e
x
t
=
c
r
-
>
n
e
x
t
;
c
r
-
>
n
e
x
t
-
>
p
r
e
v
=
p
r
;
cout<<cr->data
<<"is deleted
sucesfully"; delete
cr;
}
103
DATA STRUCTURES @UNIT-1 [Link]
}
}
template <class T>
void dlist<T>::dnode_count()
{
s
t
r
u
c
t
d
n
o
d
e
<
T
>
*
t
;
i
n
t
c
o
u
n
t
=
0
;
d
i
s
p
l
a
y
(
)
;
t
=
h
e
a
d
;
104
DATA STRUCTURES @UNIT-1 [Link]
if(head==NULL)
cout<<"List is Empty\n";
else
{ while(t!=NULL)
{
count++; t=t->next;
}
cout<<"node count is "<<count;
105
DATA STRUCTURES @UNIT-1 [Link]
}
}
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
v
o
i
d
d
li
s
t
<
T
>
::
d
i
s
p
l
a
y
(
)
{
s
t
r
u
c
t
d
n
o
d
e
<
T
106
DATA STRUCTURES @UNIT-1 [Link]
>
*
t
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
{
cout<<"List is Empty\n";
}
else
{ cout<<"Nodes in
the linked list are
...\n"; t=head;
while(t!=NULL)
{
c
o
u
t
<
<
t
-
>
d
a
t
a
<
<
"
<
=
>
"
;
t
=
t
-
107
DATA STRUCTURES @UNIT-1 [Link]
>
n
e
x
t
;
}
}
}
int main()
{
i
n
t
c
h
,
p
o
s
;
d
l
i
s
t
<
i
n
t
>
D
L
;
while(1)
{
cout<<"\n ***Operations on
Doubly List***"<<endl;
cout<<"\[Link] dnode at
End"<<endl; cout<<"[Link]
dnode at Front"<<endl;
cout<<"[Link] dnode at
END"<<endl;
cout<<"[Link] dnode at
Front"<<endl;
cout<<"[Link] nodes
"<<endl;
cout<<"[Link]
Nodes"<<endl;
cout<<"[Link]
108
DATA STRUCTURES @UNIT-1 [Link]
at a position
"<<endl;
cout<<"[Link]
e at a position
"<<endl;
cout<<"[Link]
"<<endl;
cout<<"[Link]
r Screen
"<<endl;
cout<<"Enter
Your choice:";
c
i
n
>
>
c
h
;
s
w
i
t
c
h
(
c
h
)
{
case 1: DL.insert_end();
b
re
ak
;
ca
se
2:
D
L.
in
se
rt_
fr
on
t()
;
b
r
e
a
k
109
DATA STRUCTURES @UNIT-1 [Link]
;
c
a
s
e
3
:
D
L
.
d
e
l
e
t
e
_
e
n
d
(
)
;
b
re
ak
;
ca
se
4:
D
L.
de
let
e_
fr
on
t()
;
b
re
ak
;
ca
se
5:/
/di
sp
la
y
co
nt
en
ts
110
DATA STRUCTURES @UNIT-1 [Link]
D
L
.
d
i
s
p
l
a
y
(
)
;
b
r
e
a
k
;
111
DATA STRUCTURES @UNIT-1 [Link]
case 6: DL.dnode_count();
break;
case 7:
c
o
ut
<
<
"
E
nt
er
p
o
si
ti
o
n
to
in
se
rt
";
ci
n
>
>
p
o
s;
D
L
.I
n
se
rt
_
at
_
p
o
s(
p
o
s)
;
br
e
a
k;
case 8:
co
ut
112
DATA STRUCTURES @UNIT-1 [Link]
<<
"E
nte
r
po
siti
on
to
De
let
e";
cin
>>
po
s;
D
L.
De
let
e_
at_
po
s(p
os)
;
br
ea
k;
case 9:exit(0);
case 10:system("cls");
bre
ak;
default:cout<<"Inv
alid choice";
}
}
}
CIRCULARLY LINKED LIST
A circularly linked list, or simply circular list, is a linked list in which the last
node is always points to the first node. This type of list can be build just by
replacing the NULL pointer at the end of the list with a pointer which points to
the first node. There is no first or last node in the circular list.
Advantages:
Any node can be traversed starting from any other node in the list.
There is no need of NULL pointer to signal the end of the list and
hence, all pointers contain valid addresses.
In contrast to singly linked list, deletion operation in circular list is
simplified as the search for the previous node of an element to be
deleted can be started from that item itself.
113
DATA STRUCTURES @UNIT-1 [Link]
head
Dynamic Implementation of Circular linked list ADT
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
#
i
n
c
l
u
d
e
<
s
t
d
l
i
b
.
h
>
t
e
m
114
DATA STRUCTURES @UNIT-1 [Link]
p
l
a
t
e
<
c
l
a
s
s
T
>
s
t
r
u
c
t
c
n
o
d
e
{
T data;
struct cnode<T> *link;
};
//Code fot
circular
linked List
ADT
template
<class T>
115
DATA STRUCTURES @UNIT-1 [Link]
class clist
{
int data;
s
t
r
u
c
t
c
n
o
d
e
<
T
>
*
h
e
a
d
;
p
u
b
l
i
c
:
clist();
struct
cnode<T>*
create_cnode(i
nt n); void
display();
v
o
i
d
i
n
s
e
r
t
_
e
n
d
116
DATA STRUCTURES @UNIT-1 [Link]
(
)
;
v
o
i
d
i
n
s
e
r
t
_
f
r
o
n
t
(
)
;
v
o
i
d
d
e
l
e
t
e
_
e
n
d
(
)
;
v
o
i
d
d
e
l
e
t
117
DATA STRUCTURES @UNIT-1 [Link]
e
_
f
r
o
n
t
(
)
;
v
o
i
d
c
n
o
d
e
_
c
o
u
n
t
(
)
;
};
//
code
for
defau
t
const
ructo
r
templ
ate
<clas
s T>
clist<
T>::c
list()
{
head=NULL;
}
//code to
display
elements in
118
DATA STRUCTURES @UNIT-1 [Link]
the list
template
<class T>
void clist<T>::display()
{
s
t
r
u
c
t
c
n
o
d
e
<
T
>
*
t
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
{
cout<<"clist is Empty\n";
}
else
{ t=head;
if(t->link==head)
cout<<t->data<<"->";
else
{
c
o
u
t
<
<
119
DATA STRUCTURES @UNIT-1 [Link]
t
-
>
d
a
t
a
<
<
"
-
>
"
;
t
=
t
-
>
l
i
n
k
;
w
h
i
l
e
(
t
!
=
h
e
a
d
)
{
c
o
u
t
<
<
t
-
>
d
a
t
a
120
DATA STRUCTURES @UNIT-1 [Link]
<
<
"
-
>
"
;
t
=
t
-
>
l
i
n
k
;
}
}
}
}
/
/
C
o
d
e
t
o
c
r
e
a
t
e
n
o
d
e
t
e
m
p
l
a
t
e
121
DATA STRUCTURES @UNIT-1 [Link]
<
c
l
a
s
s
T
>
struct cnode<T>* clist<T>::create_cnode(int n)
122
DATA STRUCTURES @UNIT-1 [Link]
{
struct cnode<T> *t;
t
=
n
e
w
s
t
r
u
c
t
c
n
o
d
e
<
T
>
;
t
-
>
d
a
t
a
=
n
;
t
-
>
l
i
n
k
=
N
U
L
L
;
r
e
t
u
r
n
t
123
DATA STRUCTURES @UNIT-1 [Link]
;
}
//Code
to insert
node at
the end
template
<class
T>
void clist<T>::insert_end()
{
s
t
r
u
c
t
c
n
o
d
e
<
T
>
*
t
;
s
t
r
u
c
t
c
n
o
d
e
<
T
>
*
t
e
m
p
;
i
n
t
n
;
cout<<"
124
DATA STRUCTURES @UNIT-1 [Link]
Enter
data into
cnode:";
cin>>n;
temp=crea
te_cnode(
n);
if(head==
NULL)
{
head=temp;
temp->link=temp;
}
e
ls
e t=head;
{ if(t->link==head)// list containing only one node
{
t
-
} >
els l
e i
{ n
k
=
t
e
m
p
;
t
e
m
p
-
>
l
i
n
k
=
t
;
while(t->link!=head)
{
t=t->link;
}
t
-
>
125
DATA STRUCTURES @UNIT-1 [Link]
l
i
n
k
=
t
e
m
p
;
t
e
m
p
-
>
l
i
n
k
=
h
e
a
d
;
}
}
cout<<"Node inerted"<<endl;
}
//
Code
to
insert
node
at
front
templ
ate
<clas
s T>
void clist<T>::insert_front()
{
s
t
r
u
c
t
c
n
o
126
DATA STRUCTURES @UNIT-1 [Link]
d
e
<
T
>
*
t
;
s
t
r
u
c
t
c
n
o
d
e
<
T
>
*
t
e
m
p
;
cout<<"
Enter
data into
cnode:";
cin>>dat
a;
127
DATA STRUCTURES @UNIT-1 [Link]
temp=create_cno
de(data);
if(head==NULL)
{
head=temp;
temp->link=temp;
}
e
ls
e t=head;
{ if(t->link==head)
{
t-
>
} l
els i
e n
{ k
=
t
e
m
p
;
t
e
m
p
-
>
l
i
n
k
=
t
;
//code
to find
last
node
while(
t-
>link!
=head
)
{
t=t->link;
}
128
DATA STRUCTURES @UNIT-1 [Link]
t->link=temp;
//linking last and
first node temp-
>link=head;
head=temp;
}
}
cout<<"Node inserted \n";
}
//
Code
to
delet
e
node
at
end
temp
late
<clas
s T>
void clist<T>::delete_end()
{
struct
cnod
e<T
>*cu
r,*pr
ev;
cur=
prev
=hea
d;
if(he
ad==
NUL
L)
cout<<"clist is Empty\n";
else
{
cur=prev=head; if(cur->link==head)
{
cout<<"cnode "<<cur->data<<"
Deletion is sucess"; free(cur);
head=NULL;
}
els
e
{ while(cur->link!=head)
{
prev=cur; cur=cur->link;
129
DATA STRUCTURES @UNIT-1 [Link]
130
DATA STRUCTURES @UNIT-1 [Link]
//prev=cur;
//cur=cur->link;
prev->link=head;//points to head
cout<<"cnode "<<cur-
>data<<" Deletion is
sucess"; free(cur);
}
}
}
//
Code
to
delete
node
at
front
templ
ate
<class
T>
void clist<T>::delete_front()
{
struct
cn
od
e<
T>
*t,
*te
mp
;
if(
hea
d=
=N
UL
L)
cout<<"circular list is Empty\n";
else
{ t=head;
/
/
h
e
a
d
=
h
e
a
d
-
>
131
DATA STRUCTURES @UNIT-1 [Link]
l
i
n
k
;
i
f
(
t
-
>
l
i
n
k
=
=
h
e
a
d
)
{
head=NULL;
cout<<"cnode "<<t->data<<"
Deletion is sucess"; delete(t);
}
els
e
{
//code to find last node
while(t->link!=head)
{
t=t->link;
}
temp=head;
t->link=head->link;
//linking last and first node
cout<<"cnode "<<temp->data<<"
Deletion is sucess"; head=head-
>link;
delete(temp);
}
}
}
//Code to count nodes in
the circular linked list
template <class T>
void clist<T>::cnode_count()
{
s
t
132
DATA STRUCTURES @UNIT-1 [Link]
r
u
c
t
c
n
o
d
e
<
T
>
*
t
;
i
n
t
c
=
0
;
t
=
h
e
a
d
;
i
f
(
h
e
a
d
=
=
N
U
L
L
)
{
cout<<"circular list is Empty\n";
133
DATA STRUCTURES @UNIT-1 [Link]
else
{
t=t->link; c++;
while(t!=head)
{ c++;
t=t->link;
}
cout<<"Node Count="<<c;
}
int main()
{
i
n
t
c
h
,
p
o
s
;
c
l
i
s
t
<
i
n
t
>
L
;
while(1)
{
cout<<"\n ***Operations on Circular
Linked clist***"<<endl; cout<<"\
[Link] cnode at End"<<endl;
cout<<"[Link]
Cnode at
Front"<<endl;
cout<<"[Link]
Cnode at
END"<<endl;
cout<<"[Link]
Cnode at
134
DATA STRUCTURES @UNIT-1 [Link]
Front"<<endl;
cout<<"[Link]
Nodes "<<endl;
cout<<"[Link]
Count"<<endl;
cout<<"[Link]
"<<endl;
cout<<"8
.Clear
Screen
"<<endl;
cout<<"
Enter
Your
choice:";
cin>>ch;
switch(ch)
{
case 1: L.insert_end();
b
r
e
a
k
;
c
a
s
e
2
:
L
.
i
n
s
e
r
t
_
f
r
o
n
t
(
)
;
b
re
ak
;
135
DATA STRUCTURES @UNIT-1 [Link]
ca
se
3:
L.
de
let
e_
en
d(
);
b
re
ak
;
ca
se
4:
L.
de
let
e_
fr
on
t()
;
b
re
ak
;
ca
se
5:/
/di
sp
la
y
co
nt
en
ts
L
.
d
i
s
p
l
a
y
(
)
;
b
136
DATA STRUCTURES @UNIT-1 [Link]
r
e
a
k
;
case 6: L.cnode_count();
break;
case 7:exit(0);
case 8:system("cls");
bre
ak;
default:cout<<"Inv
alid choice";
}
}
}
137
Stack: Stack ADT, array and linked list implementation, Applications- expression conversion and evalua
list implementation. Priority Queue, heaps.
STACK ADT:- A Stack is a linear data structure where insertion and
deletion of items takes place at one end called top of the stack. A Stack is
defined as a data structure which operates on a last-in first-out basis. So it is
also is referred as Last-in First-out( LIFO).
Stack uses a single index or pointer to keep track of the
information in the stack. The basic operations associated with the stack
are:
a) push(insert) an item onto the stack.
b) pop(remove) an item from the stack.
The general terminology associated with the stack is as follows:
A stack pointer keeps track of the current position on the stack.
When an element is placed on the stack, it is said to be pushed on the stack.
When an object is removed from the stack, it is said to be popped off the
stack. Two additional terms almost always used with stacks are overflow,
which occurs when we try to push more information on a stack that it can
hold, and underflow, which occurs when we try to pop an item off a stack
which is empty.
Pushing items onto the stack:
Assume that the array elements begin at 0 ( because the array subscript starts from 0)
and the maximum elements that can be placed in stack is max. The stack
pointer, top, is considered to be pointing to the top element of the stack. A
push operation thus involves adjusting the stack pointer to point to next free
slot and then copying data into that slot of the stack. Initially the top is
initialized to -1.
//code to push
an element on
to stack;
template<class
T>
void stack<T>::push()
{
if(top==max-1)
cout<<"Stack Overflow...\n";
e
ls
e
{
}
138
}
cout<<"Enter an
element to be
pushed:"; top++;
c
i
n
>
>
d
a
t
a
;
s
t
k
[
t
o
p
]
=
d
a
t
a
;
cout<<"Pushed Sucesfully....\n";
139
Popping an element from stack:
To remove an item, first extract the data from top position in the
stack and then decrement the stack pointer, top.
//code to remove
an element from
stack
template<class
T>
void stack<T>::pop()
{
if(top= =-1)
cout<<"Stack is Underflow";
els
e
{ d
a
t
a
} =
} s
t
k
[
t
o
p
]
;
t
o
p
-
-
;
cout<<data<<" is poped Sucesfully.....\n";
Static implementation of Stack ADT
#
i
140
n
c
l
u
d
e
<
s
t
d
l
i
b
.
h
>
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
#
d
e
f
i
n
e
m
a
x
141
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
s
t
a
c
k
{
private:
int top;
T stk[max],data;
p
us
bt
l a
i c
ck
: (
)
;
v
}o
; i
d
p
u
s
h
(
142
)
; p
o
v p
o (
i )
d ;
void display();
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
s
t
a
c
k
<
T
>
:
:
s
t
a
c
k
(
)
{
top=-1;
143
}
//code to push
an element on
to stack;
template<class
T>
void stack<T>::push()
{
if(top==max-1)
cout<<"Stack Overflow...\n";
els
e
{ cout<<"Enter an
element to be pushed:";
top++;
c
i
n
} >
} >
d
a
t
a
;
s
t
k
[
t
o
p
]
=
d
a
t
a
;
cout<<"Pushed Sucesfully....\n";
//code to remove
an element from
stack
template<class
T>
void stack<T>::pop()
{
if(top==-1)
cout<<"Stack is Underflow";
els
e
{
144
}
}
d
a
t
a
=
s
t
k
[
t
o
p
]
;
t
o
p
-
-
;
cout<<data<<" is poped Sucesfully.....\n";
//code to
display
stack
elements
template
<class
T>
void stack<T>::display()
{
if(top==-1)
cout<<"Stack Under Flow";
else
{ cout<<"Elements in the Stack are.....\n";
for(int i=top;i>-1;i--)
{
cout<<<<stk[i]<<"\n";
}
}
}
int main()
{
i
n
t
c
h
o
i
145
c
e
;
s
t
a
c
k
<
i
n
t
>
s
t
;
while(1)
{
cout<<"\n*****Menu for
Stack operations*****\n";
cout<<"[Link]\[Link]\
[Link]\[Link]\n";
146
c
o
u
t
<
<
"
E
n
t
e
r
C
h
o
i
c
e
:
"
;
c
i
n
>
>
c
h
o
i
c
e
;
s
w
i
t
c
h
(
c
h
o
i
c
e
)
{
case 1: [Link]();
b
r
e
a
k
147
;
c
a
s
e
2
:
s
t
.
p
o
p
(
)
;
b
r
e
a
k
;
c
a
s
e
3
:
s
t
.
d
i
s
p
l
a
y
(
)
;
break;
tput:
}
}
ou
148
case 4: exit(0); default:cout<<"Invalid choice...Try again...\n";
}
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:1
Enter an
element to
be
pushed:11
Pushed
Sucesfully
....
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:1
Enter an
element to
be
pushed:22
Pushed
Sucesfully
....
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:1
Enter an
element to
be
pushed:44
Pushed
Sucesfully
....
*****Menu for
Stack
operations****
* [Link]
2. POP
149
3. DISPLAY
4. EXIT
E
n
t
e
r
C
h
o
i
c
e
:
1
E
n
t
e
r
C
h
o
i
c
e
:
1
Enter
an
item to
be
pushed
:55
Pushed
Sucesf
ully....
150
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
E
n
t
e
r
C
h
o
i
c
e
:
1
S
t
a
c
k
O
v
e
r
f
l
o
w
.
.
.
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:2
55 is poped Sucesfully....
*****Menu for
Stack
operations****
151
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:3
Elements in the Stack are....
44
22
11
*****Menu for
Stack
operations****
* [Link]
2. POP
3. DISPLAY
4. EXIT
Enter Choice:4
Dynamic implementation of Stack ADT
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
t
e
m
p
l
a
t
e
152
<
c
l
a
s
s
T
>
s
t
r
u
c
t
n
o
d
e
{
T data;
struct node<T> *link;
};
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
s
t
a
c
153
k
{
int data;
struct node<T>*top;
154
p
u
b
l top=NULL;
i
c
:
s
t
a
c
k
(
)
{
}
v
o
i
d
d
i
s
p
l
a
y
(
)
;
v
o
i
d
p
u
s
h
(
)
;
v
o
i
d
p
o
155
p
(
)
;
};
template <class T>
void stack<T>::display()
{
struct node<T>*t;
if(top==NULL)
{
cout<<"stack is Empty\n";
}
else
{
t=top; while(t!=NULL)
{
cout<<"|"
<<t-
>data<<"
|"<<endl;
t=t-
>link;
}
}
}
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
v
o
i
d
s
156
t
a
c
k
<
T
>
:
:
p
u
s
h
(
)
{
struct node <T>*t,*temp;
cout<<
"Enter
data
into
node:";
cin>>d
ata;
tem
p=n
ew
stru
ct
nod
e<T
>;
tem
p-
>dat
a=d
ata;
t
e
m
p
-
>
l
i
n
k
=
N
U
L
L
;
157
i
f
(
t
o
p
=
=
N
U
L
L
)
top=temp;
else
{
temp->link=top; top=temp;
}
}
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
v
o
i
d
s
t
a
c
k
<
T
>
:
158
:
p
o
p
(
)
{
struct node<T>*t;
if(top==NULL)
cout<<"stack is Empty\n";
159
else
{ t=top;
top=top->link;
cout<<"node "<<t-
>data<<" Deletion is
sucess"; delete(t);
}
}
int main()
{
int ch;
stack <int> st;
while(1)
{
cout<<"\n ***Operations on
Dynamic stack***"<<endl;
cout<<"\[Link]"<<endl;
cout<
<"2.P
OP"<
<endl
;
cout<
<"3.D
isplay
"<<en
dl;
cout<
<"4.E
xit
"<<en
dl;
cout<
<"Ent
er
Your
choic
e:";
cin>>
ch;
switch(ch)
{
case 1: [Link]();
b
r
e
a
k
;
c
a
160
s
e
2
:
s
t
.
p
o
p
(
)
;
b
r
e
a
k
;
c
a
s
e
3
:
s
t
.
d
i
s
p
l
a
y
(
)
;
;
break;
case
4:exit(0);
default:cou
t<<"Invali
d choice";
}
}
}
161
Applications of Stack:
1. Stacks are used in conversion of infix to postfix expression.
2. Stacks are also used in evaluation of postfix expression.
3. Stacks are used to implement recursive procedures.
4. Stacks are used in compilers.
5. Reverse String
An arithmetic expression can be written in three different but
equivalent notations, i.e., without changing the essence or output of an
expression. These notations are −
1. Infix Notation
2. Prefix (Polish) Notation
3. Postfix (Reverse-Polish) Notation
162
Conversion of Infix Expressions to Prefix and Postfix
Convert following infix expression to prefix and postfix
(A + B) * C - (D - E) * (F + G)
The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower,[1]
and sometimes pluralized) is a mathematical game or puzzle. It consists of three
rods, and a number of disks of different sizes which can slide onto any rod. The
puzzle starts with the disks in a neat stack in ascending order of size on one
rod, the smallest at the top, thus making a conical shape.
163
The objective of the puzzle is to move the entire stack to another rod,
obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.
QUEUE ADT
A queue is an ordered collection of data such that the data is inserted at one
end and deleted from another end. The key difference when compared stacks
is that in a queue the information stored is processed first-in first-out or
FIFO. In other words the information receive from a queue comes in the
same order that it was placed on the queue.
Representing a Queue:
One of the most common way to implement a queue is using array. An easy
way to do so is to define an array Queue, and two additional variables front
and rear. The rules for manipulating these variables are
simple:
Each time information is added to the queue, increment rear.
Each time information is taken from the queue, increment front.
Whenever front >rear or front=rear=-1 the queue is empty.
Array implementation of a Queue do have drawbacks. The maximum
queue size has to be set at compile time, rather than at run time. Space can
be wasted, if we do not use the full capacity of the array.
164
Operations on Queue:
A queue have two basic operations:
a) adding new item to thequeue
b) removing items from queue.
The operation of adding new item on the queue occurs only at one end of the
queue called the rear or back.
The operation of removing items of the queue occurs at the other end called the front.
For insertion and deletion of an element from a queue, the array elements
begin at 0 and the maximum elements of the array is maxSize. The variable
front will hold the index of the item that is considered the front of the queue,
while the rear variable will hold the index of the last item in the queue.
Assume that initially the front and rear variables are initialized to -
1. Like stacks, underflow and overflow conditions are to be checked before
operations in a queue.
Queue empty or underflow condition is
if((f
r
o
n
t
>
r
e
a
r
)
|
|
f
r
o
n
t
=
=
-
1
)
c
o
u
t
<
”
Q
u
e
u
e
i
165
s
e
m
p
t
y
”
;
Queue Full or overflow condition is
if((rear==max) cout<”Queue is full”;
Static implementation of Queue ADT
#
i
n
c
l
u
d
e
<
s
t
d
l
i
b
.
h
>
#
i
n
c
l
u
d
e
<
i
o
s
t
r
166
e
a
m
.
h
>
#
d
e
f
i
n
e
m
a
x
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
q
u
e
u
e
{
T
q
[
167
m
a
x
]
,
i
t
e
m
;
i
n
t
f
r
o
n
t
,
r
e
a
r
;
public: queue();
v
o
i
d
i
n
s
e
r
t
_
q
(
)
;
v
o
i
d
d
e
l
e
t
e
_
168
q
(
)
;
v
o
i
d
d
i
s
p
l
a
y
_
q
(
)
;
};
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
q
u
e
u
e
<
T
>
:
:
q
u
e
u
169
e
(
)
{
front=rear=-1;
}
//code to
insert an
item into
queue;
template
<class T>
void queue<T> ::insert_q()
170
{
if(front>rear)
f
r
o
n
t
=
r
e
a
r
=
-
1
;
i
f
(
r
e
a
r
=
=
m
a
x
-
1
)
cout<
<"queue
Overflo
w...\n";
else
{
if(fr
ont= front=0;
=-1)
rear
++;
cout<<"Enter
an item to be
inserted:";
cin>>item;
q[rear]=item;
cout<<"inserted Sucesfully..into queue..\n";
}
}
template <class T>
void queue<T>::delete_q()
{
if((front==-1&&rear==-1)||front>rear)
171
{
front=rear=-1;
cout<<"queue is Empty .. \n";
}
else
{
i
t
e
m
=
q
[
f
r
o
n
t
]
;
f
r
o
n
t
+
+
;
cout<<item<<" is deleted Sucesfully ...\n";
}
}
template <class T>
void queue<T>::display_q()
{
if((front==-1&&rear==-1)||front>rear)
{
front=rear=-1;
cout<<"queue is Empty .. \n";
}
else
{
for(int
i=fron
t;i<=r
} ear;i+
int +)
main cout<
() <"|"<
{ <q[i]<
int <"|
choi <--";
ce; }
queue<int> q;
while(1)
172
{
cout<<"\n\n*****Menu for operations
on QUEUE*****\n\n";
cout<<"[Link]\[Link]\
[Link]\[Link]\n";
173
c
o
u
t
<
<
"
E
n
t
e
r
C
h
o
i
c
e
:
"
;
c
i
n
>
>
c
h
o
i
c
e
;
switch(choice)
{
case 1: q.insert_q();
b
r
e
a
k
;
c
a
s
e
2
:
q
.
174
d
e
l
e
t
e
_
q
(
)
;
break;
case 3:
cout<<
"Eleme
nts in
the
queue
are... \
n";
[Link]
ay_q();
break;
case 4: exit(0);
default: cout<<"Invalid choice...Try again...\n";
}
}
}
Dynamic implementation of Queue ADT
#
i
n
c
l
u
d
e
<
s
t
d
l
i
b
.
h
>
#
i
n
175
c
l
u
d
e
<
i
o
s
t
r
e
a
m
.
h
>
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
s
t
r
u
c
t
n
o
d
e
{
T
d
a
t
a
176
;
s
t
r
u
c
t
n
o
d
e
<
T
>
*
n
e
x
t
;
};
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
q
u
e
u
e
{
private:
177
p T item;
u node<T> *front,*rear;
bl
ic queue();
: v
o
i
d
}; i
n
s
e
r
t
_
q
(
)
;
v
o
i
d
d
e
l
e
t
e
_
q
(
)
;
v
o
i
d
d
i
s
p
l
a
y
_
q
(
)
;
178
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
q
u
e
u
e
<
T
>
:
:
q
u
e
u
e
(
)
{
front=rear=NULL;
}
//code to
insert an
item into
queue;
template
<class T>
void queue<T>::insert_q()
{
node<T>*p;
cout<<"Enter an element to be inserted:";
179
c
i
n
>
>
i
t
e
m
;
p
=
n
e
w
n
o
d
e
<
T
>
;
p
-
>
d
a
t
a
=
i
t
e
m
;
p
-
>
n
e
x
t
=
N
U
L
L
;
i
f
(
180
f
r
o
n
t
=
=
N
U
L
L
)
{
rear=front=p;
}
else
{
r
e
a
r
-
>
n
e
x
t
=
p
;
r
e
a
r
=
p
;
}
cout<<"\nInserted into Queue Sucesfully... \n";
}
//code to
delete an
elementfrom
queue
template
<class T>
void queue<T>::delete_q()
{
node<T>*t;
if(front==NULL)
cout<<"
\nQueue is
Underflow
"; else
{
181
i
t
e
m
=
f
r
o
n
t
-
>
d
a
t
a
;
t
=
f
r
o
n
t
;
f
r
o
n
t
=
f
r
o
n
t
-
>
n
e
x
t
;
cout<<"\n"<<item<<" is deletedfrom Queue... \n";
}
delete(t);
}
//code to
display
elements
in queue
template
<class T>
void queue<T>::display_q()
{
182
node<T>*t;
if(front==
NULL)
cout<<
"\
nQueue
Under
Flow";
else
{
cout<<"\
nElements in the
Queue are... \n";
t=front;
while(t!=NULL)
{
cout<<"|"
<<t-
} >data<<"|
} <-"; t=t-
} >next;
int main()
{
int choice;
queue<int>q1;
183
while(1)
{
cout<<"\n\n***Menu for
operations on Queue***\n\n";
cout<<"[Link]\[Link]\
[Link]\[Link]\n";
cout<<"Enter Choice:";
c
i
n
>
>
c
h
o
i
c
e
;
s
w
i
t
c
h
(
c
h
o
i
c
e
)
{
case 1: q1.insert_q();
b
r
e
a
k
;
c
a
s
e
2
:
q
1
.
d
184
e
l
e
t
e
_
q
(
)
;
b
r
e
a
k
;
c
a
s
e
3
:
q
1
.
d
i
s
p
l
a
y
_
q
(
)
;
break;
case 4: exit(0);
default: cout<<"Invalid choice...Try again...\n";
}
}
}
Application of Queue:
Queue, as the name suggests is used whenever we need to have any group
of objects in an order in which the first one coming in, also gets out first
while the others wait for there turn, like in the following scenarios :
1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people
calling them in an order, until a service representative is free.
185
3. Handling of interrupts in real-time systems. The interrupts are handled
in the same order as they arrive, First come first served.
CIRCULAR QUEUE
Once the queue gets filled up, no more elements can be added to it even if
any element is removed from it consequently. This is because during
deletion, rear pointer is not adjusted.
When the queue contains very few items and the rear pointer points to last
element. i.e. rear=maxSize- 1, we cannot insert any more items into queue
because the overflow condition satisfies. That means a lot of space is wasted
.Frequent reshuffling of elements is time consuming. One
solution to this is arranging all elements in a circular fashion. Such
structures are often referred to as Circular Queues.
186
A circular queue is a queue in which all locations are treated as
circular such that the first location CQ[0] follows the last location
CQ[max-1].
Circular Queue empty or underflow condition is
if(front==-1)
cout<<"Queue is empty";
Circular Queue Full or overflow condition is
if(front==(rear+1)%max)
{
cout<<"Circular Queue is full\n";
}
Insertion into a Circular Queue:
Algorithm
CQueueInsertion(Q,maxSize,Fro
nt,Rear,item) Step 1: If Rear =
maxSize-1 then
Rear = 0
else
Rear=Rear+1
Step 2:
I
f
187
F
r
o
n
t
=
R
e
a
r
t
h
e
n
p
r
i
n
t
“
Q
u
e
u
e
O
v
e
r
f
l
o
w
”
R
e
t
u
r
n
Step 3: Q[Rear] = item
188
Step 4:
I
f
F
r
o
n
t
t
h
e
n
F
r
o
n
t
1
Step 5: Return
Deletion from Circular Queue:
Algorithm CQueueDeletion(Q,maxSize,Front,Rear,item)
Step 1: If Front = 0 then
p
ri
nt
“
Q
u
e
u
e
U
n
d
er
fl
o
w
”
R
et
u
r
189
n
Step 2: K=Q[Front]
Step 3: If
Fro
nt =
Rea
r
the
n
beg
in
Front = -1
Rear = -1
e
n
d
e
l
s
e
If Front =
m
ax
Si
ze
-1
th
en
Fr
o
nt
=
0
else
Front = Front + 1
Step 4: Return K
Static implementation of Circular Queue ADT
#
i
n
c
l
u
d
e
<
i
o
s
t
r
190
e
a
m
.
h
>
#
d
e
f
i
n
e
m
a
x
t
e
m
p
l
a
t
e
<
c
l
a
s
s
T
>
c
l
a
s
s
C
i
r
c
u
l
a
r
Q
191
{
T
public: c
q
[
m
a
} x
; ]
;
i
n
t
f
r
o
n
t
,
r
e
a
r
;
C
i
r
c
u
l
a
r
Q
(
)
;
v
o
i
d
i
n
s
e
r
t
Q
(
)
192
;
v
v o
o i
i d
d
d
d i
e s
l p
e l
t a
e y
Q Q
( (
) )
; ;
tem
plat
e
<cl
ass
T>
Cir
cul
arQ
<T
>::
Cir
cul
arQ
()
{
front=rear=-1;
}
template <class T>
void CircularQ<T>:: insertQ()
{
int num;
if(front==(rear+1)%max)
{
cout<<"Circular Queue is full\n";
}
193
els
e
{ cout<<"
Enter an
element"
;
cin>>nu
m;
if(front==-1)
rear=front=0;
else
rear=(rear+1)%max;
cq[rear]=num;
cout<<num <<" is inserted ...";
}
}
template
<class T>
void CircularQ<T>::deleteQ()
{
int num;
if(front==-1)
cout<<"Queue is empty";
el
s
e num=cq[front];
{ cout<<"Delete
d item is "<<
num;
if(front==rear)
f
else
ront=
}
} rear=
-1;
front
=(fro
nt+1)
%ma
x;
template <class T>
void CircularQ<T>::displayQ()
{
int i;
if(front==-1)
cout<<"Queue is empty";
else
194
{
cout<<"
Queue
element
s are\n";
for(i=fr
ont;i<=r
ear;i++)
cout<<cq[i]<<"\t";
}
if(front>rear)
{
for(i=front;i<max;i++)
c
out
<<
cq[
i]<
<"\
t";
for
(i=
0;i
<=
rea
r;i
+
+)
cout<<cq[i]<<"\t";
}
}
int main()
{
C
i
r
c
u
l
a
r
Q
<
i
n
t
>
o
b
j
;
195
n
t
c
h
o
i
c
e
;
while(1)
{ cout<<"\n*** Circular Queue Operations***\n";
196
cout<<"\[Link]
Element into
CircularQ"; cout<<"\
[Link] Element
from CircularQ";
cout<<"\[Link]
Elements in
CircularQ"; cout<<"\
[Link] ";
c
o
u
t
<
<
"\
n
E
n
te
r
C
h
o
ic
e:
";
ci
n
>
>
c
h
o
ic
e;
s
w
it
c
h
(
c
h
o
ic
e
)
{ case
1:
[Link]
sertQ(
);
break;
case 2: [Link]();
b
197
r
e
a
k
;
c
a
s
e
3
:
o
b
j
.
d
i
s
p
l
a
y
Q
(
)
;
break;
case 4: exit(0);
}
}
}
198
UNIT-2
P
r
i
o
r
i
t
y
Q
u
e
u
e
D
E
F
I
N
I
T
I
O
N
:
A priority queue is a collection of zero or more elements. Each element has a priority or value.
Unlike the queues, which are FIFO structures, the order of deleting from a priority queue is
determined by the element priority.
Elements are removed/deleted either in increasing or decreasing order of priority rather
than in the order in which they arrived in the queue.
There are two types of priority queues:
Min priority queue
Max priority queue
Min priority queue: Collection of elements in which the items can be inserted arbitrarily, but
only smallest element can be removed.
Max priority queue: Collection of elements in which insertion of items can be in any order
but only largest element can be removed.
In priority queue, the elements are arranged in any order and out of which only the
smallest or largest element allowed to delete each time.
The implementation of priority queue can be done using arrays or linked list. The data
structure heap is used to implement the priority queue effectively.
APPLICATIONS:
1. The typical example of priority queue is scheduling the jobs in operating system.
Typically OS allocates priority to jobs. The jobs are placed in the queue and position of
the job in priority queue determines their priority. In OS there are 3 jobs- real time jobs,
foreground jobs and background jobs. The OS always schedules the real time jobs first.
If there is no real time jobs pending then it schedules foreground jobs. Lastly if no real
time and foreground jobs are pending then OS schedules the background jobs.
199
UNIT-2
2. In network communication, the manage limited bandwidth for transmission the priority
queue isused.
3. In simulation modeling to manage the discrete events the
priority queue is used. Various operations that can be performed
on priority queue are-
1. Find an element
2. Insert a new element
3. Remove or delete an element
The abstract data type specification for a max priority queue is given below. The
specification for a min priority queue is the same as ordinary queue except while deletion,
find and remove the element with minimum priority
ABSTRACT DATA TYPE(ADT):
Abstract data type maxPriorityQueue
{
Instances
Finite collection of elements, each
has a priority Operations
empty():return true iff the queue is
empty
size() :return number of
elements in the queue
top() :return element
with maximum priority
del() :remove the element with largest
priority from the queue insert(x): insert
the element x into the queue
200
UNIT-2
}
HEAPS
Heap is a tree data structure denoted by either a max heap or a min heap.
A max heap is a tree in which value of each node is greater than or equal to value of its
children nodes. A min heap is a tree in which value of each node is less than or equal to
18 4
12 4 12 14
11 10 18 20
value of its children nodes.
Max heap Min heap
Insertion of element in the Heap:
Consider a max heap as given below:
Now if we want to insert 7. We cannot insert 7 as left child of 4. This is because the max
heap has a property that value of any node is always greater than the parent nodes. Hence 7
will bubble up 4 will be left child of 7.
Note: When a new node is to be inserted in complete binary tree we start from bottom and
from left child on the current level. The heap is always a complete binary tree.
201
UNIT-2
18
12 7 inserted!
11 10 4
If we want to insert node 25, then as 25 is greatest element it should be the root. Hence 25
will bubble up and 18 will move down.
25 inserted!
12 18
11 10 4
The insertion strategy just outlined makes a single bubbling pass from a leaf toward the
root. At each level we do (1) work, so we should be able to implement the strategy to have
complexity O(height) = O(log n).
void Heap::insert(int item)
{
int temp; //temp node starts at leaf and moves up.
temp=++size;
while(temp!=1 && heap[temp/2]<item) //moving element down
{
H[temp] = H[temp/2]; temp=temp/2;
//finding the parent
}
H[temp]=item;
}
Deletion of element from the heap:
202
UNIT-2
For deletion operation always the maximum element is deleted from heap. In Max
heap the maximum element is always present at root. And if root element is deleted then we
need to reheapify the tree.
Consider a Max heap
25
12 18
11 10 4
Delete root element:25, Now we cannot put either 12 or 18 as root node and that
should be greater than all its children elements.
18
12 4
11 10
Now we cannot put 4 at the root as it will not satisfy the heap property. Hence we will bubble
up 18 and place 18 at root, and 4 at position of 18.
If 18 gets deleted then 12 becomes root and 11 becomes parent node of 10.
203
UNIT-2
Thus deletion operation can be performed. The time complexity of deletion operation is O(log n).
1. Remove the maximum element which is present at the root. Then a hole is created at the
root.
2. Now reheapify the tree. Start moving from root to children nodes. If any
maximum element is found then place it at root. Ensure that the tree is satisfying
the heap property or not.
3. Repeat the step 1 and 2 if any more elements are to be deleted.
void heap::delet(int item)
{
i
n
t
i
t
e
m
,
t
e
m
p
;
i
f
(
s
i
z
e
=
=
0
)
204
UNIT-2
cout<<”Heap is empty\n”; else
{
//remove the last
elemnt and
reheapify
item=H[size--];
//item is
placed at
root
temp=1;
child=2;
while(child<=size)
{
if(child<size &&
H[child]<H[child+1])
child++;
if(item>=H[child])
b
r
e
a
k
;
H
[
t
e
m
p
]
=
H
[
c
h
i
l
d
]
;
t
e
m
p
=
c
h
i
l
d
;
205
UNIT-2
c
h
i
l
d
=
c
h
i
l
d
*
2
;
}
//pl;ace the
largest item at
root
H[temp]=item;
}
Applications Of Heap:
1. Heap is used in sorting algorithms. One such algorithm using heap is known as heap sort.
206
UNIT-2
2. In priority queue implementation the heap is used.
HEAP SORT
Heap sort is a method in which a binary tree is used. In this method first the heap is created
using binary tree and then heap is sorted using priority queue.
Eg:
25 57 48 38 10 91 84 33
In the heap sort method we first take all these elements in the array “A”
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7]
25 57 48 38 10 91 84 33
Now start building the heap structure. In forming the heap the key point is build heap
in such a way that the highest value in the array will always be a root.
Insert 25
207
UNIT-2
208
UNIT-2
The next element is 84, which 91>84>57 the middle element. So 84 will be the parent
of 57. For making the complete binary tree 57 will be attached as right of 84.
209
UNIT-2
Now the heap is formed. Let us sort it. For sorting the heap remember two main things the first
thing is that the binary tree form of the heap should not be distributed at all. For the complete
sorting binary tree should be remained. And the second thing is that we will start sorting the
higher elements at the end of array in sorted manner i.e..
A[7]=91, A[6]=84 and so on..
Step 1:- Exchange A[0] with A[7]
210
UNIT-2
211
UNIT-2
212
UNIT-2
213
UNIT-2
Step 5:-Exchane A[0] with A[2]
214
UNIT-2
Write a program to implement heap sort
#i
n
cl
u
d
e
<i
o
st
re
a
m
.h
>
v
oi
d
s
w
a
p(
in
t
*
a,
215
UNIT-2
in
t
*
b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
void heapify(int arr[], int n, int i)
{
int largest = i; //
Initialize largest
as root int l = 2*i
+ 1; // left = 2*i +
1
int r = 2*i + 2; // right = 2*i + 2
// If left
child is
larger
than root
if (l<n
&&(arr[l]
>arr[large
st]))
largest = l;
// If right child is
larger than largest
so far if (r < n
&&( arr[r] >
arr[largest]))
largest = r;
216
/
/
I
f
l
a
r
g
e
s
t
i
s
n
o
t
r
o
o
t
i
f
(
l
a
r
g
e
s
t
!
=
i
)
{
swap(&arr[i], &arr[largest]);
// Recursively
heapify the affected
sub-tree heapify(arr,
n, largest);
}
}
217
//
functio
n to do
heap
sort
void
heapS
ort(int
arr[],
int n)
{ int i;
// Build
heap
(rearran
ge
array)
for ( i =
n / 2 - 1;
i >= 0;
i--)
heapify(arr, n, i);
// One by one extract
an element from
heap for ( i=n-1;
i>=0; i--)
{
//
Mov
e
curre
nt
root
to
end
swap
(&ar
r[0],
&arr
[i]);
// call max
heapify on the
reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to
print array of size n */
void printArray(int arr[],
int n)
218
{
for (int
i=0;
i<n;
++i)
cout
<<
arr[i
] <<
" ";
cout << "\n";
}
int main()
{
int n,i;
int list[30];
cout<<"e
nter no of
elements\
n";
cin>>n;
cout<<"ente
r "<<n<<"
numbers ";
for(i=0;i<n;i
++)
c
i
n
>
>
l
i
s
t
[
i
]
;
h
e
a
p
S
o
r
t
(
l
i
s
t,
219
n
)
;
cout
<< "Sorted
array is \n";
printArray(
list, n);
return 0;
}
220
UNIT -3
Searching: Linear and binary search methods.
Sorting: Bubble sort, selection sort, Insertion sort, Quick sort, Merge sort, Heap sort. Time complexities.
Graphs: Basic terminology, representation of graphs, graph traversal methods DFS, BFS.
ALGORITHMS
Definition: An Algorithm is a method of representing the step-by-step
procedure for solving a problem. It is a method of finding the right answer to
a problem or to a different problem by breaking the problem into simple
cases.
It must possess the following properties:
1. Finiteness: An algorithm should terminate in a finite number of steps.
2. Definiteness: Each step of the algorithm must be precisely (clearly) stated.
3. Effectiveness: Each step must be effective.i.e; it should
be easily convertible into program statement and can be
performed exactly in a finite amount of time.
4. Generality: Algorithm should be complete in itself, so that it
can be used to solveall problems of given type for any input
data.
5. Input/Output: Each algorithm must take zero, one or more
quantities as input data and gives one of more output
values.
An algorithm can be written in English like
sentences or in any standard representations. The algorithm written in
English language is called Pseudo code.
Example: To find the average of 3 numbers, the algorithm is as shown below.
Step1: Read the
numbers a, b, c,
and d. Step2:
Compute the
sum of a, b, and
c. Step3: Divide
the sum by 3.
Step4: Store the
result in
variable of d.
Step5: End the
program.
Searching: Searching is the technique of finding desired data items that has been stored
221
UNIT -3
within some data structure. Data structures can include linked lists, arrays,
search trees, hash tables, or various other storage methods. The appropriate
search algorithm often depends on the data structure being searched.
Search algorithms can be classified based on their mechanism of searching. They are
Linear searching
Binary searching
Linear or Sequential searching: Linear Search is the most natural
searching method and It is very simple but very poor in performance at times
.In this method, the searching begins with
222
UNIT -3
searching every element of the list till the required record is found. The
elements in the list may be in any order. i.e. sorted or unsorted.
We begin search by comparing the first element of the list with the
target element. If it matches, the search ends and position of the element is
returned. Otherwise, we will move to next element and compare. In this way,
the target element is compared with all the elements until a match occurs. If
the match do not occur and there are no more elements to be compared, we
conclude that target element is absent in the list by returning position as -1.
For example consider the following list of elements.
55 95 75 85 11 25 65 45
Suppose we want to search for element 11(i.e. Target element = 11).
We first compare the target element with first element in list i.e. 55. Since
both are not matching we move on the next elements in the list and compare.
Finally we will find the match after 5 comparisons at position 4 starting from
position 0.
Linear search can be implemented in two ways.i)Non recursive ii)recursive
Algorithm for Linear search
Linear_Sea
rch (A[ ],
N, val ,
pos ) Step
1 : Set pos
= -1 and k
= 0 Step 2
: Repeat
while k <
N
Begin
Step 3 : if A[ k ] = val
S
e
t
p
o
s
p
r
i
n
t
p
o
s
223
UNIT -3
G
o
t
o
s
t
e
p
5
End while
Step 4 : print “Value is not present”
Step 5 : Exit
Non recursive C++ program for Linear search
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
224
UNIT -3
s
t
d
;
int
Lsearch(int
list[ ],int
n,int key);
int main()
{
int n,i,key,list[25],pos;
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
elements ";
for(i=0;i<n;
i++)
c
in>>l
ist[i];
cout<
<"ent
er
key
to
searc
h";
cin>>
key;
po
s=
Ls
ea
rc
h
(li
st,
n,
ke
y);
if(
po
s=
=-
1)
cout<<"\nelement not found";
else
225
UNIT -3
cout<<"\n element found at index "<<pos;
}
/*function for linear search*/
int Lsearch(int list[ ],int n,int key)
{
int i,pos=-1;
for(i=0;i<n;i++)
if(key==list[i])
{
p
o
} s
return =
pos; i
} ;
b
r
e
a
k
;
Run 1:
enter no of elements 5
enter
5
elem
ents
99
88 7
24
enter
key
to
searc
h7
elem
ent
foun
d at
index
2
Run 2:
enter no of elements 5
enter
5
elem
ents
99
88 7
24
226
UNIT -3
enter
key
to
searc
h 88
elem
ent
not
foun
d
Recursive C++ program for Linear search
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
227
UNIT -3
int
Rec_Lsearch(int
list[ ],int n,int
key); int main()
{
int n,i,key,list[25],pos;
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
elements ";
for(i=0;i<n;
i++)
c
in>>list[
i];
cout<<"
enter
key to
search";
cin>>ke
y;
pos=Rec
_Lsearc
h(list,n-
1,key);
if(pos==
-1)
cout<<"\nelement not found";
else
cout<<"\n element found at index "<<pos;
}
228
UNIT -3
/*recursive
function for
linear search*/
int
Rec_Lsearch(in
t list[],int n,int
key)
{
if(n<0)
r
e
t
u
r
n
-
1
;
i
f
(
l
i
s
t
[
n
]
=
=
k
e
y
)
r
e
t
u
r
n
n
;
e
l
s
e
return Rec_Lsearch(list,n-1,key);
}
RUN1:
229
UNIT -3
enter no of elements 5
5 elements 5
e 55 -4 99 7
n enter key
t to search-
e 4 element
r found at
index 2
RUN 2:
enter no of elements 5
enter
5
eleme
nts 5
55 -4
99 7
enter
key to
searc
h77
eleme
nt not
found
BINARY SEARCHING
Binary search is a fast search algorithm with run-time complexity of Ο(log
n). This search algorithm works on the principle of divide and conquer.
Binary search looks for a particular item by comparing the middle most
item of the collection. If a match occurs, then the index of item is returned. If
the middle item is greater than the item, then the item is searched in the
sub-array to the left of the middle item. Otherwise, the item is searched for in
the sub-array to the right of the middle item. This process continues on the
sub-array as well until the size of the subarray reduces to zero.
Before applying binary searching, the list of items should
be sorted in ascending or descending order.
Best case time
complexity is
O(1) Worst case
time complexity
is O(log n)
230
UNIT -3
Algorithm:
Binary_Search (A [ ], U_bound, VAL)
Step 1 : set BEG = 0 , END
= U_bound , POS = -1 Step
2 : Repeat while (BEG <=
END )
Step 3 : set MID = ( BEG + END ) / 2
Step 4 : if A [ MID ] == VAL then
POS = MID
print VAL
“ is
available at
“, POS
GoTo Step
6
End if
if
A
M
I
D
>
V
A
L
t
h
e
231
UNIT -3
n
s
e
t
E
N
D
M
I
D
1
Else
set BEG = MID + 1
E
n
d
i
f
E
n
d
w
h
i
l
e
Step 5 : if POS = -1 then
print
VAL “
is not
present
“ End if
Step 6 : EXIT
Non recursive C++ program for binary search
#
i
n
c
l
232
UNIT -3
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
int binary_search(int
list[],int key,int low,int
high); int main()
{
int n,i,key,list[25],pos;
cout<<"enter no of elements\n" ;
233
UNIT -3
cin>>n;
cout<<"enter "<<n<<"
elements in ascending order ";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"ent
er key to
search" ;
cin>>key;
pos=binary
_search(list
,key,0,n-
1);
if(pos==-
1)
cout<<"element not found" ;
else
cout<<"element found at index "<<pos;
}
/* function for binary search*/
int binary_search(int list[],int key,int low,int high)
{
int mid,pos=-1;
while(low<=high)
{
m
i
d
=
(
l
o
w
+
h
i
g
h
)
/
2
;
i
f
(
k
e
y
=
=
l
i
s
234
UNIT -3
t
[
m
i
d
]
)
{
p
o
s
=
m
i
d
;
b
r
e
a
k
;
}
else if(key<list[mid])
high=mid-1;
else
low=mid+1;
}
return pos;
}
R
u enter no of elements5
n enter 5 elements in ascending
1: order 11 22 33 44 55 enter key
to search33
element found at index 2
enter no of elements5
R enter 5 elements in ascending
u order 11 22 33 44 55 enter key
n to search21
2: element Not found
Recursive C++ program for binary search
#
i
n
c
l
u
d
235
UNIT -3
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
int rbinary_search(int list[
],int key,int low,int high); int
main()
{
236
UNIT -3
int n,i,key,list[25],pos;
cout<<"e
nter no of
elements\
n" ;
cin>>n;
cout<<"enter "<<n<<"
elements in ascending order ";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"ent
er key to
search" ;
cin>>key;
pos=rbinary
_search(list,
key,0,n-1);
if(pos==-1)
cout<<"element not found" ;
else
cout<<"element found at index "<<pos;
}
/*recursive function for binary search*/
int rbinary_search(int list[ ],int key,int low,int high)
{
int mid,pos=-1;
if(low<=high)
{
m
i
d
=
(
l
o
w
+
h
i
g
h
)
/
2
;
i
f
(
k
e
y
=
=
237
UNIT -3
l
i
s
t
[
m
i
d
]
)
{
p
o
s
=
m
i
d
;
r
e
t
u
r
n
p
o
s
;
}
else if(key<list[mid])
return rbinary_search(list,key,low,mid-1);
else
return rbinary_search(list,key,mid+1,high);
}
return pos;
}
RUN 1:
enter no of elements 5
enter 5 elements in
ascending order 11 22 33 44
66 enter key to search33
el
ement
found at
index 2
RUN 2:
enter no of elements 5
enter 5 elements in
ascending order 11 22 33 44
66 enter key to search77
element not found
238
SORTING
UNIT -3
Arranging the elements in a list either in ascending or
descending order. various sorting algorithms are
Bubble sort
239
UNIT -3
selection sort
Insertion sort
Quick sort
Merge sort
Heap sort
Bubble sort
The bubble sort is an example of exchange sort. In this method, repetitive
comparison is performed among elements and essential swapping of elements
is done. Bubble sort is commonly used in sorting algorithms. It is easy to
understand but time consuming i.e. takes more number of comparisons
to sort a list . In this type, two successive elements are compared and
swapping is done. Thus, step-by-step entire array elements are checked. It is
different from the selection sort. Instead of searching the minimum element
and then applying swapping, two records are swapped instantly upon
noticing that they are not in order.
ALGORITHM:
Bubble_Sort ( A [ ] , N )
Step 1: Start
Step 2:
Take an
array of n
elements
Step 3: for
i=0,...................................n-2
Step 4: for j=i+1,…….n-1
Step 5: if
arr[j]>
arr[j+1
] then Interchange arr[j] and arr[j+1] End of if
Step 6:
Print the
sorted
array arr
Step
7:Stop
#
i
n
c
l
u
d
e
<
i
o
s
240
UNIT -3
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
void
bubble_sort
(int
list[30],int
n); int
main()
{
int n,i;
int list[30];
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
numbers ";
for(i=0;i<n
;i++)
c
i
n
>
>
l
i
s
241
UNIT -3
t
[
i
]
;
b
u
b
b
l
e
_
s
o
r
t
(
l
i
s
t
,
n
)
;
c
o
u
t
<
<
"
af
te
r
s
o
rt
i
n
g
\
n
";
f
o
r(
i
=
0
;i
<
n
242
UNIT -3
;i
+
+
)
c
o
u
t
<
<
li
st
[i
]
<
<
e
n
d
l;
return 0;
}
void bubble_sort (int list[30],int n)
243
UNIT -3
{
i
n
t
t
e
m
p
i
n
t
i
,
j
;
f
o
r
(
i
=
0
;
i
<
n
;
i
+
+
)
f
o
r
(
j
=
0
;
j
<
n
-
1
;
j
+
244
UNIT -3
+
)
i
f
(
l
i
s
t
[
j
]
>
l
i
s
t
[
j
+
1
]
)
{
t
e
m
p
=
l
i
s
t
[
j
]
;
l
i
s
t
[
j
]
=
l
i
s
t
[
j
+
245
UNIT -3
1
]
;
l
i
s
t
[
j
+
1
]
=
t
e
m
p
;
}
}
RUN 1:
e
n
t
e
r
n
o
o
f
e
l
e
m
e
n
t
s
5
enter 5 numbers 5 4 3 2 1
after sorting 1 2 3 4 5..
Selection sort
selection sort:- Selection sort ( Select the smallest and Exchange ):
The first item is compared with the remaining n-1 items, and
246
UNIT -3
whichever of all is lowest, is put in the first [Link] the second item
from the list is taken and compared with the remaining (n-2) items, if an
item with a value less than that of the second item is found on the (n-
2) items, it is swapped (Interchanged) with the second item of the list and so on.
Alg
ori
th
m:
Sel
ecti
on_
Sor
t(
A[
],
N)
Ste
p1
:sta
rt
Step 2:
Repe
at
For
K=
0 to
N–
2
Begi
n
Step 3 : Set POS = K
247
UNIT -3
Step 4 :
Repe
at for
J=K
+1
to N
–1
Begi
n
If A[ J ] < A [ POS ]
Set POS = J
End For
Step 5 : Swap
A[K]
with A
[ POS ]
End For
Step 6 : stop
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
248
UNIT -3
s
t
d
;
void
selection_so
rt (int
list[],int n);
int main()
{
int n,i;
int list[30];
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
numbers ";
for(i=0;i<n
;i++)
ci
n
>
>
li
st
[i
];
s
el
e
ct
i
o
n
_
s
o
rt
(l
is
t,
n
);
c
o
u
t
<
<
"
249
UNIT -3
a
ft
e
r
s
o
rt
i
n
g
\
n
";
f
o
r(
i
=
0
;i
<
n
;i
+
+
)
c
o
u
t
<
<
li
st
[i
]
<
<
e
n
d
l;
return 0;
}
void selection_sort (int list[],int n)
{
int min,temp,i,j;
for(i=0;i<n;i++)
{
m
i
n
=
i
;
250
UNIT -3
f
o
r
(
j
=
i
+
1
;
j
<
n
;
j
+
+
)
{
i
f
(
l
i
s
t
[
j
]
<
l
i
s
t
[
m
i
n
]
)
m
i
n
=
j
;
}
t
e
m
p
=
251
UNIT -3
l
i
s
t
[
i
]
;
l
i
s
t
[
i
]
=
l
i
s
t
[
m
i
n
]
;
l
i
s
t
[
m
i
n
]
=
t
e
m
p
;
}
}
RUN 1:
e
n
t
e
r
n
252
UNIT -3
o
o
f
e
l
e
m
e
n
t
s
5
enter 5 numbers 5 4 3 2 1
after sorting 1 2 3 4 5
253
UNIT -3
INSERTION SORT
Insertion sort: It iterates, consuming one input element each repetition,
and growing a sorted output list. Each iteration, insertion sort removes
one element from the input data, finds the location it belongs within the
sorted list, and inserts it there. It repeats until no input elements remain.
ALGORITHM:
Step 1: start
Step
2: for i
← 1 to
length
(A)
Step
3: j←i
Step 4: while
j > 0 and A[j-
1] > A[j]
Step 5:
swap
A[j] and A[j-
1] Step 6: j
←j- 1
S
t
e
p
254
UNIT -3
7
:
end while Step 8: end for Step9: stop
program to implement insertion sort
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
void insertion_sort(int a[],int n)
{
int i,t,pos;
for(i=0;i<n;i++)
{
255
UNIT -3
t
=
a
[
i
]
;
p
o
s
=
i
;
while(pos>0&&a[pos-1]>t)
{
a
[
p
o
s
]
=
a
[
p
o
s
-
1
]
;
p
o
s
-
-
;
}
a[pos]=t;
}
}
int main()
{
int n,i;
int list[30];
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
256
UNIT -3
numbers ";
for(i=0;i<n
;i++)
ci
n
>
>
li
st
[i
];
i
n
s
e
rt
i
o
n
_
s
o
rt
(l
is
t,
n
);
c
o
u
t
<
<
"
a
ft
e
r
s
o
rt
i
n
g
\
n
";
f
o
r(
i
=
0
;i
257
UNIT -3
<
n
;i
+
+
)
c
o
u
t
<
<
li
st
[i
]
<
<
e
n
d
l;
return 0;
}
RUN 1:
enter no of elements 5
enter 5 numbers 55 44 33 22 11
after sorting 11 22 33 44 55
Quick sort
Quick sort: It is a divide and conquer algorithm. Developed by Tony
Hoare in 1959. Quick sort first divides a large array into two smaller sub-
arrays: the low elements and the high elements. Quick sort can then
recursively sort the sub-arrays.
ALGORITHM:
Step 1: Pick an element, called a pivot, from the array.
Step 2: Partitioning: reorder the array so that all elements with values less
than the pivot come before the pivot, while all elements with values
greater than the pivot come after it (equal values can go either way).
After this partitioning, the pivot is in its final position. This is called
the partition operation.
Step 3: Recursively apply the above steps to the sub-array of elements
with smaller values and separately to the sub-array of elements
with greater values.
258
UNIT -3
259
UNIT -3
260
UNIT -3
program to
implement
Quick sort
#include<iost
ream.h>
int partition(int x[],int low,int high)
{
int
down,up,pivot,t
;
if(low<high)
{
d
o
w
n
=
l
o
w
;
u
p
=
h
i
g
h
;
p
i
v
o
t
=
d
o
w
n
;
261
UNIT -3
w
h
i
l
e
(
d
o
w
n
<
u
p
)
{
while((x[down]<=x[pivot])&&(down<high))down++;
while(
x[up]>
x[pivo
t])up--
;
if(dow
n<up)
{
t
=
x
[
d
o
w
n
]
;
x
[
d
o
w
n
]
=
x
[
u
262
UNIT -3
p
]
;
x
[
u
p
]
=
t
;
}/*endif*/
}
t
=
x
[
p
i
v
o
t
]
;
x
[
p
i
v
o
t
]
=
x
[
u
p
]
;
x
[
u
p
]
263
UNIT -3
=
t
;
}
return up;
}
void quicksort(int x[],int low,int high)
{
int p;
if(low<high)
{
p=p
artit
ion(
x,lo
w,h
igh)
;
qui
cks
ort(
x,l
ow,
p-
1);
qui
cks
ort(
x,p
+1,
hig
h);
}
}
int main()
{
int n,i;
int list[30];
cout<<"enter no of elements\n";
264
UNIT -3
cin>>n;
cout<<"enter
"<<n<<"
numbers ";
for(i=0;i<n;i+
+)
cin>
>list[
i];
quic
ksort
(list,
0,n-
1);
cout
<<"
after
sorti
ng\
n";
for(i
=0;i
<n;i
++)
cout
<<lis
t[i]<
<end
l;
return 0;
}
e
n
t
e
r
n
o
o
f
e
l
e
265
UNIT -3
m
e
n
t
s
5
enter 5 numbers 5 4 3 2 1
after sorting 1 2 3 4 5
Merge sort
Merge sort is a sorting technique based on divide and conquer technique. In
merge sort the unsorted list is divided into N sublists, each having one
element, because a list of one element is considered sorted. Then, it
repeatedly merge these sublists, to produce new sorted sublists, and at lasts
one sorted list is produced. Merge Sort is quite fast, and has a time
complexity of O(n log n).
Conceptually, merge sort works as follows:
1. Divide the unsorted list into two sub lists of about half the size.
2. Divide each of the two sub lists recursively until we have list sizes of
length 1, in which case the list itself is returned.
3. Merge the two sub lists back into one sorted list.
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
266
UNIT -3
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
e
s
t
d
;
void merge(int a[ ],int low,int mid,int high)
{
int temp[100];
267
UNIT -3
int i,j,k;
i
=
l
o
w
;
j
=
m
i
d
+
1
;
k
=
l
o
w
;
while((i<=mid)&&(j<=high))
{
if(a[i]<=a[j])
{
temp[k]=a[i];
++i;
}
el
s
e temp[k]=a[j];
{ ++j;
}
+
+
k;
}
if(i>mid)
{
while(j<=high)
{
temp[k]=a[j];
++j;
++k;
}
}
els
e
{
268
UNIT -3
while(i<=mid)
{
temp[k]=a[i];
++i;
++k;
}
}
for(
int
i=l
ow;
i<=
hig
h;i
++)
a[i]
=te
mp
[i];
}
void mergesort(int a[],int low,int high)
{
i
n
t
m
i
d
;
i
f
(
l
o
w
<
h
i
g
h
)
{
mid=(low+high)/
2;
mergesort(a,low,
mid);
mergesort(a,mid+
1,high);
merge(a,low,mid,
high);
}
}
269
UNIT -3
int main()
{
int n,i;
int list[30];
cout<<"e
nter no
of
elements
\n";
cin>>n;
cout<<"ent
er "<<n<<"
numbers ";
for(i=0;i<n
;i++)
c
i
n
>
>
l
i
s
t
[
i
]
;
m
e
r
g
e
s
o
r
t
(
l
i
s
t
,
0
,
n
-
1
)
;
270
UNIT -3
c
o
u
t
<
<
"
a
ft
e
r
s
o
rt
i
n
g
\
n
";
f
o
r(
i
=
0
;i
<
n
;i
+
+
)
c
o
u
t
<
<
li
st
[i
]
<
<
”\
t”
;
return 0;
}
RUN 1:
enter no of elements 5
enter 5 numbers 44 33 55 11 -1
271
UNIT -3
after sorting -1 11 33 44 55
Heap sort
It is a completely binary tree with the property that a parent is
always greater than or equal to either of its children (if they exist). first the
heap (max or min) is created using binary tree and then heap is sorted using
priority queue.
Steps Followed:
a) Start with just one element. One element will always satisfy heap property.
b) Insert next elements and make this heap.
c) Repeat step b, until all elements
are included in the heap. Steps of Sorting:
a) Exchange the root and last element in the heap.
b) Make this heap again, but this time do not include the last node.
c) Repeat steps a and b until there is no element left.
C++ program for implementation of Heap Sort
#
i
n
c
l
u
d
e
<
i
o
s
t
r
e
a
m
>
u
s
i
n
g
n
a
m
e
s
p
a
c
272
UNIT -3
e
s
t
d
;
// To heapify a subtree rooted with node i which is
// an index
in arr[]. n is
size of heap
void
heapify(int
arr[], int n,
int i)
{
int largest = i; //
Initialize largest
as root int L= 2*i
+ 1; // left = 2*i +
1
int R= 2*i + 2; // right = 2*i + 2
273
UNIT -3
// If left child is larger than root
if (L < n
&&
arr[L] >
arr[large
st])
largest =
L;
// If right child is
larger than largest
so far if (R < n
&& arr[R] >
arr[largest])
largest = R;
/
/
I
f
l
a
r
g
e
s
t
i
s
n
o
t
r
o
o
t
i
f
(
l
a
r
g
e
s
t
!
=
274
UNIT -3
i
)
{
swap(arr[i], arr[largest]);
// Recursively
heapify the affected
sub-tree heapify(arr,
n, largest);
}
}
void heapSort(int arr[], int n)
{ int i;
// Build
heap
(rearran
ge
array)
for ( i =
n/2-
1; i >=
0; i--)
heapify(arr, n, i);
// One by one
extract an element
from heap for ( i=n-
1; i>=0; i--)
{
//
Mo
ve
curr
ent
root
to
end
swa
p(ar
r[0]
,
arr[i
]);
// call max
heapify on the
reduced heap
heapify(arr, i,
0);
}
}
/* A utility function to
275
UNIT -3
print array of size n */
void printArray(int
arr[], int n)
{
for
(
i
n
t
i
=
0
;
i
<
n
;
+
+
i
)
c
o
u
t
<
<
a
r
r
[
i
]
<
<
"
"
;
cout << "\n";
}
int main()
{
int n,i;
int list[30];
cout<<"e
nter no
of
elements
\n";
276
UNIT -3
cin>>n;
cout<<"ent
er "<<n<<"
numbers ";
for(i=0;i<n
;i++)
c
i
n
>
>
l
i
s
t
[
i
]
;
h
e
a
p
S
o
r
t
(
l
i
s
t
,
n
)
;
cout
<<
"Sort
ed
array
is \n";
print
Array
(list,
n);
277
UNIT -3
return 0;
}
RUN 1:
enter no of elements 5
enter 5
numbers
11 99 22
101 1
Sorted
array is
1 11 22 99 101
Time complexities:
Algorithm Worst case Average case Best case
2 2
Bubble sort O(n ) O(n ) O(n2)
selection sort O(n2) O(n2) O(n2)
Insertion sort O(n2) O(n2) O(n2)
Quick sort O(n log n) O(n log n) O(n2)
Merge sort O(n log n) O(n log n) O(n log n)
Heap sort O(n log n) O(n log n) O(n log n)
Linear search O(n) O(n) O(1)
Binary search O(log n) O(log n) O(1)
278
UNIT -3
Terminology of Graph
Graphs:-
A graph G is a discrete structure consisting of nodes (called vertices) and
lines joining the nodes (called edges). Two vertices are adjacent to each
other if they are joint by an edge. The edge joining the two vertices is said
to be an edge incident with them. We use V (G) and E(G) to denote the set
of vertices and edges of G respectively.
279
UNIT -3
280
UNIT -3
Euler Circuit and Euler Path
An Euler circuit in a graph G is a simple circuit containing every edge of G.
An Euler path in G is a simple path containing every edge of G.
Graph Representations
Graph data structure is represented using following representations...
1. Adjacency Matrix
2. Incidence Matrix
3. Adjacency List
Adjacency Matrix
In this representation, graph can be represented using a matrix of size total number of
vertices by total number of vertices. That means if a graph with 4 vertices can be
represented using a matrix of 4X4 class. In this matrix, rows and columns both
represents 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
281
UNIT -3
vertex to column vertex.
For example, consider the following undirected graph representation...
Directed graph representation...
Incidence Matrix
In this representation, graph can be represented using a matrix of size total
number of vertices by total number of edges. That means if a graph with 4
vertices and 6 edges can be represented using a matrix of 4X6 class. In this
matrix, rows represents vertices and columns represents edges. This matrix
is filled with either 0 or 1 or -1. Here, 0 represents row edge is not
connected to column vertex, 1 represents row edge is connected as
outgoing edge to column vertex and -1 represents row edge is connected as
incoming edge to column vertex.
For example, consider the following directed graph representation...
Adjacency List
In this representation, every vertex of graph contains list of its adjacent vertices.
282
UNIT -3
For example, consider the following directed graph representation
implemented using linked list...
This representation can also be implemented using array as follows..
Graph traversals
Graph traversal means visiting every vertex and edge exactly once in a well-defined
order. While using certain graph algorithms, you must ensure that each vertex of the
graph is visited exactly once. The order in which the vertices are visited are
important and may depend upon the algorithm or question that you are solving.
During a traversal, it is important that you track which vertices have been visited.
The most common way of tracking vertices is to mark them.
Depth First Search (DFS)
The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It
involves exhaustive searches of all the nodes by going ahead, if possible, else by
backtracking.
Here, the word backtrack means that when you are moving forward and there are no
more nodes along the current path, you move backwards on the same path to find
nodes to traverse. All the nodes will be visited on the current path till all the
unvisited nodes have been traversed after which the next path will be selected.
283
UNIT -3
This recursive nature of DFS can be implemented using stacks. The
basic idea is as follows: Pick a starting node and push all its adjacent
nodes into a stack.
Pop a node from stack to select the next node to visit and push all its adjacent nodes into a
stack.
Repeat this process until the stack is empty. However, ensure that the nodes that are
visited are marked. This will prevent you from visiting the same node more than
once. If you do not mark the nodes that are visited and you visit the same node more
than once, you may end up in an infinite loop.
DFS-iterative (G, s): //Where G is graph
and s is source vertex let S be stack
[Link]( s ) //Inserting s in stack mark s as visited.
while ( S is not empty):
//Pop a vertex
from stack to
visit next v =
[Link]( )
[Link]( )
//Push all the neighbours of v in
stack that are not visited for all
neighbours w of v in Graph G:
if w
i
s
n
o
t
v
i
s
i
t
e
d
S
.
p
u
s
h
(
284
UNIT -3
)
mark w as visited
D
F
S
-
r
e
c
u
r
s
i
v
e
(
G
,
s
)
:
m
a
r
k
a
s
v
i
s
i
t
e
d
for all
neighbours w
of s in Graph
G: if w is not
visited:
285
UNIT -3
DFS-recursive(G, w)
286
UNIT -3
Breadth First Search (BFS);
There are many ways to traverse graphs. BFS is the most commonly used
[Link] is a traversing algorithm where you should start traversing from a
selected node (source or starting node) and traverse the graph layerwise thus
exploring the neighbour nodes (nodes which are directly connected to source node).
You must then move towards the next-level neighbour [Link] the name BFS
suggests, you are required to traverse the graph breadthwise as follows:
1. First move horizontally and visit all the
nodes of the current layer [Link] to the next
layer
287
UNIT -4
Dictionaries:- linear list representation, skip list representation, operations insertion, deletion and searching, has
DICTIONARIES:
Dictionary is a collection of pairs of key and value where every
value is associated with the corresponding key.
Basic operations that can be performed on dictionary are:
1. Insertion of value in the dictionary
2. Deletion of particular value from dictionary
3. Searching of a specific value with the help of key
Linear List Representation
The dictionary can be represented as a linear list. The linear list is a
collection of pair and value. There are two method of representing linear
list.
1. Sorted Array- An array data structure is used to implement the dictionary.
2. Sorted Chain- A linked list data structure is used to implement the dictionary
Structure of linear list for dictionary:
class dictionary
{
private:
i
n
t
k
,
d
a
t
a
;
s
t
r
u
c
t
n
o
d
e
{
p
u
b
l
i
288
UNIT -4
c
:
i
n
t
k
e
y
;
i
n
t
v
a
l
u
e
;
struct node *next;
} *head;
pu
bl d
ic: i
c
t
i
o
n
}; a
r
y
(
)
;
v
o
i
d
i
n
s
e
r
t
_
d
(
289
UNIT -4
) i
; s
p
v l
o a
i y
d _
d
d (
e
l )
e ;
t
e v
_ o
d i
( d
) l
; e
n
v g
o t
i h
d (
)
d ;
Insertion of new node in the dictionary:
Consider that initially
dictionary is empty
then head = NULL
We will create a new node with some key and value contained in it.
290
UNIT -4
Now as head is NULL, this new node becomes head. Hence the dictionary
contains only one record. this node will be ‘curr’ and ‘prev’ as well. The
‘cuur’ node will always point to current visiting node and ‘prev’ will always
point to the node previous to ‘curr’ node. As now there is only one node in
the list mark as ‘curr’ node as ‘prev’ node.
New/head/curr/prev
1 10 NULL
Insert a record, key=4 and value=20,
New
4 20 NULL
Compare the key value of ‘curr’ and ‘New’ node. If New->key > Curr->key
then attach New node to ‘curr’ node.
prev/head New curr->next=New
prev=curr
1 10 4 20 NULL
Add a new node <7,80> then
head/prev curr New
1 10 4 20 7 80 NULL
If we insert <3,15> then we have to search for it proper position
by comparing key value. (curr->key < New->key) is false. Hence
else part will get executed.
1 10 4 20
7 80 NULL
3 15
void dictionary::insert_d( )
{
node *p,*curr,*prev;
cout<<"Enter an key
and value to be
291
UNIT -4
inserted:"; cin>>k;
cin>>data;
292
UNIT -4
p
=
n
e
w
n
o
d
e
;
p
-
>
k
e
y
=
k
;
p
-
>
v
a
l
u
e
=
d
a
t
a
;
p
-
>
n
e
x
t
=
N
U
L
L
;
if(head==NULL)
head=p;
el {
s
e
293
UNIT -4
curr=head;
while((curr->key<p->key)&&(curr->next!=NULL))
{
p
r
e
v
=
c
u
r
r
;
c
u
r
r
=
c
u
r
r
-
>
n
e
x
t
;
}
if(curr->next==NULL)
{
if(curr->key<p->key)
{
c
u
} r
els r
e -
{ >
n
e
} } x
els t
e =
{ p
;
p
r
e
v
=
c
294
UNIT -4
u p- rev-
r > >ne
r n xt;
; e prev
x -
t >ne
= xt=
p p;
p
-
>
n
e
x
t
=
p
r
e
v
-
>
n
e
x
t
;
p
r
e
v
-
>
n
e
x
t
=
p
;
}
cout<<"\nInserted into dictionary Sucesfully.....\n";
}
}
The delete operation:
Case 1: Initially assign ‘head’ node as ‘curr’ [Link] ask for a key value
of the node which is to be deleted. Then starting from head node key value
of each jode is cked and compared with the desired node’s key value. We will
get node which is to be deleted in variable ‘curr’. The node given by
variable ‘prev’ keeps track of previous node of ‘cuu’ node. For eg, delete
node with key value 4 then
295
UNIT -4
cur
1 10 3 15 4 20 7 80 ULL
296
UNIT -4
Case 2:
If the node to
be deleted is
head node i.e..
if(curr==head
)
Then, simply make ‘head’ node as next node and delete ‘curr’
curr head
1 10 3 15 4 20 7 80 ULL
Hence the list becomes
head
3 15 4 20 7 80 ULL
void dictionary::delete_d( )
{
node*curr,*prev;
cout<<"Enter key value that
you want to delete..."; cin>>k;
if(head==NULL)
cout<<"\ndictionary is Underflow";
else
{ curr=head;
while(curr!=NULL)
{
if(curr->key==k)
b
r
e
a
k
;
p
r
297
UNIT -4
e
v
=
c
u
r
r
;
c
u
r
r
=
c
u
r
r
-
>
n
e
x
t
;
}
}
if(curr==NULL)
cout<<"Node not found...";
else
{
if(curr==head)
298
UNIT -4
head=curr->next;
else
prev->next=curr->next;
delete curr;
cout<<"Item deleted from dictionary...";
}
}
T
he
le
ng
th
op
er
ati
on
:
in
t
di
ct
io
na
ry
::l
en
gt
h(
)
{
s
t
r
u
c
t
n
o
d
e
*
c
u
r
r
;
i
299
UNIT -4
n
t
c
o
u
n
t
;
c
o
u
n
t
=
0
;
c
u
r
r
=
h
e
a
d
;
i
f
(
c
u
r
r
=
=
N
U
L
L
)
{
cou
t<<
”Th
e
list
is
em
pty
”;
retu
300
UNIT -4
rn
0;
}
while(curr!=NULL)
{
c
o
} u
return n
count; t
} +
+
;
c
u
r
=
c
u
r
r
-
>
n
e
x
t
;
SKIP LIST REPRESENTATION
Skip list is a variant list for the linked list. Skip
lists are made up of a series of nodes connected one after the other. Each
node contains a key and value pair as well as one or more references, or
pointers, to nodes further along in the list. The number of references each
node contains is determined randomly. This gives skip lists their
probabilistic nature, and the number of references a node contains is called
its node level.
There are two special nodes in the skip list one is head node which is the
starting node of the list and tail node is the last node of the list
1 2 3 4 5 6 7
head tail
node node
The skip list is an efficient implementation of dictionary using sorted
chain. This is because in skip list each node consists of forward
references of more than one node at a time.
301
UNIT -4
Eg:
null
Now to search any node from above given sorted chain we have to
search the sorted chain from head node by visiting each node. But this
searching time can be reduced if we add one level in every alternate
node. This extra level contains the forward pointer of some node. That
means in sorted chain come nodes can holds pointers to more than one
node.
NULL
If we want to search node 40 from above chain there we will require
comparatively less time. This search again can be made efficient if we add
few more pointers forward references.
NULL
skip list
Node structure of skip list:
tem
plate
<cla
ss
K,
class
E>
struc
t
skip
node
{
typedef
pair<const
K,E>
pair_type;
302
UNIT -4
pair_type
element;
skipnode<K,E> **next;
skipnode(const pair_type &New_pair, int MAX):element(New_pair)
{
next=new skipnode<K,E>*[MAX];
}
};
303
UNIT -4
The individual node looks like this:
Key value array of pointer
Element *next
Searching:
The desired node is searched with the help of a key value.
template<class K, class E>
skipnode<K,E>* skipLst<K,E>::search(K& Key_val)
{
skipnode<K,E>* Forward_Node = header; for(int i=level;i>=0;i--)
{
while (Forward_Node->next[i]->[Link] < key_val) Forward_Node = Forward_Node->next[i];
last[i] = Forward_Node;
}
return Forward_Node->next[0];
}
Searching for a key within a skip list begins with starting at header at the
overall list level and moving forward in the list comparing node keys to the
key_val. If the node key is less than the key_val, the search continues moving
forward at the same level. If o the other hand, the node key is equal to or
greater than the key_val, the search drops one level and continues forward.
This process continues until the desired key_val has been found if it is
present in the skip list. If it is not, the search will either continue at the end
of the list or until the first key with a value greater than the search key is
found.
Insertion:
There are two tasks that should be done before insertion operation:
1. Before insertion of any node the place for this new node in the skip
list is searched. Hence before any insertion to take place the search
routine executes. The last[] array in the search routine is used to keep
track of the references to the nodes where the search, drops down
one level.
2. The level for the new node is retrieved by the routine randomelevel()
template<class K,class E>
void skipLst<K,E>::insert(pair<K,E>& New_pair)
{
if(New_pair.key >= tailkey)
{
cout<<”Key is too large”;
}
skipNode<K,E>* temp =
search(New_pair.key);
if(temp->[Link] ==
New_pair.key)
10
UNIT -4
{
temp-
>[Link]=N
ew_pair.value;
return;
}
if*New_Level > levels)
{
Ne
w_
Lev
el =
+
+le
vels
;
last
[Ne
w_
Lev
el]
=
hea
der;
}
skipNode<K,E> *newNode = new
skipNode<K,E>(New_pair, New_Level+1); for(int
i=0;i<=New_Level;i++)
{
newNode-
>next[i] =
last[i]-
>next[i];
last[i]-
>next[i] =
newNode;
}
l
e
n
+
+
;
r
e
t
u
r
n
10
UNIT -4
;
}
Determining the level of each node:
template <class K, class E>
int skipLst<K,E>::randomlevel()
{
int lvl=0;
while(rand() <= Lvl_No) lvl=lvl+1; if(lvl<=MaxLvl)
return lvl; else
return MaxLvl;
}
Deletion:
First of all, the deletion makes use of search algorithm and searches the
node that is to be deleted. If the key to be deleted is found, the node
containing the key is removed.
template<class K, class E>
void skipLst<K,E>::delet(K& Key_val)
{
if(
ke
y_
val
>=t
ail
Ke
y)
ret
urn
;
skipNode<K,E>*
temp =
search(Key_val);
if(temp-
>[Link] !=
Key_val)
return;
for(int i=0;i<=levels;i++)
10
UNIT -4
{
if(last[i]-
>next[i]
== temp)
last[i]=>n
ext[i] =
temp-
>next[i];
}
while(level>0 &&
header->next[level] ==
tail) levels--;
d
e
l
e
t
e
t
e
m
p
;
l
e
n
-
-
;
}
HASH TABLE REPRESENTATION
Hash table is a data structure used for storing and retrieving data very
quickly. Insertion of data in the hash table is based on the key value.
Hence every entry in the hash table is associated with some key.
Using the hash key the required piece of data can be searched in the
hash table by few or more key comparisons. The searching time is
then dependent upon the size of the hash table.
The effective representation of dictionary can be done using hash
table. We can place the dictionary entries in the hash table using hash
function.
HASH FUNCTION
Hash function is a function which is used to put the data in the hash
table. Hence one can use the same hash function to retrieve the data
from the hash table. Thus hash function is used to implement the
hash table.
The integer returned by the hash function is called hash key.
For example: Consider that we want place some employee records in the hash
table The record of employee is placed with the help of key: employee ID.
10
UNIT -4
The employee ID is a 7 digit number for placing the record in the hash table.
To place the record 7 digit number is converted into 3 digits by taking only
last three digits of the key.
If the key is 496700 it can be stored at 0th position. The second key
8421002, the record of those key is placed at 2nd position in the array.
Hence the hash function will be- H(key) = key%1000
Where key%1000 is a hash function and key obtained by hash function is called hash key.
Bucket and Home bucket: The hash function H(key) is used to map
several dictionary entries in the hash table. Each position of the hash
table is called bucket.
The function H(key) is home bucket for the dictionary with pair whose value is key.
TYPES OF HASH FUNCTION
There are various types of hash functions that are used to place the record in the hash table-
1. Division Method: The hash function depends upon
the remainder of division. Typically the divisor is table
length.
For eg; If the record 54, 72, 89, 37 is placed in the hash table and if the table size is 10 then
10
UNIT -4
h(key) = record % table size 0
1
54%10=4 2 72
72%10=2 3
89%10=9 4 54
37%10=7 5
6
7 37
8
9 89
2. Mid Square:
In the mid square method, the key is squared and the middle or mid part of
the result is used as the index. If the key is a string, it has to be preprocessed
to produce a number.
Consider that if we want to place a record 3111 then
31112 = 9678321
for the hash
table of size
1000 H(3111)
= 783 (the
middle 3
digits)
3. Multiplicative hash function:
The given record is multiplied by some constant value. The formula for
computing the hash key is-
H(key) = floor(p *(fractional part of key*A)) where p is integer constant
and A is constant real number.
Donald Knuth suggested to use constant A = 0.61803398987
If key 107 and p=50 then
H(key) = floor(50*(107*0.61803398987))
= floor(3306.4818458045)
= 3306
At 3306 location in the hash table the record 107 will be placed.
4. Digit Folding:
The key is divided into separate parts and using some simple
operation these parts are combined to produce the hash key.
For eg; consider a record 12365412 then it is divided into separate parts as
123 654 12 and these are added together
H(key) = 123+654+12
= 789
The record will be placed at location 789
5. Digit Analysis:
The digit analysis is used in a situation when all the identifiers are
known in advance. We first transform the identifiers into numbers using some
10
UNIT -4
radix, r. Then examine the digits of each identifier. Some digits having most
skewed distributions are deleted. This deleting of digits is continued until the
number of remaining digits is small enough to give an address in the range
of the hash table. Then these digits are used to calculate the hash address.
10
UNIT -4
COLLISION
the hash function is a function that returns the key value using which the
record can be placed in the hash table. Thus this function helps us in placing
the record in the hash table at appropriate position and due to this we can
retrieve the record directly from that location. This function need to be
designed very carefully and it should not return the same hash key address for
two different records. This is an undesirable situation in hashing.
Definition: The situation in which the hash function returns the same hash key (home bucket) for more than one recor
Similarly when there is no room for a new pair in the hash table then
such a situation is called overflow. Sometimes when we handle collision it
may lead to overflow conditions. Collision and overflow show the poor
hash functions.
For example, 0
1 131
Consider a hash function. 2
3 43
H(key) = recordkey%10 having the hash table size of 10 4 44
5
The record keys to be placed are 6 36
7 57
131, 44, 43, 78, 19, 36, 57 and 77 8 78
131%10=1 9 19
44%10=4
43%10=3
78%10=8
19%10=9
36%10=6
57%10=7
77%10=7
Now if we try to place 77 in the hash table then we get the hash key to be 7
and at index 7 already the record key 57 is placed. This situation is called
collision. From the index 7 if we look for next vacant position at subsequent
indices 8.9 then we find that there is no room to place 77 in the hash table.
This situation is called overflow.
COLLISION RESOLUTION TECHNIQUES
If collision occurs then it should be handled by applying some
techniques. Such a technique is called collision handling technique.
1. Chaining
2. Open
addressing
(linear
probing)
[Link]
10
UNIT -4
probing
4. Double hashing
5.
D
o
u
b
l
e
h
a
s
h
i
n
g
6
.
R
e
h
a
s
h
i
n
g
10
UNIT -4
CHAINING
In collision handling method chaining is a concept which introduces an additional field with
data
i.e. chain. A separate chain table is maintained for colliding data. When
collision occurs then a linked list(chain) is maintained at the home
bucket.
For eg;
Consider the keys to be placed in
their home buckets are 131, 3, 4,
21, 61, 7, 97, 8, 9
then we will apply a hash
function as H(key) = key % D
Where D is the size of table. The
hash table will be- Here D = 10
0
1 131 21 61
NULL
3
NULL
61 NULL
131
97 NULL
7
A chain is maintained for colliding elements. for instance 131 has a
home bucket (key) 1. similarly key 21 and 61 demand for home bucket
1. Hence a chain is maintained at index 1.
OPEN ADDRESSING – LINEAR PROBING
This is the easiest method of handling collision. When collision occurs i.e.
when two records demand for the same home bucket in the hash table then
collision can be solved by placing the second record linearly down whenever
the empty bucket is found. When use linear probing (open addressing), the
hash table is represented as a one-dimensional array with indices that range
from 0 to the desired table size-1. Before inserting any elements into this
table, we must initialize the table to represent the situation where all slots are
empty. This allows us to detect overflows and collisions when we inset
elements into the table. Then using some suitable hash function the element
can be inserted into the hash table.
10
UNIT -4
For example:
Consider that following keys are to be
inserted in the hash table 131, 4, 8, 7,
21, 5, 31, 61, 9, 29
10
UNIT -4
Initially, we will put the following keys in the hash table.
We will use Division hash function. That means the keys are placed using the formula
H(
ke
y)
=
ke
y
%
ta
bl
esi
ze
H(
ke
y)
=
ke
y
%
10
For instance the
element 131 can be
placed at H(key) =
131 % 10
=1
Index 1 will be the home bucket for 131. Continuing in this
fashion we will place 4, 8, 7. Now the next key to be inserted is
21. According to the hash function
H(key)=21%10
H(key) = 1
But the index 1 location is already occupied by 131 i.e. collision occurs. To
resolve this collision we will linearly move down and at the next empty
location we will prob the element. Therefore 21 will be placed at the index
2. If the next element is 5 then we get the home bucket for 5 as index 5 and
this bucket is empty so we will put the element 5 at index 5.
Index
Key Key Key
NULL NULL NULL
0
131 131 131
10
NULL 21 21
UNIT -4
1
after placing keys 31, 61
10
UNIT -4
The next record key is 9. According to decision hash function it demands for
the home bucket 9. Hence we will place 9 at index 9. Now the next final
record key 29 and it hashes a key 9. But home bucket 9 is already
occupied. And there is no next empty bucket as the table size is limited to
index 9. The overflow occurs. To handle it we move back to bucket 0 and is
the location over there is empty 29 will be placed at 0th index.
Problem with linear probing:
One major problem with linear probing is primary clustering. Primary
clustering is a process in which a block of data is formed in the hash table
when collision is resolved.
Key
39
19%10 = 9 cluster is formed 29
18%10 = 8 8
39%10 = 9
29%10 = 9
8%10 = 8
re
st of the table is empty this cluster problem
18
can be solved by quadratic probing. 19
QUADRATIC PROBING:
Quadratic probing operates by taking the original hash value and adding
successive values of an arbitrary quadratic polynomial to the starting value.
This method uses following formula.
H(key) = (Hash(key) + i2) % m)
where m can be table size or any prime number.
for eg; If we have to insert following elements in the hash table with table size 10:
37, 90, 55, 22, 17, 49, 87 0 90
1 11
37 % 10 = 7 2 22
90 % 10 = 0 3
55 % 10 = 5 4
22 % 10 = 2 5 55
11 % 10 = 1 6
7 37
Now if we want to place 17 a collision will occur as 17%10 = 7 and 8
bucket 7 has already an element 37. Hence we will apply 9
quadratic probing to insert this record in the hash table.
Hi (key)
10
UNIT -4
(Hash(ke
y) + i2)
%m
Consider
i = 0 then
(17 + 02) % 10 = 7
10
UNIT -4
(17 + 12) % 10 = 8, when i =1
The bucket 8 is empty hence we will place the element at index 8. 90 0
Then comes 49 which will be placed at index 9. 11 1
2 22
49 % 10 = 9 3
4
5 55
6
7 37
8 49
9
Now to place 87 we will use quadratic probing.
0
90
(87 + 0) % 10 = 7
11 1
(87 + 1) % 10 = 8… but already occupied
(87 + 22) % 10 = 1.. already occupied 22 2
3
(87 + 32) % 10 = 6 45
It is observed that if we want place all the necessary elements in
the hash table the size of divisor (m) should be twice as large as 55 6
87 7
total number of elements.
37
8
49
9
DOUBLE HASHING
Double hashing is technique in which a second hash function is applied to the
key when a collision occurs. By applying the second hash function we will
get the number of positions from the point of collision to insert.
There are two important rules to be followed for the second function:
it must never evaluate to zero.
must make sure that all cells can be probed.
The formula to be used for double hashing is
where M is a prime number smaller than the size of the table.
H1(key) = key mod
Key
Consider the following elements to be placed in the
tablesize H2(key) = M –
hash table of size 10 37, 90, 45, 22, 17, 49, 55 90
Initially
(key mod M) insert the elements using
the formula for H1(key). Insert 37, 22
90, 45, 22
H1(37) = 37 % 10 = 7
H1(90) = 90 % 10 = 0 45
H1(45) = 45 % 10 = 5
H1(22) = 22 % 10 = 2
H1(49) = 49 % 10 = 9 37
49
10
UNIT -4
Now if 17 to be inserted then
Key
H1(17) = 17 % 10 = 7
90
H2(key) = M – (key % M)
17
Here M is prime number smaller than the size of 22
the table. Prime number smaller than table size
10 is 7
H 45
e
37
n
49
c
10
UNIT -4
)
=7–3=4
That means we have to insert the element 17 at 4 places e to
from 37. In short we ha jumps. Therefore the 17 will be
placed at index 1.
Now to insert number 55
H1(55) = 55 % 10 =5 Collision Key
90
H2(55) = 7-(55 % 7) 17
=7–6=1 22
That means we have to take one jump
from index 5 to place 55. Finally the
hash table will be - 45
55
37
49
Comparison of Quadratic Probing & Double Hashing
The double hashing requires another hash function whose
probing efficiency is same as some another hash function required when
handling random collision.
The double hashing is more complex to implement than quadratic
probing. The quadratic probing is fast technique than double hashing.
REHASHING
Rehashing is a technique in which the table is resized, i.e., the size of table
is doubled by creating a new table. It is preferable is the total size of table is a
10
UNIT -4
prime number. There are situations in which the rehashing is required.
When table is completely full
With quadratic probing when the table is filled half.
When insertions fail due to overflow.
10
UNIT -4
In such situations, we have to transfer entries from old table to the new
table by re computing their positions using hash functions.
Consider we have to insert the elements 37, 90, 55, 22, 17, 49, and 87. the
table size is 10 and will use hash function.,
H(key) = key mod tablesize
37 % 10 = 7
90 % 10= 0
55 % 10 = 5
22 % 10 = 2
17 % 10 = 7 Collision
solved by linear probing
49 % 10 = 9
Now this table is almost full and if we try to insert more elements collisions
will occur and eventually further insertions will fail. Hence we will rehash by
doubling the table size. The old table size is 10 then we should double this
size for new table, that becomes 20. But 20 is not a prime number, we will
prefer to make the table size as 23. And new hash function will be
H(key) key mod 23 900
1 11
37 % 23 = 14 2 22
90 % 23 = 21 3
55 % 23 = 9 4
22 % 23 = 22 555
17 % 23 = 17 876
49 % 23 = 3 377
87 % 23 = 18 498
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Now the hash table is sufficiently large to accommodate new insertions.
Advantages:
11
UNIT -4
1. This technique provides the programmer a flexibility to enlarge the table size if
required.
2. Only the space gets doubled with simple hash function
which avoids occurrence of collisions.
EXTENSIBLE HASHING
Extensible hashing is a technique which handles a large amount
of data. The data to be placed in the hash table is by extracting
certain number of bits.
Extensible hashing grow and shrink similar to B-trees.
In extensible hashing referring the size of directory the
elements are to be placed in buckets. The levels are
indicated in parenthesis.
For eg: Directory
1
0
Levels
(0)
00 11 data to
1 1 be
01 placed
0 in
bucket
The bucket can hold the data of its global depth. If data in
bucket is more than global depth then, split the bucket and
double the directory.
Consider we have to insert 1, 4, 5, 7, 8, 10. Assume each page can hold
2 data entries (2 is the depth).
Step 1:
Insert 1, 4 1 = 001
0
4 = 100
(0)
We will
001
examine last
010 bit of data
and insert
the data in
bucket.
11
UNIT -4
Insert 5. The bucket is full. Hence double the directory.
11
UNIT -4
1 = 001
0 1
4 = 100
(0) (1)
5 = 101
100 00
1 Based on
01 last bit the
0 data is
inserted.
Step 2: Insert 7
7 = 111
But as depth is full we can not insert 7 here. Then double the directory
and split the bucket. After insertion of 7. Now consider last two bits.
00 (2) (2)
01 10 11
(1) 00 11
Step 3: Insert 8 i.e. 1000 1 1
100 (2)01
00 010 10 11
00 11
(1) 1 1
100 01
1000 0
Step 4: 0
11
UNIT -4
Thus the data is inserted using extensible hashing.
Deletion Operation:
If we wan tot delete 10 then, simply make the bucket of 10 empty.
00 01 10 11
(1) (2) (2)
100 001 111
1000 101
Delete 7.
00 01 10 11
(1) (1)
100 001 Note that the level was increased
1000 101 when we insert 7. Now on deletion
of 7, the level should get decremented.
Delete 8. Remove entry from directory 00.
(1) (1)
00 00 10 11
100 00
1
10
1
Applications of hashing:
11
UNIT -4
1. In compilers to keep track of declared variables.
2. For online spelling checking the hashing functions are used.
3. Hashing helps in Game playing programs to store the moves made.
4. For browser program while caching the web pages, hashing is used.
5. Construct a message authentication code (MAC)
6. Digital signature.
7. Time stamping
8. Key updating: key is hashed at specific intervals resulting in new key
11
Binary Search Trees: Various Binary tree representation, definition, BST ADT, Implementation, Operations- Searching,
AVL Trees : Definition, Height of an AVL Tree, Operations – Insertion, Deletion and Searching
B-Trees: B-Tree of order m, height of a B-Tree, insertion, deletion and searching, B+ Tree.
TREES
A Tree is a data structure in which each element is attached to one or more elements directly
beneath it.
Level 0
A
B 1
C D
E F G
H I J
2
K L 3
Terminology
The connections between elements are called branches.
A tree has a single root, called root node, which is shown at the top of the
tree. i.e. root is always at the highest level 0.
Each node has exactly one node above it, called parent. Eg: A is the parent of B,C and
D.
The nodes just below a node are called its children. ie. child nodes are
one level lower than the parent node.
A node which does not have any child called leaf or terminal node. Eg: E, F, K, L, H,
I and M are
l ea v .
N o des with at least one child are called non terminal or internal nodes.
The child nodes of same parent are said to be siblings.
A path in a tree is a list of distinct nodes in which successive nodes are
connected by branches in the tree.
The length of a particular path is the number of branches in that path.
The degree of a node of a tree is the number of children of that node.
The maximum number of children a node can have is often
referred to as the order of a tree. The height or depth of a tree is
the length of the longest path from root to anyleaf.
1. Root: This is the unique node in the tree to which further sub trees are attached. Eg: A
Degree of the node: The total number of sub-trees attached to the node is
called the degree of the [Link]: For node A degree is 3. For node K
degree is 0
3. Leaves: These are the terminal nodes of the tree. The nodes with degree 0 are
115
always the leaf nodes. Eg: E, F, K, L,H, I, J
116
4. Internal nodes: The nodes other than the root node and the leaves are called
the internal nodes. Eg: B, C, D, G
5. Parent nodes: The node which is having further sub-trees(branches) is
called the parent node of those sub-trees. Eg: B is the parent node of E and
F.
6. Predecessor: While displaying the tree, if some particular node occurs
previous to some other node then that node is called the predecessor of the
other node. Eg: E is the predecessor of the node B.
7. Successor: The node which occurs next to some other node is a
successor node. Eg: B is the successor of E and F.
8. Level of the tree: The root node is always considered at level 0, then its
adjacent children are supposed to be at level 1 and so on. Eg: A is at level 0,
B,C,D are at level 1, E,F,G,H,I,J are at level 2, K,L are at level 3.
9. Height of the tree: The maximum level is the height of the tree. Here
height of the tree is 3. The height if the tree is also called depth of the tree.
10. Degree of tree: The maximum degree of the node is called the degree of the tree.
BINARY TREES
Binary tree is a tree in which each node has at most two children, a left child and
a right child. Thus the order of binary tree is 2.
A binary tree is
either empty or
consists of a) a
node called the
root
b) left and right sub trees are themselves binary trees.
A binary tree is a finite set of nodes which is either empty or consists of a
root and two disjoint trees called left sub-tree and right sub-tree.
In binary tree each node will have one data field and two pointer
fields for representing the sub-branches. The degree of each node in the binary tree
will be at the most two.
Types Of Binary Trees:
There are 3 types of binary trees:
1. Left skewed binary tree: If the right sub-tree is missing in every node of
a tree we call it as left skewed tree.
117
A
118
2. Right skewed binary tree: If the left sub-tree is missing in every node of
a tree we call it is right sub-tree.
C
3. Complete binary tree:
The tree in which degree of each node is at the most two is called a
complete binary tree. In a complete binary tree there is exactly one node at level
0, two nodes at level 1 and four nodes at level 2 and so on. So we can say that a
l
complete binary tree depth d will contain exactly 2 nodesat each level l, where l
is from 0 to d.
A
B C
D E F G
Note:
n
1. A binary tree of depth n will have maximum 2 -1 nodes.
2. A complete binary tree of level l will have maximum 2l nodes at each level, where l
starts from 0.
3. Any binary tree with n nodes will have at the most n+1 null branches.
4. The total number of edges in a complete binary tree with n terminal nodes are 2(n-1).
Binary Tree Representation
A binary tree can be represented mainly in 2 ways:
a) Sequential Representation
b) Linked Representation
a) Sequential Representation
The simplest way to represent binary trees in memory is the sequential
representation that uses one- dimensional array.
1) The root of binary tree is stored in the 1 st location of array
th
2) If a node is in the j location of array, then its left child is in the location 2J+1 and
its right
child in the location 2J+2
d+1
The maximum size that is required for an array to store a tree is 2 -1, where d is the depth of
the tree.
119
Advantages of sequential representation:
The only advantage with this type of representation is that the
direct access to any node can be possible and finding the parent or left children
of any particular node is fast because of the random access.
Disadvantages of sequential representation:
1. The major disadvantage with this type of representation is wastage of
memory. For example in the skewed tree half of the array is unutilized.
2. In this type of representation the maximum depth of the tree has to be
fixed. Because we have decide the array size. If we choose the array size
quite larger than the depth of the tree, then it will be wastage of the
memory. And if we coose array size lesser than the depth of the tree then
we will be unable to represent some part of the tree.
3. The insertions and deletion of any node in the tree will be costlier as other
nodes has to be adjusted at appropriate positions so that the meaning of
binary tree can bepreserved.
As these drawbacks are there with this sequential type of representation, we
will search for more flexible representation. So instead of array we will make use
of linked list to represent the tree.
b) Linked Representation
Linked representation of trees in memory is implemented using pointers.
Since each node in a binary tree can have maximum two children, a node in a
linked representation has two pointers for both left and right child, and one
information field. If a node does not have any child, the corresponding pointer
field is made NULL pointer.
In linked list each node will look like this:
Left Child Data Right Child
Advantages of linked representation:
1. This representation is superior to our array representation as
there is no wastage of memory. And so there is no need to
have prior knowledge of depth of the tree. Using dynamic
memory concept one can create as much memory(nodes) as
required. By chance if some nodes are unutilized one can
delete the nodes by making the address free.
2. Insertions and deletions which are the most common
120
operations can be done without moving the nodes.
121
Disadvantages of linked representation:
1. This representation does not provide direct access to a node and
special algorithms are required.
2. This representation needs additional space in each node for
storing the left and right sub- trees.
TRAVERSING A BINARY TREE
Traversing a tree means that processing it so that each node is visited
exactly once. A binary tree can be
traversed a number of [Link] most common tree traversals are
In-order
Pre-order and
Post-order
Pre-order [Link] the root Root | Left | Right
[Link] the left sub tree in pre-order
[Link] the right sub tree in pre-order.
In-order [Link] the left sub tree in in-order Left | Root | Right
2. Visit the root
3. Traverse the right sub tree in in-order.
Post-order [Link] the left sub tree in post- Left | Right | Root
order
[Link] the right sub tree in post-
order. [Link] the root
B C
D E F G
H I J
K
The pre-order
traversal is:
ABDEHCFGIKJ The
in-order traversal is :
DBHEAFCKIGJ The
post-order traversal
is:DHEBFKIJGCA
122
Inorder Traversal:
rd
Print 3
A
nd th
Print 2 Print 4
B D
C Print this E
at the last
st
Print 1
C-B-A-D-E is the inorder traversal i.e. first we go towards the leftmost node. i.e. C so print
that node
C. Then go back to the node B and print B. Then root node A then move towards
the right sub-tree print D and finally E. Thus we are following the tracing
sequence of Left|Root|Right. This type of traversal is called inorder traversal. The
basic principle is to traverse left sub-tree then root and then the right sub-tree.
Pseudo Code:
template <class T>
void inorder(bintree<T> *temp)
{
if(temp!=NULL)
{
i
n
o
r
d
e
r
(
t
e
m
p
-
>
l
e
f
t
)
;
c
o
u
t
123
<
<
”
t
e
m
p
-
>
d
a
t
a
”
;
i
n
o
r
d
e
r
(
t
e
m
p
-
>
r
i
g
h
t
)
;
}
}
is the preorder traversal of the above fig. We are following Root|Left|
Right path i.e. data at the root node will be printed first then we move on
the left sub-tree and go on printing the data till we reach to the left most
node. Print the data at that node and then move to the right sub- tree.
Follow the same principle at each sub-tree and go on printing the data
124
accordingly.
template <class T>
void preorder(bintree<T> *temp)
125
{
if(temp!=NULL)
{
cout<<”temp->data”; preorder(temp->left);
preorder(temp->right);
}
}
From figure the postorder traversal is C-D-B-E-A. In the postorder traversal
we are following the Left|Right|Root principle i.e. move to the leftmost node,
if right sub-tree is there or not if not then print the leftmost node, if right sub-
tree is there move towards the right most node. The key idea here is that at
each sub-tree we are following the Left|Right|Root principle and print the data
accordingly.
Pseudo Code:
template <class T>
void postorder(bintree<T> *temp)
{
if(temp!=NULL)
{
po
sto
rd
er(
te
m
p-
>l
eft
);
po
sto
rd
er(
te
m
p-
>ri
126
gh
t);
co
ut
<<
”te
m
p-
>d
ata
”;
}
}
BINARY SEARCH TREE
In the simple binary tree the nodes are arranged in any fashion.
Depending on user’s desire the new nodes can be attached as a left or right child
of any desired node. In such a case finding for any node is a long cut
procedure, because in that case we have to search the entire tree. And thus the
searching time complexity will get increased unnecessarily. So to make the
searching algorithm faster in a binary tree we will go for building the binary
search tree. The binary search tree is based on the binary search algorithm.
While creating the binary search tree the data is systematically arranged. That
means values at left sub-tree < root node value < right sub-tree values.
127
Operations On Binary Search Tree:
The basic operations which can be performed on binary search tree are.
1. Insertion of a node in binary search tree.
2. Deletion of a node from binary search tree.
3. Searching for a particular node in binary search tree.
Insertion of a node in binary search tree.
While inserting any node in binary search tree, look for its appropriate
position in the binary search tree. We start comparing this new node with each
node of the tree. If the value of the node which is to be inserted is greater than
the value of the current node we move on to the right sub-branch otherwise
we move on to the left sub-branch. As soon as the appropriate position is
found we attach this new node as left or right child appropriately.
Before Insertion
In the above fig, if we wan to insert 23. Then we will start comparing 23 with value of
root node
i.e. 10. As 23 is greater than 10, we will move on right sub-tree. Now we will
compare 23 with 20 and move right, compare 23 with 22 and move right.
Now compare 23 with 24 but it is less than
24. We will move on left branch of 24. But as there is node as left child of
24, we can attach 23 as left child of 24.
128
Deletion of a node from binary search tree.
For deletion of any node from binary search tree thereare three which are possible.
i. Deletion of leaf node.
ii. Deletion of a node having one child.
iii. Deletion of a node having two children.
Deletion of leaf node.
This is the simplest deletion, in which we set the left or right pointer of parent node as NULL.
10
7 15
Before
deletio
n
5 9 12 18
From the above fig, we want to delete the node having value 5 then we will set
left pointer of its parent node as NULL. That is left pointer of node having value
7 is set to NULL.
129
Deletion of a node having one child.
130
To explain this kind of deletion, consider a tree as given below.
If we want to delete
the node 15, then we
will simply copy
node 18 at place of 16
and then set the node
free
Deletion of a node having two children.
Consider a tree as given below.
131
Let us consider that we want to delete node having value 7. We will then find
out the inorder successor of node 7. We will then find out the inorder successor
of node 7. The inorder successor will be simply copied at location of node 7.
That means copy 8 at the position where value of node is 7. Set left
pointer of 9 as NULL. This completes the deletion procedure.
Searching for a node in binary search tree.
In searching, the node which we want to search is called a key node. The key
node will be compared with each node starting from root node if value of key
node is greater than current node then we search for it on right sub branch
otherwise on left sub branch. If we reach to leaf node and still we do not get
the value of key node then we declare “node is not present in the tree”.
132
In the above tree, if we want to search for value 9. Then we will compare 9
with root node 10. As 9 is less than 10 we will search on left sub branch. Now
compare 9 with 5, but 9 is greater than 5. So we will move on right sub tree.
Now compare 9 with 8 but 9 is greater than 8 we will move on right sub
branch. As the node we will get holds the value 9. Thus the desired node can be
searched.
AVL TREES
Adelsion Velski and Lendis in 1962 introduced binary tree
structure that is balanced with respect to height of sub trees. The
tree can be made balanced and because of this retrieval
of any node
Fromcanthe be done in (log n) times, where n is total number of
nodes. Ο of these scientists the tree is called AVL
name
tree.
Definition:
An empty tree is height balanced if T is a non empty binary
tree with TL and TR as its left and right sub trees. The T is height
balanced if and only if
i. TL and TR are height balanced.
ii. hL-hR <= 1 where hL and hR are heights of TL and TR.
The idea of balancing a tree is obtained by calculating the balance factor of a tree.
Definition of Balance Factor:
The balance factor BF(T) of a node in binary tree is defined to be
hL-hR where hL and hR are heights of left and right sub trees of T.
For any node in AVL tree the balance factor i.e. BF(T) is -1, 0 or +1.
133
Height of AVL Tree:
Theorem: The height of AVL tree with n elements (nodes) is O(log n).
Proof: Let an AVL tree with n nodes in it. Nh be the minimum number of
nodes in an AVL tree of height h.
In worst case, one sub tree may have height h-1 and other sub tree may have
height h-2. And both these sub trees are AVL trees. Since for every node in
AVL tree the height of left and right sub trees differ by at most 1.
Hence
Nh = Nh-1+Nh-2+1
Where Nh denotes the minimum number of nodes in an
AVL tree of height h. N0=0 N1=2
134
W
e
c
a
n
a
l
s
o
w
r
i
t
e
i
t
a
s
N
>
N
h
=
N
h
-
1
+
N
h
-
2
+
1
> 2Nh-2
> 4Nh-4
.
.
> 2iNh-2i
If value of
h is even,
let i = h/2-1
135
Then
equation
becomes
N > 2h/2-1N2
= N > 2(h-1)/2x4 (N2 = 4)
= O(log N)
If value of h is odd, let I = (h-1)/2
then equation becomes N > 2(h-
1)/2 N1
N > 2(h-1)/2 x 1
H = O(log N)
This proves that height of AVL tree is always O(log N). Hence search,
insertion and deletion can be carried out in logarithmic time.
Representation of AVL Tree
The AVL tree follows the property of binary search tree. In fact
AVL trees are basically binary search trees with balance
factors as -1, 0, or +1.
After insertion of any node in an AVL tree if the balance factor
of any node becomes other than -1, 0, or +1 then it is said
that AVL property is violated. Then we have to restore the
destroyed balance condition. The balance factor is denoted at
right top corner inside the node.
136
After insertion of a new node if balance condition gets destroyed, then the
nodes on that path(new node insertion point to root) needs to be
readjusted. That means only the affected sub tree is to be rebalanced.
The rebalancing should be such that entire tree should satisfy AVL property.
In above given example-
137
Insertion of a node.
There are four different cases when rebalancing is required after insertion of new node.
1. An insertion of new node into left sub tree of left child. (LL).
2. An insertion of new node into right sub tree of left child. (LR).
3. An insertion of new node into left sub tree of right child. (RL).
4. An insertion of new node into right sub tree of right child.(RR).
Some modifications done on AVL tree in order to rebalance it is called rotations of
AVL tree
There are two types of rotations:
Single rotation Double rotation
Left-Left(LL rotation) Left-Right(LR rotation)
Right-Right(RR rotation) Right-Left(RL rotation)
Insertion Algorithm:
1. Insert a new node as new leaf just as an ordinary binary search tree.
2. Now trace the path from insertion point(new node inserted as leaf)
towards root. For each node ‘n’ encountered, check if heights of left (n)
and right (n) differ by at most 1.
a) If yes, move towards parent (n).
b) Otherwise restructure by doing either a single rotation or a double rotation.
Thus once we perform a rotation at node ‘n’ we do not require to perform
any rotation at any ancestor on ‘n’.
138
When node ‘1’ gets inserted as a left child of node ‘C’ then AVL property
gets destroyed i.e. node A has balance factor +2.
The LL rotation has to be applied to rebalance the nodes.
2. RR rotation:
When node ‘4’ gets attached as right child of node ‘C’ then node ‘A’ gets
unbalanced. The rotation which needs to be applied is RR rotation as shown in
fig.
139
When node ‘3’ is attached as a right child of node ‘C’ then unbalancing
occurs because of LR. Hence LR rotation needs to be applied.
When node ‘2’ is attached as a left child of node ‘C’ then node ‘A’ gets
unbalanced as its balance factor becomes -2. Then RL rotation needs to be
applied to rebalance the AVL tree.
Example:
Insert 1, 25, 28, 12 in the following AVL tree.
140
Insert 1
To insert node ‘1’ we have to attach it as a left child of ‘2’. This will
unbalance the tree as follows. We will apply LL rotation to preserve AVL
property of it.
Insert 25
We will attach 25 as a right child of 18. No balancing is required as entire
tree preserves the AVL property
141
Insert 28
The node ‘28’ is attached as a right child of 25. RR rotation is required to rebalance.
142
Insert 12
To rebalance the tree we have to apply LR rotation.
143
Deletion:
Even after deletion of any particular node from AVL tree, the tree has to be
restructured in order to preserve AVL property. And thereby various
rotations need to be applied.
Algorithm for deletion:
The deletion algorithm is more complex than insertion algorithm.
1. Search the node which is to be deleted.
2. a) If the node to be deleted is a leaf node then simply make it NULL to remove.
b) If the node to be deleted is not a leaf node i.e. node may have one or
two children, then the node must be swapped with its inorder successor.
Once the node is swapped, we can remove this node.
3. Now we have to traverse back up the path towards
root, checking the balance factor of every node
along the path. If we encounter unbalancing in
some sub tree
then balance that sub tree using
appropriate single or double rotations. The
deletion algorithm takes O(log n) time to delete
any node.
144
The tree becomes
145
Searching:
The searching of a node in an AVL tree is very simple. As AVL tree is basically
binary search tree, the algorithm used for searching a node from binary search
tree is the same one is used to search a node from AVL tree.
The searching of a node from AVL tree takes O(log n) time.
BTREES
Multi-way trees are tree data structures with more than two branches
at a node. The data structures of m-way search trees, B trees and Tries
belong to this category of tree structures.
AVL search trees are height balanced versions of binary search trees,
provide efficient retrievals and storage operations. The complexity of
insert, delete and search operations on AVL search trees id O(log n).
Applications such as File indexing where the entries in an index may
be very large, maintaining the index as m-way search trees provides a
better option than AVL search trees which are but only balanced
binary search trees.
While binary search trees are two-way search trees, m-way search
trees are extended binary search trees and hence provide efficient
retrievals.
B trees are height balanced versions of m-way search trees and
they do not recommend representation of keys with varying sizes.
Tries are tree based data structures that support keys with varying sizes.
146
UNIT -5
Definition:
A B tree of order m is an m-way search tree and hence may be empty. If non
empty, then the following properties are satisfied on its extended tree
representation:
i. The root node must have at least two child nodes and at most m child nodes.
ii. All internal nodes other than the root node must have at least |m/2 | non empty
child nodes and at most m non empty child nodes.
iii. The number of keys in each internal node is one less than its number of
child nodes and these keys partition the keys of the tree into sub trees.
iv. All external
nodes are at the
samelevel. v.
Example:
F K O B tree of order 4
Level 1
G M N
C D P Q W
S T X Y Z
Insertion Level 3
For example construct a B-tree of order 5 using following numbers. 3, 14, 7, 1, 8, 5, 11, 17,
13, 6, 23, 12,
20, 26, 4, 16, 18, 24, 25, 19
The order 5 means at the most 4 keys are allowed. The internal node should
have at least 3 non empty children and each leaf node must contain at least 2
keys.
Step 1: Insert 3, 14, 7, 1
1 3 7 14
147
UNIT -5
Step 2: Insert 8, Since the node is full split the node at medium 1, 3, 7, 8, 14
1 5, 11,317 which can be easily inserted in
Step 3: Insert 8 a B-tree.
14
1 3 5 8 11 14 17
Step 4: Now insert 13. But if we insert 13 then the leaf node will have 5 keys which
is not allowed. Hence 8,
11, 13, 14, 17 is split and medium node 13 is moved up.
7 13
1 3 5 8 11 14
17
148
UNIT -5
Step 5: Now insert 6, 23, 12, 20 without any split.
7 13
1 3 5 6 8 11 12 14 17 20 23
Step 6: The 26 is inserted to the right most leaf node. Hence 14, 17, 20, 23, 26 the node
is split and 20 will be moved up.
7 13 20
1 3 5 6 8 11 12 14 17 23 26
149
UNIT -5
Step 7: Insertion of node 4 causes left most node to split. The 1, 3, 4, 5, 6 causes key 4 to move
up.
Then insert 16, 18, 24, 25.
4 7 13 20
Step 8: Finally insert 19. Then 4, 7, 13, 19, 20 needs to be split. The median
1 3 13 will be moved
5 8 node.
6 to from a root
up 11 12 14 16 17 18 23 24 25 26
The tree then will be -
13
4 7 17 20
8 11 12 14 16
1Thus the
3 B tree is
5 constructed.
6 18 19 23 24 25 26
13
Deletion
Consider a B-tree
17 20
4 7
1 3 5 6 8 11 12 14 16 18 19 23 24 25 26
150
UNIT -5
Delete 8, then it
is very simple.
13
4 7 17 20
1 3 5 6 11 12 14 16 18 19 23 24 25 26
Now we will delete 20, the 20 is not in a leaf node so we will find its successor
which is 23, Hence 23 will be moved up to replace 20.
13
4 7 17 23
1 3 we will delete
Next 5 11 of 1812from the corresponding
618. Deletion 14 16 node18causes19the 24 25 26
node with only one key, which is not desired (as per rule 4) in B-tree of order
5. The sibling node to immediate right has an extra key. In such a case we can
borrow a key from parent and move spare key of sibling up.
151
UNIT -5
13
17
4 724
1 Now3 delete 5. 5But deletion
6 of 511is not 12
easy. The first1 thing
4 is165 is from
19 leaf 23
node. 25 26
Secondly this leaf node has no extra keys nor siblings to immediate left or right.
In such a situation we can combine this node with one of the siblings. That means
remove 5 and combine 6 with the node 1, 3. To make the tree balanced we have to
move parent’s key down. Hence we will move 4 down as 4 is between 1, 3, and 6.
The tree will be-
13
7
17 24
1 3 4 6 19B-tree.
But again internal node of 7 11 12only one key which
contains 1 4 not allowed
16 in 23We 25 26
then will try to borrow a key from sibling. But sibling 17, 24 has no spare key. Hence
we can do is that, combine 7 with 13 and 17,
24. Hence the B-tree will be
152
UNIT -5
7 13 17 24
1
25 326 4 6 11 12 14 16 19 23
Searching
The search operation on B-tree is similar to a search to a search on binary search tree.
Instead of choosing between a left and right child as in binary tree, B-tree makes an m-
way choice. Consider a B-tree as given below.
13
4 7
17
20
1 3 5 6 8 11 12 14 16 18 19 23 24 25 26
If we want to search 11 then
i. 11 < 13 ; Hence search left node
ii. 11 > 7 ; Hence right most node
iii. 11 > 8 ; move in second block
iv. node 11 is found
153
UNIT -5
The running time of search operation depends upon the height of the tree. It is O(log n).
Height of B-tree
The maximum height of B-tree gives an upper bound on number of disk access.
The maximum number of keys in a B-tree of order 2m and depth h is
2 h-1
1 + 2m + 2m(m+1) + 2m(m+1) + . . .+ 2m(m+1)
h
i-1
= 1 + ∑ 2m(m+1)
i=1
The maximum height of B-tree with n keys
log m+1 n = O(log n)
2m
154
B+ Trees
Most implementations use the B-tree variation, the B+-tree.
In the B-tree, every value of the search field appears once at
some level in the tree, along with the data pointer to the record,
or block where the record isstored.
In a B+ tree, data pointers are stored only at the leaf nodes,
therefore the structure of the leaf nodes vary from the
structure of the internal (non leaf)nodes.
If the search field is a key field, the leaf nodes have a value
for every value ofthe search field, along with the data pointer to
the record or block.
If the search field is a non key field, the pointer points to a
block containing pointers to the data file records, creating an
extra level of indirection (similar to option 3 for the secondary
indexes)
The leaf nodes of the B+ Trees are linked to provide ordered
access on the search field to the record. The first level is
similar to the base level of anindex.
Some search field values in the leaf nodes are repeated in
the internal nodes of the B+ trees, in order to guide the
search.
B+ Tree Example
3 7 8
13 5 67 8 912
B+ Tree Internal Node Structure
1. Each internal node is of the form <P1, K1, P2, K2, …., Pq-1,
Kq-1, Pq>, where q<=p and each Pi is a tree pointer.
2. Within each internal node, K1 < K2 < ….< Kq-1.
3.
For all search field values X in the subtree pointed at by Pi, we have:
Ki-1 < X <= Ki for 1 < i < q;
X <=K for i = 1;
and Ki-1 < X for i = q.
4.
Each internal node has at most, p tree pointers.
5.
Each internal node, except the root, has at least p/2 tree
pointers. The root node has at least two tree pointers if it is
an internal node.
6.
An internal node with q pointers, q <=p, has q-1 search field values.
155
B+ Tree Leaf Node Structure
1. Each leaf node is of the form, <<K1, Pr1>, <K2, Pr2>,… ,<Kq-1,
Prq-1>, Pnext> where q<=p, each Pri is a data pointer, and Pnext
points to the next leaf node of the B+ tree.
2. Within each leaf node, K1 < K2 < …< Kq-1,q<=p
3. Each Pri is a data pointer that points to the record whose search
field value is Ki, or to a file block containing the record (or a
block of pointers if the search field is not a key field)
4.
Each leaf node has at least p/2 values.
5.
All leaf nodes are at the same level.
B+ Tree Information
By starting at the leftmost block, it is possible to traverse leaf
nodes as a linked list using the Pnext pointers. This provides
ordered access to the data records on the indexing field.
Entries in internal nodes of a B+ tree include search values
and tree pointers, without any data pointers, more entries can
be stored into an internal node ofa B+ tree, than for a B-tree.
Therefore the order p will be larger for a B+ tree, which
leads to fewer B+ tree levels, improving the search time.
The order p can be different for the internal and
leaf nodes, because of the structural differences
of the nodes.
Example 6 from Text
To calculate the order p of a B+ Tree. suppose the search key field is
V = 9 bytes long, the block size is B = 512 bytes, a record pointer is
Pr = 7 bytes and a block pointer is P = 6 bytes. An internal node of
the B+ trees can have up to p tree pointers and p – 1 search field
values, which must fit into a single block.
Calculate the value of p for an internal node:
56 bytes
9 bytes
p
*
P
(
p
-
1
)
*
V
<
=
5
1
2
156
p
*
6
(
p
-
1
)
*
9
<
=
5
1
2
6
p
9
p
–
9
<
=
5
1
2
15p <= 522
p = 34 which means that each internal node can hold up to 34 tree
pointers, and 33 search key values.
Calculate the value of p for a leaf node:
1 3 6 bytes
9 bytes
7 bytes
(plea
f)*((
Pr +
V))
+P
<=
512
16ple
157
af + 6
<=
512
pleaf <= 506/16
158
pleaf = 31 which means each leaf node can hold up to pleaf = 31
value/data pointer combinations, assuming data pointers are record
pointers.
Example 7 from Text
Suppose that we construct a B+ tree on the field of Example 6. To
calculate the approximate number of entries of the B+ tree we
assume that each node is 69 percent full. On average, each internal
node will have 34 * 0.69 or approximately 23 pointers, and hence 22
values.
Each leaf node, on the average will hold 0.69*pleaf = 0.69*31 or
approximately 21 data record pointers. A B+ tree will have the
following average number of entries at each level.
R
1 22 23 pointers
oo
node entries 529 pointers
t:
23 506
Le
nodes entries
ve
l
1:
Level 2: 529 nodes 11,638 entries 12,167 pointers
Leaf Level: 12,167 nodes 255,507 record pointers
When we compare this result with the previous B-tree example
(Example 5), we can see that the B+ tree can hold up to 255,507
record pointers, whereas a corresponding B-tree can only hold
65,535 entries.
Insertion and Deletion with B+-trees.
The following example has p
= 3, and pleaf = 2 Points to
Note:
Every key value must exist at the leaf level, because all
data pointers are atthe leaf level,
Every value appearing in an internal node, also appears as the
rightmost value in the leaf level of the subtree pointed at by the
tree pointer to the left of the value.
When a leaf node is full, and a new entry is inserted there, the
node overflows and must be split. The first j = (pleaf+1)/2
entries (in the example 2 entries) in the original node are kept
there, and the remaining entries are moved to the new leaf
node. The entry at position j is copied/replicated and moved to
the parentnode.
When an internal node is full, and a new entry is to be
inserted, the node overflows and must be split into 2 nodes.
The entry at position j is moved to the parent node. The first
j-1 entries are kept in the original node, and the last j+1
entries are moved to the new node.
To practice B+ Tree insertion, complete Exercise 14.15 in Chapter 14 of the course text.
159
You might also like
- 1q.explain The Classification of Data StructureNo ratings yet1q.explain The Classification of Data Structure6 pages
- Understanding Data Structures and ArraysNo ratings yetUnderstanding Data Structures and Arrays36 pages
- Understanding Data Structures & AlgorithmsNo ratings yetUnderstanding Data Structures & Algorithms85 pages
- 1-Introduction To Data Structure and C ProgrammingNo ratings yet1-Introduction To Data Structure and C Programming116 pages
- Introduction to Data Structures ExplainedNo ratings yetIntroduction to Data Structures Explained40 pages
- Applications of Stacks in Data StructuresNo ratings yetApplications of Stacks in Data Structures28 pages
- Data Structures and Algorithms OverviewNo ratings yetData Structures and Algorithms Overview57 pages
- Introduction to Data Structures & AlgorithmsNo ratings yetIntroduction to Data Structures & Algorithms33 pages
- Introduction to Data Structures & AlgorithmsNo ratings yetIntroduction to Data Structures & Algorithms26 pages
- Understanding Data Structures and TypesNo ratings yetUnderstanding Data Structures and Types53 pages
- Data Structures and Algorithms OverviewNo ratings yetData Structures and Algorithms Overview74 pages
- Introduction to Data Structures & AlgorithmsNo ratings yetIntroduction to Data Structures & Algorithms59 pages
- Data Structures and Algorithms OverviewNo ratings yetData Structures and Algorithms Overview65 pages
- Advanced Data Structures Course OverviewNo ratings yetAdvanced Data Structures Course Overview95 pages
- Understanding Data Structures in ComputingNo ratings yetUnderstanding Data Structures in Computing138 pages
- Introduction to Data Structures OverviewNo ratings yetIntroduction to Data Structures Overview9 pages
- Understanding Python Variables and TypesNo ratings yetUnderstanding Python Variables and Types21 pages
- Java Classes, Objects, and Methods GuideNo ratings yetJava Classes, Objects, and Methods Guide27 pages
- Core Java, JDBC, Servlet, JSP, Struts, Hibernate, Spring FAQsNo ratings yetCore Java, JDBC, Servlet, JSP, Struts, Hibernate, Spring FAQs5 pages
- Simplifying Boolean Expressions with K-MapsNo ratings yetSimplifying Boolean Expressions with K-Maps19 pages
- Understanding Generics in Programming 2No ratings yetUnderstanding Generics in Programming 227 pages
- Python Functions: Built-in & User-DefinedNo ratings yetPython Functions: Built-in & User-Defined57 pages
- Area Calculation in Java Using InterfacesNo ratings yetArea Calculation in Java Using Interfaces10 pages