UNIT I - LINEAR STRUCTURES

Abstract Data Types (ADTs) – ADTs and classes -Overview of linked lists, operations on single
linked list – Doubly linked list and Circular linked list and its operations. Implementing
problems on Linked Lists: Search a book in a list. Reverse Names list using doubly linked list.

Data Structures

Data Structure is a branch of Computer Science. It is a specialized format for

organizing, processing, retrieving and storing data efficiently in the memory of a
computer. As applications are becoming more complex and the amount of data is increasing
every day, it may lead to problems with data searching, processing speed, multiple requests
handling, and many more. Data Structures support different methods to organize, manage,
and store data efficiently.

Classification of Data structure

Based on how data is organized, data structures can be classified into two types – linear
data structures and non-linear data structures. Array, Linked list, Stack and Queue are
linear data structures. Array is a static linear data structure with fixed memory size and the
array elements can be accessed easily. Linked list, Stack and Queue are dynamic linear data
structures in which memory size is not fixed and changes randomly. In linear data structures
data is organized sequentially.

Graph and trees are non-linear data structures. The data elements of graphs and trees are
not organized sequentially and all the elements cannot be accessed easily in a single run.

Array data structure

An array is a linear data structure that contains elements of the same data type and
stores them in contiguous and adjacent memory locations.

Array elements are accessed using their indices / subscripts and the
index of first element is always 0.

Array elements can be accessed quickly using their index.

Arrays have a fixed memory size and cannot be changed.
There are two types of arrays – one –dimensional arrays and multi-
dimensional arrays (arrays with 2 or more dimensions).

One-dimensional array example

Syntax to declare a one-dimensional array

Array-type array-name[size];

Example

int arr[5];

Initializing a 1D Array

Example 1: int a[]={10,20,30,40,50};

Example 2: int b[5] = {1,2,3,4,5};

Accepting input for a 1D array

int arr[5], i; Execution output:

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

printf(“\n Enter value for arr[%d] “,i);

scanf(“%d”,&arr[i]);

Printing the elements of the above array

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

printf("%d\t",arr[i]);

Two-dimensional array example

Syntax to declare a two-dimensional array

Array-type array-name[rows][cols];

Example

int marks[5][3]; // to store 5 students 3 subject marks

Initializing a 1D Array

Example 1: int marks[5][3]={90,80,70,60,50,40,50,60,70,80,70,60,95,92,93};

Example 2: int marks[5][3] = {

{90, 80, 70},

{60, 50, 40},

{50, 60, 70},

{80, 70, 60},

{95, 92, 93}

};

Accepting input for a 1D array

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

{
printf("\nEnter mark for student %d ",i+1);
for(j=0 ; j<=2 ; j++)
{
printf("\n Enter mark for subject %d ",j);
scanf("%d",&marks[i][j]);
}
Printing the elements of the above array

printf("Displaying student marks \n");

for(i=0 ; i <=4 ; i++)
{
for(j=0 ; j<=2 ; j++)
printf("%d\t",marks[i][j]);
printf("\n");

Deleting element from a 1D array

The algorithm to delete an element from an array is given below:

Step 1: Search for the given element in the given array. If element found note the index and
goto Step 2, otherwise goto Step 3.
Step 2: Shift all the elements from index + 1 by 1 position to the left.
Step 3: Display the message ‘Element not found’.

Example 1:

int arr[5] = {10,20,30,40,50}, searchvalue=30, i, index= -1, n=5;

//searching for value 30
for(i=0 ; i<n ; i++)
{
if (searchvalue == arr[i])
{
index = i;
break;
}
}
if ( index == -1)
printf(“Search value not found…”);
else
{
//shifting elements to left by 1 position
for(i=index+1 ; i<n ; i++)
arr[i-1] = arr[i];
}

Advantages of Array data structure

 Array elements are stored in contiguous memory locations and hence they can be
accessed easily and quickly. They also consume less memory.

Drawbacks of Array data structure

 Memory for an array is allocated during compile-time and they have a fixed size.
Hence there may be wastage of memory space.
Linked List

 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.
 Linked List forms a series of connected nodes, where each node stores the data and the
address of the next node.
 Node Structure: A node in a linked list typically consists of two components:
Data: It holds the actual value or data associated with the node.
Next Pointer: It stores the memory address (reference) of the next node in the
sequence.
 Head and Tail: The linked list is accessed through the head node, which points to the
first node in the list. The last node in the list points to NULL or null pointer, indicating
the end of the list. This node is known as the tail node.

Advantages of linked list

 Linked list is a dynamic data structure for which memory can be allocated or de-
allocated dynamically during run-time. Hence memory is utilized efficiently.
 Insertion and deletion of elements can be done quickly.

Types of linked list

1. Single or Singly linked list

• In this type of linked list, each node contains reference of next node.
• Traversing a single linked list is done in forward direction.
• Applications: used for memory management (allocation and de-allocation of
memory), used in database indexing for faster insert and delete operations, used to
represent polynomials and sparse matrices, used in operating system for scheduling
processes and managing system resources.
2. Double or doubly linked list

• Each node contains references to both the next and previous nodes.
• Allows traversal in both forward and backward directions.
•
3. Circular linked list

• The last node points back to the head node, creating a circular structure.
• It can be either singly or doubly linked.

Operations on Linked Lists

1. Insertion: Adding a new node to a linked list involves adjusting the pointers of the
existing nodes to maintain the proper sequence. Insertion can be performed at the
beginning, end, or any position within the list
2. Deletion: Removing a node from a linked list requires adjusting the pointers of the
neighboring nodes to bridge the gap left by the deleted node. Deletion can be performed
at the beginning, end, or any position within the list.
3. Searching: Searching for a specific value in a linked list involves traversing the list
from the head node until the value is found or the end of the list is reached.

Singly linked list

Structure definition for singly linked list node.

Data addr

 A node in a singly linked list has two parts – data and address of next node.
 A structure is defined to represent nodes of a singly linked list. The members in the
structure definition must include data / datum of any data type and a pointer variable of
same structure type to store address of next node.
 Example

struct node
{
int data;
struct node *next;
};
 The following pointer variables must be declared for the above struct definition.
*head – to store address of first node
*tail – to store address of last node
*n – to store new node data
*ptr – to traverse the nodes in the list.

Structure definition along with pointer variables

struct node
{
int data;
struct node *next;
}*head, *tail, *n, *ptr;

 Creating a new node.

 To create a new node memory should be allocated for the pointer *n
n = (struct node *) malloc( sizeof(struct node));
 Accept input for new node data
scanf(“%d”,&n->data);
 Adding node to a singly linked list.
 A new node can be added in the beginning or end of the list. It can also be
inserted in between the nodes of the list.
 To add a new node check if list is empty by verifying if head==NULL.
 If list is empty, make new node as head node and tail node
head= tail = n;
 The next pointer of new node must be made to point to NULL.
n->next = NULL;
tail

head 10 NULL

n
 If list is not empty, and new node is added at the beginning of the list
n->next = head; //new node next is made to point to existing head node
head = n; //new node is made head node
head head tail

25 30 15 NULL

n
 If list is not empty and new node is added at the end of the list
tail->next = n; //last node next is made to point to new node
tail = n; // new node is made tail node
head tail tail

30 15 25 NULL

n
 If list is not empty and new node is inserted between two nodes then locate the
node after which the new node is inserted and it is called previous node.
The next of previous node is made to point to new node and new node next is
made to point to already existing previous node next.
head tail

30 15 25 NULL

previous previous --> next

Inserting new node after previous

head tail

30 15 5 25
NULL

previous n previous  next

 Traversing the nodes in a singly linked list.

head tail

30 15
NULL
5 25

 Visiting each node in a singly linked list is known as traversal.

 Traversal should start from head node and continue till the tail node.
 A pointer variable is initially made to point to head node and is then made to
point to next node until the tail node is reached.

head tail

NULL
30 15 5
ptr 25

head tail

NULL

30 15 5 25

ptr

head tail

NULL
30 15 5 25

ptr

head tail

NULL
30 15 5 25

ptr

head tail

NULL
30 15 5 25

ptr
 for loop or while loop may be used for traversing a singly linked list.
for( ptr = head ; ptr != NULL ; ptr = ptr->next)
OR
ptr = head;
while (ptr != NULL)
{
ptr = ptr  next;
}

Deleting node from a singly linked list

 Accept data of node to be removed as input from user.

 Traverse the list to locate the node.
 If node located is head node, make the next node as new head
node and free the memory of the located node.

head head tail

NULL
30 15 25

ptr (node located)

 If node located is tail node, make previous node as tail node and
free the memory of the located node.

head tail tail

30 15 25 NULL

ptr (node located)

 If node located is in between two nodes, link the previous node

with the next node. Free the memory of the located node.

head tail

NULL
30 15 5 25

ptr (node located)

/* C program to manage a singly linked list */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
}*head, *tail, *ptr, *n;
//function to create a new node
void createnode()
{
//allocate memory for the new node
n = (struct node *) malloc( sizeof(struct node) );
//accept input for new node data
printf("\nEnter data for new node ");
scanf("%d",&n->data);
}
//function to add node in the beginning
void addbeg()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
n->next = NULL;
}
else
{
n->next = head;
head = n;
}
printf("\nNew node inserted at the beginning of the list");
}
//function to add node at the end of the list
void addend()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
}
else
{
tail->next = n;
tail = n;
}
n->next=NULL;
printf("\nNew node inserted at the end of the list");
}
//function to insert node in between
void insert()
{
int s, flag=0;
if ( head == NULL )
{
printf("\nEmpty list...Cannot insert...\n");
return;
}
printf("\nEnter search node data ");
scanf("%d",&s);
//locate the node containing search data s
for(ptr=head; ptr!=NULL; ptr=ptr->next)
{
if (ptr->data == s)
{
flag=1; //search node located
break;
}
}
if (flag==0)
printf("\nSearch node not located...Cannot insert...\n");
else
{
createnode(); //function call to create a new node
n->next = ptr->next;
ptr->next = n;
printf("\nNode inserted...\n");
}
}
//function to delete node from the list containing data x
void delnode(int x)
{
struct node *previous, *t;
int flag=0;
if (head==NULL)
{
printf("\nEmpty list...Cannot delete...\n");
return;
}
for(ptr=previous=head; ptr!=NULL ; ptr=ptr->next)
{
if (ptr->data == x)
{
flag=1; //search node located
break;
}
previous=ptr;
}
if (flag==0)
printf("\nSearch node does not exist...Cannot delete...\n");
else
{
if (ptr==head && ptr==tail)
{
printf("\nDeleting single node\n");
free(ptr);
head=tail=NULL;
}
else if (ptr==tail) //deleting tail node
{
printf("\nDeleting tail node\n");
t=tail; //store tail node address in pointer t
tail=previous; //make previous node as tail node
free(t); //free memory
tail->next=NULL;
}
else if (ptr==head)
{
printf("\nDeleting head node\n");
t=ptr;
head = head->next;
free(t);
}
else
{
printf("\nDeleting node in between \n");
t=ptr;
previous->next = ptr->next;
free(t);
}
printf("\nNode deleted...\n");
}
}
//function to display data in all the nodes
void display()
{
if (head==NULL)
{
printf("\nEmpty list\n");
return;
}
for(ptr=head; ptr!=NULL; ptr=ptr->next)
printf("%d\n",ptr->data);
}
/* main() function */
int main()
{
int choice, d;
head = tail = NULL;
do
{
printf("\n1.Add node in the beginning\n");
printf("\n2.Add node at the end\n");
printf("\n3.Insert node\n");
printf("\n4.Delete node\n");
printf("\n5.Display data in all the nodes\n");
printf("\n6.Exit \n");
printf("Enter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
addbeg();
break;
case 2:
addend();
break;
case 3:
insert();
break;
case 4:
printf("Enter data of node to delete ");
scanf("%d",&d);
delnode(d);
break;
case 5:
display();
break;
case 6:
exit(0);
break;
default:
printf("\nInvalid choice\n");
}

}while (choice!=6);
return 0;
}

Doubly linked list

Structure definition for doubly linked list node.

addr Data addr

A node in a doubly linked list has three parts – address of previous node, data and address of
next node.
 A structure is defined to represent nodes of a doubly linked list. The members in the
structure definition must include data / datum of any data type and a pointer variable of
same structure type to store address of next node and previous node.
 Example

struct node
{
int data;
struct node *next, *prev;
};

 The following pointer variables must be declared for the above struct definition.
*head – to store address of first node
*tail – to store address of last node
*n – to store new node data
*ptr – to traverse the nodes in the list.

Structure definition along with pointer variables

struct node
{
int data;
struct node *next, *prev;
}*head, *tail, *n, *ptr;

Adding node to a doubly linked list.

Inserting a new node in a doubly linked list is very similar to inserting new node in linked list.
There is a little extra work required to maintain the link of the previous node. A node can be
inserted in a Doubly Linked List in four ways:
 At the front of the Doubly linked list.
 In between two nodes : Either after a given node or before a given node.
 At the end of the Doubly linked list.
 To add a new node check if list is empty by verifying if head==NULL.

Adding new node to empty list

 Make new node as head node and tail node

head= tail = n;
 The next and prev pointer of new node must be made to point to NULL.
n->next = NULL; n->prev = NULL;
tail head

NULL
NULL 10

n
Adding new node to the beginning of list containing nodes

n->next = head; //new node next is made to point to existing head node
head->prev = n; //head node prev pointer is made to point to new node
head = n; //new node is made head node
head head tail
NULL
NULL 4
2 3
2

n
Adding node at the end of the list

 If list is not empty and new node is added at the end of the list
tail->next = n; //last node next is made to point to new node
tail = n; // new node is made tail node
head tail tail

NULL 4 NULL
2 3
2

n
Inserting new node in between

 If list is not empty and new node is inserted between two nodes then locate the
node after which the new node is inserted and it is called previous node.
The next of previous node is made to point to new node and new node prev is
made to point to this previous node.
The new node next is made to point to already existing next of the previous
node. The previous node next previous is made to point to the new node..

head tail

NULL NULL
4
2 2 3
2

Traversing the nodes in doubly linked list

 Traversing a doubly linked list can be done in both directions, forward and reverse.
 To traverse the list in forward direction, start from head node and access the other nodes using
next pointer till the last node.
head tail

NULL NULL
4
2 2 3
2

ptr

 To traverse the list in reverse direction, start from tail node and access the previous nodes
using prev pointer till the head node.

head tail

NULL NULL
4
2 2 3
2

ptr
Deleting node from doubly linked list

 Accept data of node to be removed as input from user.

 Traverse the list to locate the node.
 If node located is head node, make the next node as new head
node and the prev pointer of new head is made to point to NULL.
The memory of the located node is freed.
head head tail

NULL NULL
30 15 25

ptr (node located)

 If node located is tail node, make previous node as tail node and
the next pointer of previous node must be made to point to NULL.
The memory of the located node is freed.

head tail tail

30 15 25 NULL
NULL
ptr (node located)
 If node located is in between two nodes, link the previous node
with the next node. Free the memory of the located node.

head tail

NULL
30 15 5 25

ptr (node located)

Advantages of Doubly Linked List over the singly linked list:

 A Doubly linked list can be traversed in both forward and backward directions.
 The delete operation in Doubly linked list is more efficient if a pointer to the node to be
deleted is given.
 We can quickly insert a new node before a given node.
 In a singly linked list, to delete a node, a pointer to the previous node is needed. To get this
previous node, sometimes the list is traversed. In Doubly linked list, we can get the previous
node using the previous pointer.

Disadvantages of Doubly Linked List over the singly linked list:

 Every node of Doubly linked list requires extra space for a previous pointer.
 All operations require an extra pointer previous to be maintained.

Applications of Doubly Linked List:

 It is used by web browsers for backward and forward navigation of

web pages
 LRU ( Least Recently Used ) / MRU ( Most Recently Used ) Cache are
constructed using Doubly Linked Lists.
 Used by various applications to maintain undo and redo
functionalities.
 In Operating Systems, a doubly linked list is maintained by thread
scheduler to keep track of processes that are being executed at that
time.

/* C program to manage a doubly linked list */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next, *prev;
}*head, *tail, *ptr, *n;
//function to create a new node
void createnode()
{
//allocate memory for the new node
n = (struct node *) malloc( sizeof(struct node) );
//accept input for new node data
printf("\nEnter data for new node ");
scanf("%d",&n->data);
}
//function to add node in the beginning
void addbeg()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
n->next = NULL;
n->prev = NULL;
}
else
{
n->next = head;
head->prev = n;
head = n;
n->prev = NULL;
}
printf("\nNew node inserted at the beginning of the list");
}
//function to add node at the end of the list
void addend()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
n->prev = NULL;
}
else
{
tail->next = n;
n->prev = tail;
tail = n;
}
n->next=NULL;
printf("\nNew node inserted at the end of the list");
}
//function to insert node in the list
void insert()
{
int s, flag=0;
if (head==NULL)
{
printf("\nEmpty list...Cannot insert new node...\n");
return;
}
printf("\nEnter search node data ");
scanf("%d",&s);
//locate the node containing search data s
for(ptr=head; ptr!=NULL; ptr=ptr->next)
{
if (ptr->data == s)
{
flag=1; //search node located
break;
}
}
if (flag==0)
printf("\nSearch node not located...Cannot insert new node...\n");
else
{
printf("\nSearch node located...\n");
createnode(); //function call to create a new node
if (ptr!=tail)
{
n->next = ptr->next;
ptr->next->prev = n;
ptr->next = n;
n->prev = ptr;
printf("\nNode inserted in between...\n");
}
else if (ptr==tail)
{
tail->next = n;
n->prev = tail;
tail = n;
n->next = NULL;
printf("\nNode inserted at the tail end...\n");
}
}
}
//function to delete node from the list containing data x
void delnode(int x)
{
struct node *t;
int flag=0;
if (head==NULL)
{
printf("\nEmpty list...Cannot delete node...\n");
return;
}
for(ptr=head; ptr!=NULL ; ptr=ptr->next)
{
if (ptr->data == x)
{
flag=1; //search node located
break;
}

}
if (flag==0)
printf("\nSearch node does not exist...\n");
else
{
if (ptr==head && ptr==tail)
{
free(ptr);
head=tail=NULL;
printf("\nNode deleted...List is empty...\n");
}
else if (ptr==tail) //deleting tail node
{
t=tail; //store tail node address in pointer t
tail=tail->prev; //make previous node as tail node
tail->next = NULL;
free(t); //free memory
printf("\nTail node deleted...\n");
}
else if (ptr==head)
{
t=ptr;
head = head->next;
head->prev = NULL;
free(t);
printf("\nHead node deleted...\n");
}
else
{
t=ptr;
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
free(t);
printf("\nNode in between deleted...\n");
}

}
}
//function to display data in all the nodes
void display()
{
if (head==NULL)
{
printf("\nEmpty list...\n");
return;
}
for(ptr=head; ptr!=NULL; ptr=ptr->next)
printf("%d\n",ptr->data);
}
/* main() function */
int main()
{
int choice, d;
head = tail = NULL;
do
{
printf("\n1.Add node in the beginning\n");
printf("\n2.Add node at the end\n");
printf("\n3.Insert node\n");
printf("\n4.Delete node\n");
printf("\n5.Display data in all the nodes\n");
printf("\n6.Exit \n");
printf("Enter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
addbeg();
break;
case 2:
addend();
break;
case 3:
insert();
break;
case 4:
printf("Enter data of node to delete ");
scanf("%d",&d);
delnode(d);
break;
case 5:
display();
break;
case 6:
exit(0);
break;
default:
printf("\nInvalid choice\n");
}
}while (choice!=6);
return 0;
}

Circular linked list

 In a circular linked list, the first node and the last node are connected to
each other to form a circle. There is no NULL pointer at the end.
 Example

 There are two types of circular linked list: Circular Singly linked list and Circular
Doubly linked list.
 Circular Singly linked list

 Circular Doubly linked list

Structure definition for Circular singly linked list node.

Data addr

 A node in a singly linked list has two parts – data and address of next node.
 A structure is defined to represent nodes of a singly linked list. The members in the
structure definition must include data / datum of any data type and a pointer variable of
same structure type to store address of next node.
 Example

struct node
{
int data;
struct node *next;
};

 The following pointer variables must be declared for the above struct definition.
*head – to store address of first node
*tail – to store address of last node
*n – to store new node data
*ptr – to traverse the nodes in the list.
Structure definition along with pointer variables

struct node
{
int data;
struct node *next;
}*head, *tail, *n, *ptr;

 Creating a new node.

 To create a new node memory should be allocated for the pointer *n
n = (struct node *) malloc( sizeof(struct node));
 Accept input for new node data
scanf(“%d”,&n->data);
 Adding a node to a Circular singly linked list.
 A new node can be added in the beginning or end of the list. It can also be
inserted in between the nodes of the list.
 To add a new node check if list is empty by verifying if head==NULL.
 If list is empty, make new node as head node and tail node
head= tail = n;
 The next pointer of new node must be made to point to head node.
n->next = head;
tail

head 10

n
 If list is not empty, and new node is added at the beginning of the list
n->next = head; //new node next is made to point to existing head node
head = n; //new node is made head node
tail->next = head; //tail node next is made to point to new head
head head tail

n 25 30 15
 If list is not empty and new node is added at the end of the list
tail->next = n; //last node next is made to point to new node
tail = n; // new node is made tail node
head tail tail

30 15 25

 If list is not empty and new node is inserted between two nodes then locate the
node after which the new node is inserted and it is called previous node.
The next of previous node is made to point to new node and new node next is
made to point to already existing previous node next.
head tail

30 15 25

Inserting new node after previous

head tail

30 15 5 25

previous n previous  next

 Traversing the nodes in a singly linked list.

head tail

30 15 5 25

 Visiting each node in a singly linked list is known as traversal.

 Traversal should start from head node and continue till the tail node.
 A pointer variable is initially made to point to head node and is then made to
point to next node until the tail node is reached.

head tail

30 15
ptr 5 25

ptr

head tail

30 15 5 25

ptr

head tail

30 15 5 25

ptr

head tail

30 15 5 25

ptr
 do..while loop is suitable for traversing a Circular singly linked list.
ptr = head;
do
{
ptr = ptr  next;
}while(ptr!=head);

Deleting node from a Circular singly linked list

 Accept data of node to be removed as input from user.
 Traverse the list to locate the node.
 If node located is head node, make the next node as new head
node and free the memory of the located node.
head head tail

30 15 25

ptr (node located)

 If node located is tail node, make previous node as tail node and
free the memory of the located node.

head tail tail

30 15 25

ptr (node located)

 If node located is in between two nodes, link the previous node

with the next node. Free the memory of the located node.

head tail

30 15 5 25

ptr (node located)

/* C program to manage a circular singly linked list */

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
}*head, *tail, *ptr, *n;
//function to create a new node
void createnode()
{
//allocate memory for the new node
n = (struct node *) malloc( sizeof(struct node) );
//accept input for new node data
printf("\nEnter data for new node ");
scanf("%d",&n->data);
}
//function to add node in the beginning
void addbeg()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
n->next = tail;
}
else
{
n->next = head;
head = n;
tail->next=head;
}
printf("\nNew node inserted at the beginning of the list");
}
//function to add node at the end of the list
void addend()
{
createnode(); //function call to create a node
if (head==NULL) //list is empty
{
tail = head = n; //new node is head node and tail node
}
else
{
tail->next = n;
tail = n;
tail->next = head;
}

printf("\nNew node inserted at the end of the list");

}
//function to insert node in between
void insert()
{
int s, flag=0;
if (head==NULL)
{
printf("\nEmpty list\n");
return;
}
printf("\nEnter search node data ");
scanf("%d",&s);
//locate the node containing search data s
for(ptr=head; ptr!=NULL; ptr=ptr->next)
{
if (ptr->data == s)
{
flag=1; //search node located
break;
}
}
if (flag==0)
printf("\nSearch node not located...\n");
else
{
createnode(); //function call to create a new node
n->next = ptr->next;
ptr->next = n;
printf("\nNode inserted...\n");
}
}
//function to delete node from the list containing data x
void delnode(int x)
{
struct node *previous, *t;
int flag=0;
if (head==NULL)
{
printf("\nEmpty list...\n");
return;
}
for(ptr=previous=head; ptr!=NULL ; ptr=ptr->next)
{
if (ptr->data == x)
{
flag=1; //search node located
break;
}
previous=ptr;
}
if (flag==0)
printf("\nSearch node does not exist...\n");
else
{
if (ptr==head && ptr==tail)
{
free(ptr);
head=tail=NULL;
}
else if (ptr==tail) //deleting tail node
{
t=tail; //store tail node address in pointer t
tail=previous; //make previous node as tail node
tail->next = head;
free(t); //free memory
}
else if (ptr==head)
{
t=ptr;
head = head->next;
tail->next = head;
free(t);
}
else
{
t=ptr;
previous->next = ptr->next;
free(t);
}
printf("\nNode deleted...\n");
}
}
//function to display data in all the nodes
void display()
{
if (head==NULL)
{
printf("\nEmpty list...\n");
return;
}
ptr=head;
do
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}while(ptr!=head);

}
/* main() function */
int main()
{
int choice, d;
head = tail = NULL;
do
{
printf("\n1.Add node in the beginning\n");
printf("\n2.Add node at the end\n");
printf("\n3.Insert node\n");
printf("\n4.Delete node\n");
printf("\n5.Display data in all the nodes\n");
printf("\n6.Exit \n");
printf("Enter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
addbeg();
break;
case 2:
addend();
break;
case 3:
insert();
break;
case 4:
printf("Enter data of node to delete ");
scanf("%d",&d);
delnode(d);
break;
case 5:
display();
break;
case 6:
exit(0);
break;
default:
printf("\nInvalid choice...\n");
}

}while (choice!=6);
return 0;
}
UNIT II - STACK AND QUEUE DATA STRUCTURE

Overview of Stack data structure, push and pop operations on stack using array and linked
list- Queue ADT – double ended queues. Problems on Stack: evaluation of expression,
balanced parenthesis, string reverse using stack. Overview of Queue data structure, insert and
delete operations on Queue using array and linked list. Implement Queue based programs:
generate binary no’s using queue 1 to N.

Overview of Stack data structure

 A stack is a linear data structure in which the insertion of a new element and removal of an
existing element takes place at the same end represented as the top of the stack.
 All operations in a Stack are performed in LIFO (Last In First Out) order.
 Real life examples:
 Stack Of plates – plates in a canteen placed one on top of another

 Stack of book – books placed one on stop of another.

 Stack of chairs – plastic chairs placed one on top of another.

 Stack follows LIFO (Last In First Out) strategy. According to this strategy the item that is inserted last will
come out first.
 A top pointer is always used to maintain top of stack.
 Basic operations that can be carried out on a stack are
 Push – Inserting an element into the stack
 Pop – Removing an element from stack

 Stack can be implemented using array or linked list.

Array implementation of stack Program Execution
#include <stdio.h>
int MAXSIZE = 5;
int stack[MAXSIZE];
int top = -1;

/* Check if the stack is empty */

int isempty(){
if(top == -1)
return 1;
else
return 0;
}

/* Check if the stack is full*/

int isfull(){
if(top == MAXSIZE - 1)
return 1;
else
return 0;
}

/* Function to delete from the stack */

int pop(){
int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
}
else
{
return -1;
}
}

/* Function to insert into the stack */

void push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Stack is full...\n");
}
}

/* Function to display stack elements */

void display()
{
int i;
printf("\nDisplaying stack elements \n");
for(i=0;i<=top;i++)
printf("%d\n",stack[i]);
}
/* main() function */
int main()
{
char ans='y';
int x, choice;
while (ans=='y')
{
printf("1.Push\n");
printf("2.Pop\n");
printf("3.Display\n");
printf("\nEnter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
printf("Enter data to push ");
scanf("%d",&x);
push(x);
break;
case 2:
x = pop();
if ( x != -1)
printf("Popped value is %d \n",x);
else
printf("Stack is empty\n");
break;
case 3:
display();
break;
default:
printf("Invalid choice \n");
}
printf("\n Continue y / n ?");
fflush(stdin);
scanf("%c",&ans);
}
return 0;
}
The drawback with the array implementation of stack is the array size is fixed before data is
stored, hence stack gets filled up (stack overflow) and no more elements can be pushed to
stack.
Hence linked list implementation of stack is suitable for pushing any number of elements into
the stack.

/* C program to manage a stack using linked list implementation*/

#include <stdio.h>
#include <stdlib.h> Program Output
struct node
{
int data;
struct node *next;
}*top, *ptr, *n;
//function to create a new node
void createnode()
{
//allocate memory for the new node
n = (struct node *) malloc( sizeof(struct node) );
//accept input for new node data
printf("\nEnter data for new node ");
scanf("%d",&n->data);
}
//function to push node to stack
void push()
{
createnode(); //function call to create a node
if (top==NULL) //stack is empty
{
top = n; //new node is added to top of stack
n->next = NULL;
}
else
{
n->next = top;
top = n;
}
printf("\nNew node placed at top of the stack...\n");
}
//function to delete node from the list containing data x
int pop()
{
int a;
if (top==NULL)
{
printf("\nEmpty stack\n");
return -1;
}
ptr=top;
a = ptr->data;
top=top->next;
return a;

//function to display data in all the nodes

void display()
{
if (top==NULL)
{
printf("\nStack is Empty\n");
return;
}
for(ptr=top; ptr!=NULL; ptr=ptr->next)
printf("%d\n",ptr->data);
}
/* main function */

int main()
{
int choice, d;
top = NULL;
do
{
printf("\nChoose your stack operation");
printf("\n1.Push");
printf("\n2.Pop");
printf("\n3.Display");
printf("\n4.Exit\n");
printf("Enter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
push();
break;
case 2:
d=pop();
if (d != -1)
printf("\nPopped %d from stack \n",d);
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nInvalid choice\n");
}

}while (choice!=4);
return 0;
}

Problems on Stack: evaluation of expression

 Arithmetic expression comprises of arithmetic operators (+, -, *, /) and operands.

Example: 5 * 4 + 2 - 1
 Arithmetic expressions can be written in 3 forms – infix, prefix and postfix
 When operators are used in between the operands, it is known as infix expression.
Example: 5 + 2 (5 and 2 are operands, + is the operator)
 When operators are used before operands, it is known as prefix expression.
Example: +52
 When operators are used after operands, it is known as postfix expression.
Example: 52+
 We can convert infix expression to postfix or prefix expression.
Example 1: Infix expression  5 + 4 * 3 - 2
Postfix expression  5 + 43* + 2  543*+ - 2  543*+2-
Example 2: Infix expression  5 * 3 – 2 * 4
Postfix expression  53* - 24*  53*24*-
 We can convert infix expression to prefix expression
Example 1: Infix expression  5 + 4 * 3 - 2
Prefix expression  5 + *43 + 2  +5*43 - 2  +5-*432
Example 2: Infix expression  5 * 3 – 2 * 4
Prefix expression  *53 - *24  -53*24*

Evaluating postfix expression using a stack

 Postfix expression can be evaluated using a stack.

 Iterate the expression from left to right and keep on storing the operands into a stack.
 When an operator is received, pop the two topmost elements from the stack and evaluate them.
 Push the result back into the stack again.

Consider the expression: exp = “2 3 1 * + 9 -“

Step 1: The first element is 2 which is an operand, so push it into the stack.

Stack

Step 2: The second element is 3 which is an operand, so push it into stack.

Stack

Step 3: The third element is 1 which is an operand, so push it into stack.

Stack
Step 4: The fourth element is * which is an operator. Pop two operands 1 and 3 from stack and using the
operator * evaluate the expression 3 * 1 and push the result 3 back into the stack.

Step 5: The fifth element is + which is an operator. Pop two operands 3 and 2 from stack and using the
operator + evaluate the expression 2 + 3 and push the result 5 back into the stack.

Step 5: The sixth element is 9 which is an operand, so push it into the stack.

Step 6: The last element is - which is an operator. Pop two operands 9 and 5 from stack and using the
operator - evaluate the expression 5 - 9 and push the result -4 back into the stack.

Step 7: There are no more elements, so pop the element -4 from top of stack and display it as result of the
expression.

/* C program to evaluate postfix expression using stack */

#include <stdio.h>
#include <ctype.h>
#define SIZE 20
int stack[SIZE];
char expr[SIZE];
int top = -1;
int i;
//function to push element into stack
void push( int x )
{
if (top==SIZE-1)
printf("\n\tStack is full\n");
else
{
stack[++top]= x;
}
}
//function to pop element from stack
int pop()
{
int a;
if (top==-1)
{
printf("\n\tStack is empty\n");
return -1;
}
else
{
return stack[top--];
}
}
/* main() function */
int main()
{
int a,b;
printf("\n\tEnter postfix expression : ");
scanf("%s",expr);
for(i=0; expr[i] != '\0' ; i++)
{
if (isdigit(expr[i]))
push(expr[i]-48);
else
{
b = pop();
a = pop();
switch(expr[i])
{
case '+':
push(a + b);
break;
case '-':
push(a - b);
break;
case '*':
push(a * b);
break;
case '/':
push(a / b);
break;
}
}
}
printf("Result of expression %s is %d ",expr, pop());
return 0;
}

Program output

Enter postfix expression : 543*+2-

Result of expression 543*+2- is 15

Problems on Stack: String reversal using stack

/* C program to reverse a string using a stack */

#include <stdio.h>
char str[20], stack[20];
int i, top=-1;
void push( char ch )
{
stack[++top] = ch;
}
char pop()
{
if (top==-1)
return '\0';
else
return stack[top--];
}
int main()
{
char ch;
printf("Enter a string ");
scanf("%s",str);
for(i=0; str[i]!= '\0' ; i++)
{
push( str[i] );
}
i=0;
while ( (ch=pop()) != '\0')
{
str[i++]=ch;
}

printf("\nReversed string is %s\n",str);

return 0;
}

Program output

Enter a string hello

Reversed string is olleh
Problems on Stack: Balanced parenthesis
 To check if parenthesis in an expression are balanced, push all the opening
brackets in the stack.
 Whenever we come across a closing bracket, check if the top of the stack is
the opening bracket of the same type. If it is then pop the stack and continue
the iteration.
 In the end if the stack is empty, it means all brackets are balanced or well-
formed. Otherwise, they are not balanced.
#include <stdio.h>
#define SIZE 20 Program Output 1
char paren[SIZE];
char stack[SIZE];
int top=-1;
void push(char ch)
{
if (top==SIZE-1) Program Output 2
printf("\n\tStack is full\n");
else
stack[++top] = ch;
}
char pop()
{
if (top == -1)
return '\0';
else
return stack[top--];
}
int main()
{
int i, flag=0;
char x;
printf("\n\tEnter parenthesis expression ");
scanf("%s",paren);
for(i=0; paren[i] != '\0'; i++)
{
if (paren[i]=='(' || paren[i]=='[' || paren[i]=='{')
push( paren[i]);
else if (paren[i]==')' || paren[i]==']' || paren[i]=='}')
{
x = pop() ;
if (x)
{
if (paren[i]==')' && x=='(' || paren[i]==']' && x=='[' || paren[i]=='}' && x=='{' )
continue;
else
{
flag=1;
break;
}
}
}
}
x=pop();
if (x!='\0' || flag==1)
printf("\n\tParenthesis not balanced properly\n");
else
printf("\n\tParenthesis balanced properly\n");
return 0;
}
Overview of Queue data structure
 A Queue is a linear data structure in which operations are performed in First In First Out (FIFO)
order.
 Example

 An item which enters the queue first must leave the queue first.
 Queue data structure can be implemented using array or linked list.
 Adding an item to a queue is called enqueue operation and removing an item from queue is called dequeue
operation.
 Queues in which items are added at both ends and removed from both ends are known as Double Ended
queues.

Insert and delete operations on Queue using array.

 In the array implementation of queue, the array size is fixed before data is stored in the
queue.
 If all the elements in the array used queue is stored, the queue is full and no more
elements can be added to the queue.
 When removing an element from a queue, the elements from index 1 till rear are shifted
to the previous index. This requires extra time.

/* C program for array implementation of queue */

#include <stdio.h>
#define SIZE 5
int que[SIZE]={0};
int front =-1, rear= -1;
//function to add item to queue
void enqueue( int x )
{
if (front==-1) //QUEUE IS EMPTY
{
front++;
rear++;
que[rear]=x;
printf("\n\tItem was added to the queue\n");
}
else if (rear==SIZE-1)
printf("\n\tQueue is full...Cannot add new item\n");
else
{
que[++rear]=x;
printf("\n\tItem was added to the queue\n");
}
}
//function to display items from queue
void display()
{
if (rear==-1)
{
printf("\n\tQueue is Empty...\n");
return;
}
printf("\n\tDisplaying items in queue\n");
for(int i=front; i<=rear ; i++)
printf("\t%d\n",que[i]);
}
//function to delete item from queue
void dequeue()
{
int i;
if (rear==-1)
printf("\n\tCannot delete...Queue is empty...\n");
else
{
printf("\n\tDeleteing .... %d\n",que[front]);
//shifting elements from position front + 1 to previous position
for(i=0; i<=rear; i++)
que[i] = que[i+1];
rear--;
}
}
/* main() function */
int main()
{
int n, choice;
char ans='y';
while (ans=='y')
{
printf("\n\tChoose your queue operation \n");
printf("\n\t1.Enqueue\n\t2.Dequeue\n\t3.Display\n\tEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n\tEnter value to add to the queue ");
scanf("%d",&n);
enqueue( n );
break;
case 2:
dequeue();
break;
case 3:
display();
break;
default:
printf("\n\tInvalid choice...\n");
}
printf("\n\tContinue y / n ? ");
fflush(stdin);
scanf("%c",&ans);
}
return 0;
}
Insert and delete operations on Queue using linked list

/* C program to manage a queue using linked list */

#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
}*front, *rear, *ptr, *n;
//function to create a new node
void createnode()
{
//allocate memory for the new node
n = (struct node *) malloc( sizeof(struct node) );
//accept input for new node data
printf("\n\tEnter data for new node ");
scanf("%d",&n->data);
}
//function to add node to queue
void enqueue()
{
createnode(); //function call to create a node
if (front==NULL) //queue is empty
{
front = rear = n;
n->next = NULL;
}
else
{
rear->next = n;
rear = n;
n->next = NULL;
}
printf("\n\tNew node added to queue...\n");
}
//function to delete node from the queue
int dequeue()
{
int a;
if (front==NULL)
{
printf("\n\tQueue is Empty\n");
return -1;
}
ptr=front;
a = ptr->data;
front=front->next;
return a;
}

//function to display data in all the nodes

void display()
{
if (front==NULL)
{
printf("\n\tQueue is Empty\n");
return;
}
for(ptr=front; ptr!=NULL; ptr=ptr->next)
printf("\n\t%d",ptr->data);
}
/* main() function */
int main()
{
int choice, d;
front = rear = NULL;
do
{
printf("\n\tChoose your queue operation \n");
printf("\n\t1.Enqueue");
printf("\n\t2.Dequeue");
printf("\n\t3.Display");
printf("\n\t4.Exit \n");
printf("\n\tEnter your choice ");
scanf("%d",&choice);
switch( choice )
{
case 1:
enqueue();
break;
case 2:
d=dequeue();
if (d!=-1)
printf("\n\t%d Removed from queue \n",d);
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\n\tInvalid choice\n");
}

}while (choice!=4);
return 0;
}
UNIT III - SORTING AND SEARCHING

Bubble sort – selection sort – insertion sort – merge sort – quick sort – time complexity of the sorting
methods– linear search – binary search – Hashing techniques: liner probing and chaining method,
analysis of time complexity.

Bubble Sort

 This simple sorting algorithm starts at the beginning of the list of values stored in an array.
 It compares each pair of adjacent elements and swaps them if they are in the unsorted order.
 This comparison and passes to be continued until no swaps are needed, which indicates that the
list of values stored in an array is sorted.
 The algorithm is a comparison sort, is named for the way smaller elements "bubble" to the top of
the list.
 Although the algorithm is simple, it is too slow and less efficient when compared to insertion
sort and other sorting methods.

Pseudo code

1. Start with the first element i.e., index = 0, compare the current element with the next element of
the
array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next or right side of the element, move to the next element.
Go to
Step 1 and repeat until end of the index is reached.

Example

Let's consider an array with values {15, 11, 16, 12, 14, 13}
Below, we have a pictorial representation of how bubble sort will
sort the given array.

15 is greater than 11. So 15 and 11 are interchanged

15 is less than 16. So 15 and 16 are not interchanged.

16 is greater than 12. So 16 and 12 are interchanged.

16 is greater than 14. So 16 and 14 are interchanged.

16 is greater than 13. So 16 and 13 are interchanged.

The array values after end of first pass. Two more

passes are required to sort the array completely .

Selection sort

 This simple sorting algorithm improves on the performance of bubble sort by making only
one exchange for every pass through the list.
 This algorithm will first find the smallest elements in array and swap it with the element in
the first position of an array.
 It will then find the second smallest element and swap that element with the element in the
second position and continue until the entire array is sorted in respective order.
 This algorithm repeatedly selects the next-smallest element and swaps in into the right place
for every pass. Hence it is called selection sort.

Pseudo code

1. Start from the first element i.e., index-0, we search the smallest element in the array, and
replace it with the element in the first position.
2. Now we move on to the second element position, and look for smallest element present in
the sub- array, from starting index to till the last index of sub - array.
3. Now replace the second smallest identified in step-2 at the second position in the or original
array, or also called first position in the sub array.
4. This is repeated, until the array is completely sorted.

Example
Insertion Sort

 This simple sorting algorithm works by taking elements from the list one by one and
inserting then in their correct position into a new sorted list.
 This algorithm builds the final sorted array at the end.
 This algorithm uses n-1 number of passes to get the final sorted list.

Pseudo code

Step 1 − If it is the first element, it is already sorted.

Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be
Sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Example

At the end of the pass the insertion sort algorithm gives the sorted output in ascending order as
shown below:
Merge Sort

 This sorting technique uses the Divide and conquer algorithm.

 In Divide and Conquer algorithm, a problem is divided into multiple sub-problems. Each sub-
problem is solved individually. Finally, sub-problems are combined to form the final solution.
 The process of merge sort is to divide the array into two halves, sort each half, and then
merge the sorted halves back together. This process is repeated until the entire array is sorted.
 Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be
further divided i.e., the array has only one element left (an array with one element is always
sorted). Then the sorted subarrays are merged into one sorted array.

 Example 1

 Example 2
Illustration

Consider the array arr[] = {38, 27, 43, 10}

Pseudocode

Step 1: Declare the variable low and high to mark the start and end of the array.
Step 2: Low will equal 0, and high will equal array size -1.
Step 3: Calculate mid using low + high / 2.
Step 4: Call the mergeSort function on the part (low, mid) and (mid+1, high).
Step 5: This calling will continue till low<high is satisfied.
Step 6: Finally, call the merge function to merge these two halves.

Quick Sort

 This sorting algorithm is based on the Divide and Conquer algorithm that picks an element as
a pivot and partitions the given array around the picked pivot by placing the pivot in its
correct position in the sorted array.
 The key process in quickSort is a partition(). The target of partitions is to place the pivot
(any element can be chosen to be a pivot) at its correct position in the sorted array and put all
smaller elements to the left of the pivot, and all greater elements to the right of the pivot.
 Partition is done recursively on each side of the pivot after the pivot is placed in its correct
position and this finally sorts the array.
 Example – Considering the last element as Pivot element.

Time complexity of the sorting methods

 Time Complexity is defined as the number of times a particular instruction set is
executed rather than the total time taken because the total time took also depends on
some external factors like the compiler used, processor’s speed, etc.
 Space Complexity is the total memory space required by the program for its
execution.
 Both are calculated as the function of input size(n).
Types of Time Complexity:

 Best Time Complexity: Define the input for which algorithm takes less time or
minimum time. In the best case calculate the lower bound of an algorithm. Example: In
the linear search when search data is present at the first location of large data then the
best case occurs.
 Average Time Complexity: In the average case take all random inputs and calculate
the computation time for all inputs.
And then we divide it by the total number of inputs.
 Worst Time Complexity: Define the input for which algorithm takes a long time or
maximum time. In the worst calculate the upper bound of an algorithm. Example: In
the linear search when search data is present at the last location of large data then the
worst case occurs.

Algorithm Time Complexity

Best Average Worst

Selection Sort Ω(n2) θ(n2) O(n2)

Bubble Sort Ω(n) θ(n2) O(n2)

Insertion Sort Ω(n) θ(n2) O(n2)

Quick Sort Ω(n log(n)) θ(n log(n)) O(n2)

Merge Sort Ω(n log(n)) θ(n log(n)) O(n log(n))

Time Complexity Analysis of Bubble Sort:

 Best Case: The best case occurs when the array is already sorted. So the number of
comparisons required is N-1 and the number of swaps required = 0. Hence the best
case complexity is O(N).
 Worst Case: The worst-case condition for bubble sort occurs when elements of the
array are arranged in decreasing order.
In the worst case, the total number of iterations or passes required to sort a given array
is (N-1). where ‘N’ is the number of elements present in the array.
 At pass 1:
Number of comparisons = (N-1)
Number of swaps = (N-1)
 At pass 2:
Number of comparisons = (N-2)
Number of swaps = (N-2)
 At pass 3:
Number of comparisons = (N-3)
Number of swaps = (N-3)
 At pass N-1:
Number of comparisons = 1
Number of swaps = 1
 Now, calculating total number of comparison required to sort the array
= (N-1) + (N-2) + (N-3) + . . . 2 + 1
= (N-1)*(N-1+1)/2 { by using sum of N natural Number formula }
= (N * (N-1)) / 2
 In worst case, Total number of swaps = Total number of comparison
Total number of comparison (Worst case) = N(N-1)/2
Total number of swaps (Worst case) = N(N-1)/2
 So worst case time complexity is O(N2) as N2 is the highest order term.
 Average Case Time Complexity: The number of comparisons is constant in Bubble
Sort. So in average case, there are O(N 2) comparisons. This is because irrespective of
the arrangement of elements, the number of comparisons C(N) is same.
 For the number of swaps, consider the following points:
 If an element is in index I1 but it should be in index I2, then it will take a minimum of
(I2-I1) swaps to bring the element to the correct position.
 Consider an element E is at a distance of I3 from its position in sorted array. Then the
maximum value of I3 will be (N-1) for the edge elements and N/2 for the elements at
the middle.
 The sum of maximum difference in position across all elements will be:
 (N – 1) + (N – 3) + (N – 5) . . . + 0 + . . . + (N-3) + (N-1)
= N x (N – 2) x (1 + 3 + 5 + … + N/2)
= N2 – (2 x N2 / 4)
= N2 – N2 / 2
= N2 / 2
 Therefore, in average case the number of comparisons is O(N 2)

Linear Search

 Linear Search is the most basic method of searching an element from a list.
 It is also known as sequential search, as it sequentially checks each element of the list
until the key element is found or the entire list has been traversed.
 Example: Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30.
Step 1: Start from the first element (index 0) and compare key with each element
(arr[i]).
 Advantages of linear search
 Linear search can be used irrespective of whether the array is sorted or not. It can
be used on arrays of any data type.
 Does not require any additional memory.
 It is a well-suited algorithm for small datasets.

 Time Complexity:
 Best Case: In the best case, the key might be present at the first index. So the best
case complexity is O(1)
 Worst Case: In the worst case, the key might be present at the last index i.e.,
opposite to the end from which the search has started in the list. So the worst-case
complexity is O(N) where N is the size of the list.
 Average Case: O(N)
Binary Search

 Binary search also called half-interval search algorithm.

 It finds the position of a search element within a sorted array.
 The binary search algorithm can be done as divide-and-conquer search algorithm and
executes in logarithmic time.
 Binary search will complete the task in a logarithmic time.
 Binary search requires the elements in the array must be sorted.

Pseudo code for Binary search

1. Start with the middle element:

 If the search element is equal to the middle element of the array return the index of
the middle element.
If not, compare the middle element with the search value,
 If the search element is greater than the number in the middle index, then
select the elements to the right side of the middle index, and go to Step-1.
 If the search element is less than the number in the middle index, then select
the elements to the left side of the middle index, and start with Step-1.
2. When a match is found, display success message with the index of the element matched.
3. If no match is found for all comparisons, then display unsuccessful message.

Example

 Array elements:-

 Search element:- 60
 Calculate mid index as
mid = low + (high – low) / 2
low = 0, high = 9
mid = 0 +(9-0)/2 = 9/2 = 4
 Element at mid index 4 is 50
 Search value 60 > mid value 50. Select the elements to the right side of 50.
 low = mid + 1 = 4 + 1 = 5
 Calculate mid index
mid = 5 + ( 9 – 5 )/ 2 = 5 + 4/2 = 5 + 2 = 7
 Element at mid index 7 is 80
 Mid element 80 is > search value 60. Select the elements to the left of 80.
 high = mid – 1 = 7 – 1 = 6
 Calculate mid index
mid = 5 + (6 - 5) / 2 = 5
 Element at mid index 5 is 50.
 Mid element 50 = search value 50.
Display message ‘Element found at index 5’
Hashing Techniques: Linear probing and Chaining methods

 A group of values can be stored, accessed and processed efficiently using array data structure.
 Storing data in an array can be done quickly, but searching requires more time if dataset is
large.
 This inefficiency of array data structure is overcome by using hash data structure.
 Hash or Hash table is a data structure that maps keys (data) to values.
 It uses a hash function to calculate index for the data key and the data key is stored in the
index.
 Hashing is a technique or process of generating index for data keys using hash function and
storing them into a hash table.

Index

Data keys

 Storage and retrieval in hash data structure can be done in a constant time.

Hash function

The hash function creates a mapping between key and value, this is done through the use of
mathematical formulas known as hash functions. The result of the hash function is referred to
as a hash value or hash.

Division method

 Easiest method to create a hash function.

 h(k) = k mod n, where h(k) is the hash value obtained by dividing the key value k by size
of hash table n using the remainder. It is best that n is a prime number as that makes
sure the keys are distributed with more uniformity.
 Example
k=1276
n = 10
h(1276) = 1276 % 10 = 6.
The hash value obtained is 6.
 A disadvantage of the division method id that consecutive keys map to consecutive hash
values in the hash table. This leads to a poor performance.

Mid Square method

 Very good hash function

 It involves squaring the value of the key and then extracting the middle r digits as the
hash value.
 The value of r can be decided according to the size of the hash table.
 Example
If hash table has 100 memory locations, r=2 because 2 digits are required to map the key
to memory location.
k=20
k * k = 50 * 50 = 2500
h(50) = 50
The hash value obtained is 50.

Example for storing keys in a hash table using Division method

 Consider the following as keys to be stored in hash table.

35 50 11 76 79 58 92 53 64 17
 Hash function used is
h(k) = k mod n
 Index computed for the first data key 35 is 35 mod 10 i.e 5
Data key 35 is stored in index position 5 in the hash table

0
1
2
3
4
5 35
6
7
8
9

 Index computed for the second data key 50 is 50 mod 10 i.e o

Data key 50 is stored in index position 0 of hash table
0 50
1
2
3
4
5 35
6
7
8
9

 The third data key is 11 and its index computed is 11 % 10 i.e 1

Data key 11 is stored in index 1 of hash table.

0 50
1 11
2
3
4
5 35
6
7
8
9

 The fourth data key is 76 and its index computed is 76 % 10 = 6

Data key 76 is stored index 6 of hash table.

0 50
1 11
2
3
4
5 35
6 76
7
8
9

 The fifth data key is 79 and its index computed is 79 % 10 = 9

Data key 79 is stored index 9 of hash table.

0 50
1 11
2
3
4
5 35
6 76
7
8
9 79

 The sixth data key is 58 and its index computed is 58 % 10 = 8

Data key 58 is stored index 8 of hash table.

0 50
1 11
2
3
4
5 35
6 76
7
8 58
9 79

 The seventh data key is 92 and its index computed is 92 % 10 = 2

Data key 92 is stored index 2 of hash table.

0 50
1 11
2 92
3
4
5 35
6 76
7
8 58
9 79

 The eighth data key is 53 and its index computed is 53 % 10 = 3

Data key 53 is stored index 3 of hash table.

0 50
1 11
2 92
3 53
4
5 35
6 76
7
8 58
9 79

 The seventh data key is 64 and its index computed is 64 % 10 = 4

Data key 64 is stored index 4 of hash table.

0 50
1 11
2 92
3 53
4 64
5 35
6 76
7
8 58
9 79

 The seventh data key is 17 and its index computed is 17 % 10 = 7

Data key 17 is stored index 7 of hash table.

0 50
1 11
2 92
3 53
4 64
5 35
6 76
7 17
8 58
9 79

Collision

 The hashing process generates a small number for a big key, so there is a possibility that two
keys could produce the same value. The situation where the newly inserted key maps to an
already occupied, and it must be handled using some collision handling technology.

 A hash collision occurs when a hash algorithm produces the same hash value for two different
input values.

Linear probing

 The simplest approach to resolve a collision is linear probing.

 In this technique, if a value is already stored at a location generated by h(k), it means collision
occurred then we do a sequential search to find the empty location.
 This method will place the data key in the next available position. Because in this approach
searches are performed sequentially so it’s known as linear probing.
 If the location is empty then store value otherwise find the next location.
Following hash function is used to resolve the collision in:
h(k, i) = [h(k) + i] mod m
o m = size of the hash table,
h(k) = (k mod m),
i = the probe number that varies from 0 to m–1.
o Therefore, for a given key k, the first location is generated by [h(k) + 0] mod m, the
first time i=0.
o If the location is free, the value is stored at this location. If value
successfully stores then probe count is 1 means location is founded on the first go.
If location is not free then second probe generates the address of the location given
by [h(k) + 1]mod m.
Similarly, if the generated location is occupied, then subsequent probes generate the
address as [h(k) + 2]mod m, [h(k) + 3]mod m, [h(k) + 4]mod m, [h(k) + 5]mod m,
and so on, until a free location is found.

 Example:
 Consider the following sequence of keys {9, 7, 11, 13, 12, 8}
 Step 1: Empty hash table of size 10 with possible hash values 0 to 9
 Step 2:
First Key to be inserted in the hash table = 9.
h(k) = 2k + 5
h(9) = 2*9 + 5 = 23
h(k, i) = [h(k) + i] mod m
h(9, 0) = [23 + 0] mod 10 = 3
So, key 9 will be inserted at index 3 of the hash table.

 Step 3:
Next Key to be inserted in the hash table = 7.
h(k) = 2k + 5
h(7) = 2*7 + 5 = 19
h(k, i) = [h(k) + i] mod m
h(7, 0) = [19 + 0] mod 10 = 9
So, key 7 will be inserted at index 9 of the hash table

 Step 4:
Next Key to be inserted in the hash table = 11.
h(k) = 2k + 5
h(11) = 2*11 + 5 = 27
h(k, i) = [h(k) + i] mod m
h(11, 0) = [27 + 0] mod 10 = 7
So, key 11 will be inserted at index 7 of the hash table
 Step 5:
Next Key to be inserted in the hash table = 13.
h(k) = 2k + 5
h(13) = 2*13 + 5 = 31
h(k, i) = [h(k) + i] mod m
h(13, 0) = [31 + 0] mod 10 = 1
So, key 13 will be inserted at index 1 of the hash table

 Step 6:
Next key to be inserted in the hash table = 12.
h(k) = 2k + 5
h(12) = 2*12 + 5 = 27
h(k, i) = [h(k) + i] mod m
h(12, 0) = [27 + 0] mod 10 = 7
Here Collision has occurred because index 7 is already filled.
Now we will increase i by 1.
h(12, 1) = [27 + 1] mod 10 = 8
So, key 12 will be inserted at index 8 of the hash table.

 Step 7:
Next key to be inserted in the hash table = 8.
h(k) = 2k + 5
h(8) = 2*8 + 5 = 21
h(k, i) = [h(k) + i] mod m
h(8, 0) = [21 + 0] mod 10 = 1
Here Collision has occurred because index 1 is already filled.
Now we will increase i by 1 now i become 1.
h(k) = 2k + 5
h(8) = 2*8 + 5 = 21
h(k, i) = [h(k) + i] mod m
h(8, 0) = [21 + 1] mod 10 = 2
index 2 is vacant so 8 will be inserted at index 2.

Chaining

 Separate Chaining is the collision resolution technique that is implemented using

linked list.
 When two or more elements are hash to the same location, these elements are
represented into a singly-linked list like a chain.
 This method uses extra memory to resolve the collision, therefore, it is also known
as open hashing.
 In separate chaining, each slot of the hash table is a linked list. We will insert the
element into a specific linked list to store it in the hash table. If there is any collision
i.e. if more than one element after calculating the hashed value mapped to the same
key then we will store those elements in the same linked list.

 Example:
 Using hash function h(key) = key % table size
 Hash table size 7
 Data key 42  hash index is 42 % 7 = 0
 Data key 38  hash index is 38 % 7 = 3.
 Data key 52  hash index = 52 % 7 = 3 same as hash index for 38. Collision has
occurred. Data key 52 will also go into index 3 as given below.

Analysis of time complexity

Time Complexity is a concept in computer science that deals with the quantification of the
amount of time taken by a set of code or algorithm to process or run as a function of the amount
of input. In other words, the time complexity is how long a program takes to process a given
input. The efficiency of an algorithm depends on two parameters:
 Time Complexity
 Space Complexity
Time Complexity: It is defined as the number of times a particular instruction set is executed
rather than the total time taken. It is because the total time taken also depends on some external
factors like the compiler used, the processor’s speed, etc.
Space Complexity: It is the total memory space required by the program for its execution.

Asymptotic Notations in Complexity Analysis:

1. Big O Notation

Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it
gives the worst-case complexity of an algorithm. By using big O- notation, we can
asymptotically limit the expansion of a running time to a range of constant factors above and
below. It is a model for quantifying algorithm performance.
2. Omega Notation

Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best-case complexity of an algorithm.
The execution time serves as a lower bound on the algorithm’s time complexity. It is defined
as the condition that allows an algorithm to complete statement execution in the shortest
amount of time.

3. Theta Notation

Theta notation encloses the function from above and below. Since it represents the upper and
the lower bound of the running time of an algorithm, it is used for analyzing the average-
case complexity of an algorithm. The execution time serves as both a lower and upper bound
on the algorithm’s time complexity. It exists as both, the most, and least boundaries for a
given input value.

UNIT IV - TREE STRUCTURES

Tree ADT – Binary Tree ADT – tree traversals – LDR, DLR, RDL- binary search trees –
AVL trees – heaps – multi-way search trees.

Tree ADT

 A tree is a non-linear data structure which organizes nodes as a hierarchical

structure.
 Every individual element in a tree is called Node.
 It consists of a root node and many levels of additional nodes that form a hierarchy.
 A tree with no nodes is called the null or empty tree

Example

Edge

 The top most node or very first node in a tree is called Root node. Every tree must
have a root node. Root node is the origin of Tree data structure. In the above tree

structure, is the root node. There must be only one Root node in a tree.
 The connecting link between any 2 nodes is called Edge. If there are n nodes in a tree,
there will be n-1 edges. In the above tree there is an edge between nodes A and B, A
and C, and D, B and E etc. There are 11 nodes in the above tree and 10 edges.
 The node which is predecessor of any node or a node which has child / children is
called Parent node. In the above tree, A, B, C, E and G are the parent nodes.
 The node which is descendent of any node is called Child node. In
 A node that does not have any child or a node with degree 0 is called Leaf node.
 Degree of any node is the total number of children the node has. In the above tree,
degree of A is 2, degree of B is 3, degree of node K is zero.
 Height of a tree is the total number of edges from Leaf node to a particular node in
the longest in the longest path. Height of the above tree is 3. In the above tree, the
longest path are A  B  E I, A  B  E J, A  C  G K and hence
height is 3. The height of leaf node is 0.
 Depth of a node is the total number of edges from Root node to that particular node.
 Path between 2 nodes is the sequence of nodes and edges from one node to another
node. The path between nodes A and J is A – B – E – J.
Binary Tree ADT

 A tree in which each node can have a maximum of 2 children.

 A general tree does not have limitation on number of child nodes.
 Degree of a binary tree may be two, one or zero.
 A binary tree consists of a Root node and 2 sub trees, Left subtree and Right subtree.
 Types of binary tree
 Strictly binary tree – All nodes will have zero or two children.
 Skew tree – All nodes except leaf node will have only one child node.
-- Two types: Left skewed tree, Right skewed tree
-- Left skewed tree – Nodes have only left child i.e tree has only left
subtree.
-- Right skewed tree - Nodes have only right child i.e tree has only
Right subtree.

 Full binary tree - A binary tree is a full binary tree if all leaves are at the
same level and every non leaf node has exactly two children.

 Complete binary tree - Every non leaf node has exactly two children but all
leaves are not necessary at the same level.

 Applications of binary tree

 Store hierarchical structure like Folder data.

 Implement indexing in databases.
 Evaluation of Arithmetic expression in compiler design.
 Shortest Path Trees are used in Routers, Bridges in computer networks.
 Machine learning algorithm.
 Implement searching and sorting algorithms.
 Decision making algorithms in Artificial Intelligence.

Tree traversal

A tree traversal can be defined as the process of visiting each node exactly once in
some order. There are 3 different traversal methods
1. Pre Order Traversal: DLR: Visit the root node first, then visit left node,
then right node.
2. In Order Traversal: LDR: Visit left sub tree, then root then right sub
tree.
3. Post Order Traversal: LRD: visit the left sub tree first, then right sub
tree, then the root node

Pre Order Traversal (DLR) example

 In pre-order traversal, each node is processed before (pre) either of its sub-
trees.
 This is the simplest traversal.

1
 In the tree given above, node 1 is visited first.

1, 2

 Pre-order of left subtree.

 Apply the rule: root  left right

1, 2, 4, 5

 Move to right subtree.

1, 2, 4, 5, 3

 Apply the rule: Root  Left  Right

1, 2, 4, 5, 3, 6, 7


 Final Pre-order traversal is 1, 2, 4, 5, 3, 6, 7

In Order Traversal (LDR) example

 From the root keep going to the left subtree.

4

 Visit the root.

4, 2

 Visit the right subtree.


 Apply rule to the root: Visit the root.

4, 2, 5, 1

 Traverse the right subtree.

4, 2, 5, 1, 6, 3, 7

 Final in-order traversal is: 4, 2, 5, 1, 6, 3, 7

Binary Search Tree

Binary Search Tree is a node-based binary tree data structure which has
the following properties:
 The left subtree of a node contains only nodes with keys lesser than
the node’s key.
 The right subtree of a node contains only nodes with keys greater
than the node’s key.
 The left and right subtree each must also be a binary search tree.
 Example

 Searching for a node in a Binary Search Tree is easier and insertion

and deletion of node is faster.

Creating a Binary Search Tree

 Consider data elements - 45, 15, 79, 90, 10, 55, 12, 20, 50
 The first data 45 is inserted as Root node of the tree.
Creation of Binary Search Tree is completed.
Searching in a binary search tree

Searching a binary search tree is finding a specific data in the tree. It is easy to search for a
node in binary search tree because the nodes are arranged in a specific order.
Steps to search for a node in a binary search tree:
1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root element, if it is
smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.

Example: Consider the following binary search tree. The node to be searched is 20.

Step 1: Compare Root node data 45 and Search node data 20. Search node data 20 < Root node
data 45. So move to left i.e Root = RootLeft.

Step 2: The current node data is 15. Search node data 20 > Current root node data 15. Hence move
to right i.e Root = RootRight.

Step 3: New Root node data is 20 which is the Search node data. Hence search node located.

Deleting a node in Binary Search Tree

The possible situations when a node is deleted from a binary search tree are:

1. The node to be deleted is the leaf node.

 Replace leaf node as NULL

 Free memory space of the deleted node.

2. The node to be deleted has only one child.

 Replace the target node to be deleted with its child node.

 Free the memory space of the target node.

3. The node to be deleted has two children.

 Find the inorder successor of the node to be deleted i.e find the minimum element in
the right child of the node.
 After that, replace that node with the inorder successor until the target node is
placed at the leaf of tree.
 And at last, replace the node with NULL and free up the allocated space.

Implementation of Binary Search Tree

AVL Trees
AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is
named AVL in honour of its inventors.
AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its right sub-
tree from that of its left sub-tree.
Tree is said to be balanced if balance factor of each node is in between -1 to 1,
otherwise, the tree will be unbalanced and need to be balanced.
Due to the fact that, AVL tree is also a binary search tree therefore, all the
operations are performed in the same way as they are performed in a binary search tree.
Searching and traversing do not lead to the violation in property of AVL tree.
Insertion and deletion operations in Binary Search Tree are performed the same way
as in Binary Search Tree but the balance factor may be changed and by performing rotations
the balance factor can be retained.

 If balance factor of any node is 1, it means that the left sub-tree is one level higher
than the right sub-tree.
 If balance factor of any node is 0, it means that the left sub-tree and right sub-tree
contain equal height.
 If balance factor of any node is -1, it means that the left sub-tree is one level lower
than the right sub-tree.
 An AVL tree is given in the following figure. We can see that, balance factor
associated with each node is in between -1 and +1. therefore, it is an example of AVL
tree.

Example
Heaps

Heap is a complete binary tree. A complete binary tree is a binary tree in which all
nodes except leaf node have two children.

Example: Complete binary tree Example: Not a complete binary tree

 The heap tree is a special balanced binary tree data structure where the root node is
compared with its children and arranged accordingly.
 There are 2 types of heaps – Min heap, Max heap.
 In Min heap the value of parent node must be less than or equal to either of its
children i.e for every node, the node value is greater than or equal to its parent
value.
 Example:
 In Max heap tree, the value of Parent node is greater than or equal to its children.
Example

Multi-way search trees

 A multiway tree is defined as a tree that can have more than two children. If a
multiway tree can have maximum m children, then this tree is called as multiway
tree of order m (or an m-way tree).
 As with the other trees that have been studied, the nodes in an m-way tree will be
made up of m-1 key fields and pointers to children.

Multiway tree of order 5

 A multiway tree is defined as a tree that can have more than two children. If a
multiway tree can have maximum m children, then this tree is called as multiway
tree of order m (or an m-way tree).
 As with the other trees that have been studied, the nodes in an m-way tree will be
made up of m-1 key fields and pointers to children.

Multiway tree of order 5

To make the processing of m-way trees easier some type of constraint or order will
be imposed on the keys within each node, resulting in a multiway search tree of
order m (or an m-way search tree). By definition an m-way search tree is a m-way
tree in which following condition should be satisfied −

 Each node is associated with m children and m-1 key fields

 The keys in each node are arranged in ascending order.
 The keys in the first j children are less than the j-th key.
 The keys in the last m-j children are higher than the j-th key.

UNIT V – GRAPH STRUCTURES

Graph ADT – representations of graph – graph traversals – Search methods : BFS, DFS -
DAG – topological ordering – greedy algorithms – dynamic programming – shortest paths –
minimum spanning trees – introduction to complexity classes and intractability.

Graph ADT
 Non-linear data structure.
 Collection of nodes that have data and are connected to other nodes.
 Graph is composed of a set of vertices (V) and a set of edges ( E ).
 The graph is denoted by G(E, V).
 Vertices:
 Fundamental units of the graph.
 Also known as nodes.
 Can be labeled or unlabelled.
 Edges:
 Edges are lines that connect any two nodes in the graph.
 Can connect any two nodes in any possible way. There are no rules.
 Also known as arcs.
 Every edge can be labeled / unlabelled.
 Graph example
 The Facebook uses graph data structure to store data.
 Every thing posted on Facebook like user, photo, group, album, comment, story,
video, link etc are considered as nodes in a graph.
 When a photo is posted on Facebook by a user, an edge is drawn between user
node and the photo node.
 Facebook is a collection of nodes and edges.

Application of graphs

 Graphs are used to solve many real-life problems.

 Graphs are used to represent networks. The networks may include paths in a city or
telephone network or circuit network.
 Graphs are also used in social networks like linkedIn, Facebook. For example, in
Facebook, each person is represented with a vertex(or node). Each node is a structure
and contains information like person id, name, gender, locale etc.
 Google maps uses graphs for building transportation systems, where intersection of
two(or more) roads are considered to be a vertex and the road connecting two vertices
is considered to be an edge, thus their navigation system is based on the algorithm to
calculate the shortest path between two vertices.
 In World Wide Web, web pages are considered to be the vertices. There is an edge
from a page u to other page v if there is a link of page v on page u. This is an example
of Directed graph.
 In Operating System, we come across the Resource Allocation Graph where each
process and resources are considered to be vertices. Edges are drawn from
resources to the allocated process, or from requesting process to the requested
resource. If this leads to any formation of a cycle then a deadlock will occur.
 In mapping system we use graph. It is useful to find out which is an excellent place
from the location as well as your nearby location. In GPS we also use graphs.
 Microsoft Excel uses DAG means Directed Acyclic Graphs.
 Graphs are used in biochemical applications such as structuring of protein, DNA etc.

Graph connecting capitals of countries

Telephone circuit graph

Circuit Network Graph

Facebook Graph

 Directed graph / digraph

 This type of graph is indicated with an arrow on the edge.
 Example
 Each vertex in a directed graph has two different degree measures: indegree
and outdegree.
 Indegree is the number of incoming edges to a vertex
 Outdegree is the number of outgoing edges from a vertex.
 A directed graph can contain cycles, which are paths that start and end at the
same vertex and contain at least one edge.
 Social networks, transportation networks, computer networks use directed
graphs.
 A null graph has no edges. It has only isolated nodes.

 Trivial graph

A graph is called a trivial graph if it has only one vertex present in it. The trivial
graph is the smallest possible graph that can be created with the least number of
vertices that is one vertex only.

 Undirected / Non directed graph

1 2
5

 Edges have no specified direction assigned to them.

 Edges connecting vertices in this graph are bidirectional.
 An undirected graph may contain loops, which are edges that connect a vertex to
itself.
 Degree of each vertex is the same as the total no of edges connected to it.
 Social Networks: Undirected graphs are used to model social networks where
people are represented by nodes and the connections between them are
represented by edges.
 Traffic flow optimization: Undirected graphs are used in traffic flow optimization
to model the flow of vehicles on road networks. The vertices of the graph
represent intersections or road segments, and the edges represent the connections
between them. The graph can be used to optimize traffic flow and plan
transportation infrastructure.
 Website analysis: Undirected graphs can be used to analyze the links between web
pages on the internet. Each web page is represented by a vertex, and each link
between web pages is represented by an edge.

 Directed graph / digraph

 A graph is called a directed graph or digraph if all the edges present between any
vertices or nodes of the graph are directed or have a defined direction.
 The edges of this graph that have a direction to determine starting node and
ending node.

 Connected / Complete graph

 In this type of graph there must be at least a single path between every pair of the
graph's vertices.

 Disconnected graph
 A graph is said to be a disconnected graph where there does not exist any path
between at least one pair of vertices.

 Cyclic graph
 If a graph has a minimum of one cycle present, it is called a cyclic graph.
 There are 2 cycles in the graph given below.
 Acyclic graph

Representations of Graph

 The two most commonly used representations of graphs are

 Adjacency matrix
 Adjacency list
Adjacency matrix representation of graphs.

 An adjacency matrix is a two-dimensional array (2D array) of size V X V,

where V is the number of vertices in the graph.
 Storing a 1 at position i, j indicates there is an edge from vertex i to vertex j, and
0 otherwise.
 Instead of a 1 or 0, weightage of the edge can also be stored.
 Example 1: Adjacency matrix representation of an undirected graph.

1 2

3 4

0 1 2 3 4
0
1 0 1 1 0
2 1 0 0 0
3 1 0 0 1
4 0 0 1 0

 Example 2: Adjacency matrix representation of a directed graph.

1 2

3 4

0 1 2 3 4
0
0 1 1 0
0 0 0 0
0 0 0 1
0 0 0 0
1
2
3
4

Graph Traversal algorithms

 Traversal means visiting all the nodes of a graph.

 These algorithms specify an order to search through the nodes of a graph.
 We start at the source node and keep searching until we find the target node.
 There are two algorithms available for Graph Traversal.
1) Breadth First Search (BFS)
2) Depth First Search (DFS)

Breadth First Search (BFS) method

 Starting from the root, all the nodes at a particular level are visited first and then the
nodes of the next level are traversed till all the nodes are visited.
 BFS uses a queue for traversal. All the adjacent unvisited nodes of the current level
are pushed into the queue and the nodes of the current level are marked visited and
removed from the queue.
 To avoid visiting the same node again and again, the vertices are divided into 2
categories – visited nodes, not visited nodes.
 An array is used to mark the visited nodes, the values stored in this array is 1 or 0.

Example:
 Consider undirected graph given below:

 Step 1:
Initially Queue and Visited array is empty.
 Step 2:

Push Node 0 into Queue and mark it Visited.

 Step 3:

Remove Node 0 from front of Queue and visit the unvisited neighbours and push
them into the Queue.

 Step 4:

Remove Node 1 from front of Queue and visit the unvisited neighbours and push
them into the Queue.

1 3

 Step 5
Remove node 2 from front of queue and visit the unvisited neighbours and add
them to the Queue.

1 3

2 4

 Step 6
 Remove node 3 from front of queue and visit the unvisited neighbours
and add them to the Queue.
 Every neighbor of node 3 is visited.
 Move to next node in front of Queue

1 3

2 4

 Step 7
 Remove node 4 from front of queue and visit the unvisited neighbours
and add them to the Queue.
 Every neighbor of node 3 is visited.
 Move to next node in front of Queue.
 Queue is empty, process is terminated.
C program to implement BFS graph traversal method for the graph
given below

Adjacency matrix for the above graph

0 1 2 3 4

0 0 1 1 0 0 0
1 1 0 1 1 0
2 1 1 0 0 1
3 0 1 0 0 1
4 0 0 1 1 0

#include <stdio.h>

int n, i, j, visited[10], queue[10], front = -1, rear = -1;

int adj[10][10];

void bfs(int v) //user-defined function to visit all nodes from node v

{
for (i = 1; i <= n; i++)
if (adj[v][i] && !visited[i])
queue[++rear] = i;
if (front <= rear)
{
visited[queue[front]] = 1;
bfs(queue[front++]);
}
}

int main()
{
int v;
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter graph data in matrix form: \n");
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
printf("Enter 1 if there is an edge between nodes %d and %d, otherwise 0 : ",i,j);
scanf("%d", &adj[i][j]);
}
printf("Enter the starting vertex: ");
scanf("%d", &v);
bfs(v);
printf("The nodes that cab be visited from %d are: \n",v);
for (i = 1; i < n; i++)
if (visited[i])
printf("%d\t", i);
return 0;
}

Depth First Search (DFS) method

Depth-first search is an algorithm for traversing graph data structure. The algorithm
starts at the root node (any node in the graph can be selected as root node) and explores as
far as possible along each path
DFS can be used to detect cycles in a graph. It can also be used to find the path
between two nodes.

Pseudo code

Step 1: Accept input for Adjacency matrix of the graph.

Step 2: Push start vertex to graph.

Step 3: If stack is not empty, pop a node from top of stack, otherwise go to Step 6

Step 4: If popped node is not visited, mark it as visited.

Step 5: Push all nodes that can be visited from current node into stack if it not already

visited. Go to Step 3.

.Step 6: Process stops as all nodes are visited.

Depth First Search Example

Sample graph (undirected), empty Visited array and empty stack are given below:

Empty Visited array

Empty Stack

Step 1: Push the start vertex to the stack.

Stack
0
0 1 2 3 4
top

Visited array
0 0 0 0 0
0 1 2 3 4

Step 2: Pop value 0 from the top of stack.

Step 3: Popped value is not already already visited. Update Visited[0] to 1.

Visited array
1 0 0 0 0
0 1 2 3 4

Step 5: Push the adjacent nodes 1, 2 and 3 to the Stack.

Stack
1 2 3
0 1 2 3 4
top

Step 6: Pop node 1 from Stack. It is not already visited. Update Visited [1] to 1.
Stack
2 3

Visited
1 1 0 0 0
0 1 2 3 4
Step 7: Push the nodes that can be visited from node 1 to stack if they are not already
visited. But nodes 0 and 1 are already visited and they are not pushed to stack.

Step 8: Pop node 2 from top of stack. It is not already visited. Update Visited [2] to 1.

Stack
3
top
Visited
1 1 1 0 0
0 1 2 3 4
Step 9: Push the nodes that can be visited from node 2 to stack if they are not already
visited. Node 4 is not already visited and 4 is pushed to stack.

Stack
3 4
top
Step 10: Pop node 3 from top of stack. It is not already visited. Update Visited [3] to 1. The
node that can be visited from 3 is 0. It is already visited and not pushed to stack.

Visited
1 1 1 1 0
0 1 2 3 4
Stack
4
top
Step 11: Pop node 4 from Stack and update Visited [4] to 1.

Visited
1 1 1 1 1
0 1 2 3 4
Empty Stack (top is -1)

/* C Program to implement DFS Algorithm for the Graph */

#include<stdio.h>

int n;
int adj[10][10];
int visited[10];
int stack[10];
int top = -1;

void create_graph()
{
int i,max_edges,origin,destin;
printf("\n\tEnter number of nodes : ");
scanf("%d",&n);
max_edges=n*(n-1);
for(i=1;i<=max_edges;i++)
{
printf("\n\tEnter edge %d( -1 -1 to quit ) : ",i);
scanf("%d %d",&origin,&destin);

if( (origin == -1) && (destin == -1) )

break;

if( origin >= n || destin >= n || origin<0 || destin<0)

{
printf("\n\tInvalid edge!\n");
i--;
}
else
{
adj[origin][destin] = 1;
}
}
}
void display()
{
int i,j;
printf("\n\tAdjacency matrix \n");
for(i=0 ; i<n ; i++)
{
for(j=0; j<n ; j++)
printf("\t%d",adj[i][j]);
printf("\n");
}
}

void push(int v)
{
if(top == 9)
{
printf("\nStack Overflow\n");
return;
}
top=top+1;
stack[top] = v;
}
int pop()
{
int v;
if(top == -1)
{
printf("\nStack Underflow\n");
exit(1);
}
else
{
v = stack[top];
top=top-1;
return v;
}
}

int isEmpty_stack( )
{
if(top == -1)
return 1;
else
return 0;
}

void DFS(int v)
{
int i;
push(v);
while(!isEmpty_stack())
{
v = pop();
if(visited[v]==0)
{
printf("%d ",v);
visited[v]=1;
}
for(i=n-1; i>=0; i--)
{
if(adj[v][i]==1 && visited[i]==0)
push(i);
}
}
}
void DF_Traversal()
{
int v;

printf("\n]\tEnter starting node for Depth First Search : ");

scanf("%d",&v);
DFS(v);
printf("\n");
}

int main()
{
create_graph();
display();
DF_Traversal();
return 0;
}

Program execution output:

DAG (Directed Acyclic Graph)

 Basic Block is a set of statements that always executes one after other, in a sequence. The
flow of control enters at the beginning of the statement and leave at the end without any
halt. Basic blocks are used in compiler design.
 The Directed Acyclic Graph (DAG) is used to represent the structure of basic blocks, to
visualize the flow of values between basic blocks, and to provide optimization techniques in
the basic block.
 DAG does not contain any cycles.
 A DAG is usually constructed using Three Address Code.
 The rule of DAG is, interior nodes represent operators and exterior nodes (lea nodes)
represent identifiers or constants.

While constructing a DAG,

 A check is made to find if there exists any node with the same value.
 A new node is created only when there does not exist any node with the same value.
 This action helps in detecting the common sub-expressions and avoiding the re-computation
of the same.

Example 1: Create a DAG for the expression (a + b) * (a + b +c)

Three Address Code for the above expression

T1 = a + b
T2 = T1 + c
T3 = T1 x T2

The Directed Acyclic Graph for the above expression is

Shortest Paths

 The shortest path problem involves finding the shortest path between two vertices
(or nodes) in a graph.
 Algorithms such as the Floyd-Warshall algorithm and different variations of
Dijkstra's algorithm are used to find solutions to the shortest path problem.
 Dijkstra's Algorithm was designed and published by Dr. Edsger W. Dijkstra, a
Dutch Computer Scientist, Software Engineer, Programmer, Science Essayist, and
Systems Scientist.
 Dijkstra's algorithm is a simple modification to breadth first search. It is used to
find the shortest path from a given node to all other nodes, where edges may have
non-negative lengths.

Steps to implement Dijkstra's Algorithm:

 Step 1: First, we will mark the source node with a current distance of 0 and set the
rest of the nodes to INFINITY.
 Step 2: We will then set the unvisited node with the smallest current distance as the
current node, suppose X.
 Step 3: For each neighbor N of the current node X: We will then add the current
distance of X with the weight of the edge joining X-N. If it is smaller than the
current distance of N, set it as the new current distance of N.
 Step 4: We will then mark the current node X as visited.
 Step 5: We will repeat the process from 'Step 2' if there is any node unvisited left in
the graph.

Example: Consider the input graph given below with start node as A.

1. With the above graph as the input, let node A be the source.
2. Mark all the nodes as unvisited.
3. Set the path to 0 at node A and INFINITY for all the other nodes.
4. Mark source node A as visited and access its neighboring nodes.
Note: Neighboring nodes are only accessed and not visited.
5. Update the path to node B by 4 with the help of relaxation because the path to node A is 0 and
the path from node A to B is 4, and the minimum((0 + 4), INFINITY) is 4.
6. We will also update the path to node C by 5 with the help of relaxation because the path to
node A is 0 and the path from node A to C is 5, and the minimum((0 + 5), INFINITY) is 5.
Both the neighbors of node A are now relaxed; therefore, we can move ahead.
7. Select the next unvisited node with the least path and visit it. Visit node B and perform
relaxation on its unvisited neighbors. After performing relaxation, the path to node C will
remain 5, whereas the path to node E will become 11, and the path to node D will become 13.
8. We will now visit node E and perform relaxation on its neighboring nodes B, D, and F. Since
only node F is unvisited, it will be relaxed. Thus, the path to node B will remain as it is,
i.e., 4, the path to node D will also remain 13, and the path to node F will become 14 (8 + 6).
9. Now we will visit node D, and only node F will be relaxed. However, the path to node F will
remain unchanged, i.e., 14.
10. Since only node F is remaining, we will visit it but not perform any relaxation as all its
neighboring nodes are already visited.
11. Once all the nodes of the graphs are visited, the program will end.

Minimum Spanning Trees

 A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that
includes all the vertices of the graph. it is a subset of the edges of the graph that forms a tree
(acyclic) where every node of the graph is a part of the tree.
 A minimum spanning tree (MST) or minimum weight spanning tree for a weighted,
connected, undirected graph is a spanning tree with a weight less than or equal to the weight
of every other spanning tree.
 The minimum spanning tree has all the properties of a spanning tree with an added
constraint of having the minimum possible weights among all possible spanning trees.
 There are several algorithms to find the Minimum Spanning Tree – Kruskal’s minimum
spanning tree algorithm, Prim’s minimum spanning tree algorithm, Boruvka’s minimum
spanning tree algorithm.
 Kruskal’s minimum spanning tree algorithm:

This is one of the popular algorithms for finding the minimum spanning tree from a
connected, undirected graph. This is a greedy algorithm. The algorithm workflow is
as below:
 First, it sorts all the edges of the graph by their weights,
 Then starts the iterations of finding the spanning tree.
 At each iteration, the algorithm adds the next lowest-weight edge one by one,
such that the edges picked until now does not form a cycle.
This algorithm can be implemented efficiently using a DSU ( Disjoint-Set ) data
structure to keep track of the connected components of the graph. This is used in a
variety of practical applications such as network design, clustering, and data
analysis.
A data structure that stores non overlapping or disjoint subset of elements is called
disjoint set data structure. The disjoint set data structure supports following
operations:
 Adding new sets to the disjoint set.
 Merging disjoint sets to a single disjoint set using Union operation.
 Finding representative of a disjoint set using Find operation.
 Check if two sets are disjoint or not.

 Prim’s minimum spanning tree algorithm

This is also a greedy algorithm. This algorithm has the following workflow:
 It starts by selecting an arbitrary vertex and then adding it to the MST.
 Then, it repeatedly checks for the minimum edge weight that connects one
vertex of MST to another vertex that is not yet in the MST.
 This process is continued until all the vertices are included in the MST.
To efficiently select the minimum weight edge for each iteration, this algorithm uses
priority_queue to store the vertices sorted by their minimum edge weight currently.
It also simultaneously keeps track of the MST using an array or other data structure
suitable considering the data type it is storing.
This algorithm can be used in various scenarios such as image segmentation based
on color, texture, or other features. For Routing, as in finding the shortest path
between two points for a delivery truck to follow.

Introduction to complexity classes and intractability

 In computer science, there exist some problems whose solutions are not yet found,
the problems are divided into classes known as Complexity Classes.
 In complexity theory, a Complexity Class is a set of problems with related
complexity.
 These classes help scientists to group problems based on how much time and space
they require to solve problems and verify the solutions.
 It is the branch of the theory of computation that deals with the resources required to
solve a problem.
 The common resources are time and space, meaning how much time the algorithm
takes to solve a problem and the corresponding memory usage.
 The time complexity of an algorithm is used to describe the number of steps
required to solve a problem, but it can also be used to describe how long it takes to
verify the answer.
 The space complexity of an algorithm describes how much memory is required for
the algorithm to operate.
 Complexity classes are useful in organizing similar types of problems.
 The following complexity classes are available
 P Class
 NP Class
 CoNP Class
 NP-hard
 NP-complete

The P Class

The P in the P class stands for Polynomial Time. It is the collection of decision
problems(problems with a “yes” or “no” answer) that can be solved by a
deterministic machine in polynomial time.
Features:
1. The solution to P problems is easy to find.
2. P is often a class of computational problems that are solvable and tractable.
Tractable means that the problems can be solved in theory as well as in
practice. But the problems that can be solved in theory but not in practice are
known as intractable.
This class contains many natural problems:
1. Calculating the greatest common divisor.
2. Finding a maximum matching.
3. Decision versions of linear programming.