MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS)

VANIYAMBADI
PG and Department of Computer Applications
st
1 B.C.A – Semester - II

E-Notes (Study Material)

Core Course -1: Data Structure Code:24UCDS21

Unit: 1 - Abstract Data Types (ADTs)- List ADT-array-based implementation-linked

list implementation singly linked lists-circular linked lists-doubly-linked lists-
applications of lists- All operations-Insertion-Deletion-Merge - Polynomial
Manipulation.
Learning Objectives: To provide the knowledge of basic data structures and their
implementations. To understand the concepts of ADTs.
Course Outcomes: Learn the basic types for data structure, implementation and
application. Know the strength and weakness of different data structures.

Overview
- Abstract Data Types (ADTs)
- List ADT
- Array-based implementation-
- Linked list implementation
- Singly linked lists
- Circular linked lists
- Doubly-linked lists
- Applications of lists
- All operations -Insertion-Deletion-Merge
- Polynomial Manipulation
Data:
A collection of raw facts, concepts, figures, observations, occurrences or
instructions in a formalized manner.
Information:
The meaning that is currently assigned to data by means of the conventions
applied to those data (i.e. processed data)
Record:
Collection of related fields.
Data type:
A data type is the characteristic of a variable that determines what kind of data it
can hold.
Data Structures:
Data Structure is the way of organizing, storing, and retrieving data and their
relationship with each other.
Characteristics of data structures:
• It depicts the logical representation of data in computer memory.
• It represents the logical relationship between the various data elements.
• It helps in efficient manipulation of stored data elements.
• It allows the programs to process the data in an efficient manner
Operations on Data Structures: [Link] [Link] [Link] [Link]
What is Data Structure?
A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently.
A data structure is not only used for organizing the data. It is also used for
processing, retrieving, and storing data. There are different basic and advanced
types of data structures that are used in almost every program or software system
that has been developed. So we must have good knowledge about data structures.
Why should we learn Data Structures?
● Data Structures and Algorithms are two of the key aspects of Computer
Science.
● Data Structures allow us to organize and store data, whereas Algorithms
allow us to process that data meaningfully.
● Learning Data Structures and Algorithms will help us become better
Programmers.
● We will be able to write code that is more effective and reliable.
 ● We will also be able to solve problems more quickly and efficiently.

Classification of Data Structure

Primary Data Strucutres/Primitive Data Structures:

Primitive data structures include all the fundamental data structures that can
be directly manipulated by machine-level instructions. Some of the common
primitive data structures include integer, character, real, boolean etc
Secondary Data Structures/Non Primitive Data Structures:
Non primitive data structures, refer to all those data structures that are
derived from one or more primitive data structures. The objective of creating
non-primitive data structures is to form sets of homogeneous or
heterogeneous data elements.
A. Linear Data Structure: Data structure in which data elements are arranged
sequentially or linearly, where each element is attached to its previous and next
adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.
1. Static Data Structure: Static data structure has a fixed memory size. It is easier
to access the elements in a static data structure.
Example: array.
Array: Array is a linear data structure that stores a collection of elements of the
same data type. Elements are allocated contiguous memory, allowing for constant-
time access. Each element has a unique index number.
2. Dynamic Data Structure: In dynamic data structure, the size is not fixed. It can
be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.
Stack:Stack is a linear data structure that follows the Last In, First Out (LIFO)
principle. Stacks play an important role in managing function calls, memory,
and are widely used in algorithms, web development, and systems like
compilers and browsers.
Queue: Queue is a linear data structure that follows the First In, First Out
(FIFO) principle. Queues play an important role in managing tasks or data in
order, scheduling and message handling systems.
Linked List : Linked list is a linear data structure that stores data in nodes,
which are connected by pointers. Unlike arrays, nodes of linked lists are not
stored in contiguous memory locations and can only be accessed
sequentially, starting from the head of list.
B. Non-Linear Data Structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data
structure, we can’t traverse all the elements in a single run only.
Examples: Trees and Graphs.
Tree: Tree is a non-linear, hierarchical data structure consisting of nodes
connected by edges, with a top node called the root and nodes having child
nodes. It is widely used in file systems, databases, decision-making
algorithms, etc.
Graph: Graph is a non-linear data structure consisting of a finite set of
vertices(or nodes) and a set of edges(or links)that connect a pair of nodes.
Graphs are widely used to represent relationships between entities.
Abstract Data type (ADT)
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined
by a set of values and a set of operations. The definition of ADT only mentions
what operations are to be performed but not how these operations will be
implemented. It does not specify how data will be organized in memory and what
algorithms will be used for implementing the operations. It is called “abstract”
because it gives an implementation-independent view.
The process of providing only the essentials and hiding the details is known as
abstraction.
The user of data type does not need to know how that data type is implemented,
for example, we have been using Primitive values like int, float, char data types
only with the knowledge that these data type can operate and be performed on
without any idea of how they are implemented.
So a user only needs to know what a data type can do, but not how it will be
implemented. Think of ADT as a black box which hides the inner structure and
design of the data type. Now we’ll define three ADTs namely List ADT, Stack ADT,
Queue ADT.
1. List ADT
The data is generally stored in key sequence in a list which has a head structure
consisting of count, pointers and address of compare function needed to compare
the data in the list.
The data node contains the pointer to a data structure and a self-referential pointer
which points to the next node in the list.
2. Stack ADT
In Stack ADT Implementation instead of data being stored in each node, the
pointer to data is stored.
The program allocates memory for the data and address is passed to the stack
ADT.
The head node and the data nodes are encapsulated in the ADT. The calling
function can only see the pointer to the stack.
3. Queue ADT
The queue abstract data type (ADT) follows the basic design of the stack abstract
data type.
Each node contains a void pointer to the data and the link pointer to the next
element in the queue. The program’s responsibility is to allocate memory for
storing the data.
Features of ADT:
Abstract data types (ADTs) are a way of encapsulating data and operations on that
data into a single unit. Some of the key features of ADTs include:
1) Abstraction: The user does not need to know the implementation of the
data structure only essentials are provided.
2) Better Conceptualization: ADT gives us a better conceptualization of the
real world.
3) Robust: The program is robust and has the ability to catch errors.
4) Encapsulation: ADTs hide the internal details of the data and provide a
public interface for users to interact with the data. This allows for easier
maintenance and modification of the data structure.
5) Data Abstraction: ADTs provide a level of abstraction from the
implementation details of the data. Users only need to know the operations
that can be performed on the data, not how those operations are
implemented.
6) Data Structure Independence: ADTs can be implemented using different
data structures, such as arrays or linked lists, without affecting the
functionality of the ADT.
7) Information Hiding: ADTs can protect the integrity of the data by allowing
access only to authorized users and operations. This helps prevent errors
and misuse of the data.
8) Modularity: ADTs can be combined with other ADTs to form larger, more
complex data structures. This allows for greater flexibility and modularity in
programming.
Overall, ADTs provide a powerful tool for organizing and manipulating data in a
structured and efficient manner.
Advantages:
√ Encapsulation: ADTs provide a way to encapsulate data and operations into
a single unit, making it easier to manage and modify the data structure.
 √ Abstraction: ADTs allow users to work with data structures without having
to know the implementation details, which can simplify programming and
reduce errors.
√ Data Structure Independence: ADTs can be implemented using different
data structures, which can make it easier to adapt to changing needs and
requirements.
√ Information Hiding: ADTs can protect the integrity of data by controlling
access and preventing unauthorized modifications.
√ Modularity: ADTs can be combined with other ADTs to form more complex
data structures, which can increase flexibility and modularity in
programming.
Disadvantages:
√ Overhead: Implementing ADTs can add overhead in terms of memory and
processing, which can affect performance.
√ Complexity: ADTs can be complex to implement, especially for large and
complex data structures.
√ Learning Curve: Using ADTs requires knowledge of their implementation
and usage, which can take time and effort to learn.
√ Limited Flexibility: Some ADTs may be limited in their functionality or may
not be suitable for all types of data structures.
√ Cost: Implementing ADTs may require additional resources and investment,
which can increase the cost of development.
List ADT
• List is a collection of elements in sequential order.
• In memory we can store the list in two ways, one way is we can store the
elements in sequential memory locations. This is known as arrays. And the other
way is, we can use pointers or links to associate the elements sequentially. This
known as Linked Lists.

The List can be implemented by two ways

1. Array based implementation.
2. Linked List based implementation.
1. Array Based Implementation
Array is a collection of specific number of same type of data stored in consecutive
memory
locations. Array is a static data structure i.e., the memory should be allocated in
advance and the size is fixed. This will waste the memory space when used space
is less than the allocated space.
Insertion and Deletion operation are expensive as it requires more data
movements
Find and Print list operations takes constant time.

Declaration of Array:
#define maxsize 10
int list[maxsize], n ;
1. Create Operation:
Create operation is used to create the list with „ n „ number of elements .If „ n
„ exceeds the array‟s max size, then elements cannot be inserted into the list.
Otherwise the array elements are stored in the consecutive array locations (i.e.) list
[0], list [1] and so on.
 void Create ( )
{
int i;
cout<<"\nEnter the number of elements to be added in the list:\t";
cin>>n;
cout<<"\nEnter the array elements:\t";
for(i=0;i<n;i++)
cin>>list[i];

}
If n=6, the output of creation is as follows:
list[6]

2. Insert Operation:
Insert operation is used to insert an element at particular position in the existing
list. Inserting the element in the last position of an array is easy. But inserting the
element at a particular position in an array is quite difficult since it involves all the
subsequent elements to be shifted one position to the right.
Routine to insert an element in the array:
void Insert( )
{
int i,data,pos;
cout<<"\nEnter the data to be inserted:\t";
cin>>data;
cout<<"\nEnter the position at which element to be inserted:\t";
cin>>pos;
if (pos==n)
cout<<<“Array overflow”;
for(i = n-1 ; i >= pos-1 ; i--)
list[i+1] = list[i];
list[pos-1] = data;
n=n+1;
Display();
 }

Consider
an array with 5 elements [max elements = 10 ]
After this four data movement, 15 is inserted in the 2nd position of the array.

3. Deletion Operation:
Deletion is the process of removing an element from the array at any
[Link] an element from the end is easy. If an element is to be deleted
from any particular position ,it requires all subsequent element from that position is
shifted one position towards left.
Routine to delete an element in the array:
void Delete( )
{
int i, pos ;
cout<<"\nEnter the position of the data to be deleted:\t";
cin>>pos;
cout<<("\nThe data deleted is:\t %d", list[pos-1];
for(i=pos-1;i<n-1;i++)
list[i]=list[i+1];
n=n-1;
Display();
}
Consider an array with 5 elements [max elements = 10]

4. Display Operation/Traversing a list

Traversal is the process of visiting the elements in a array. Display( ) operation is
used to display all the elements stored in the list. The elements are stored from the
index 0 to n - 1. Using a for loop, the elements in the list are viewed.
Routine to traverse/display elements of the array:
void display( )
{
int i;
cout<<"\n**********Elements in the array**********\n";
for(i=0;i<n;i++)
cout<<list[i];
}

5. Search Operation:
Search( ) operation is used to determine whether a particular element is present in
the list or not. Input the search element to be checked in the list.
Routine to search an element in the array:
void Search( )
{
int search,i,count = 0;
cout<<"\nEnter the element to be searched:\t";
cin>>search;
for(i=0;i<n;i++)
 {
if(search == list[i])
count++;
}
if(count==0)
cout<<"\nElement not present in the list";
else
cout<<"\nElement present in the list";
}
Program for array implementation of List
#include<iostream>
#define maxsize 10
int list[maxsize],n;
using namespace std;
void Create();
void Insert();
void Delet();
void Display();
void Search();
void main()
{
int choice;
clrscr();
do
{
cout<<"\n Array Implementation of List\n";
cout<<"\[Link]\n";
cout<<"\[Link]\n";
cout<<"\[Link]\n";
cout<<"\[Link]\n";
cout<<"\[Link]\n";
cout<<"\[Link]\n";
cout<<"\nEnter your choice:\t";
 cin>>choice;
switch(choice)
{
case 1: Create();
break;
case 2: Insert();
break;
case 3: Delete();
break;
case 4: Display();
break;
case 5: Search();
break;
case 6: exit(1);
default: cout<<"\nEnter option between 1 - 6\n";
break;
}
}while(choice<7);
}
void Create()
{
int i;
cout<<"\nEnter the number of elements to be added in the list:\t";
cin>>n;
cout<<”\nEnter the array elements:\t";
for(i=0;i<n;i++)
cin>>list[i];
Display();
}

void Insert()
{
int i,data,pos;
 cout<<"\nEnter the data to be inserted:\t";
cin>>data;
cout<<"\nEnter the position at which element to be inserted:\t";
cin>>pos;
for(i = n-1 ; i >= pos-1 ; i--)
list[i+1] = list[i];
list[pos-1] = data;
n+=1;
Display();
}
void Delete( )
{
int i,pos;
cout<<"\nEnter the position of the data to be deleted:\t";
cin>>pos;
cout<<"\nThe data deleted is:\t %d", list[pos-1];
for(i=pos-1;i<n-1;i++)
list[i]=list[i+1];
n=n-1;
Display();
}
void Display()
{
int i;
printf("\n**********Elements in the array**********\n");
for(i=0;i<n;i++)
cout<<"%d\t",list[i];
}

void Search()
{
int search,i,count = 0;
cout<<"\nEnter the element to be searched:\t";
 cin>>search;
for(i=0;i<n;i++)
{
if(search == list[i])
{
count++;
}
}
if(count==0)
cout<<"\nElement not present in the list";
else
cout<<"\nElement present in the list";
}
Output
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1
Enter the number of elements to be added in the list: 5
Enter the array elements: 1 2 3 4 5
**********Elements in the array**********
12345
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 2
Enter the data to be inserted: 3
Enter the position at which element to be inserted: 1
**********Elements in the array**********
312345
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 3
Enter the position of the data to be deleted: 4
The data deleted is: 3
**********Elements in the array**********
31245
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 5
Enter the element to be searched: 1
Element present in the list
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice:6
Advantages of array implementation:
[Link] elements are faster to access using random access
[Link] an element is easier
Limitation of array implementation
• An array store its nodes in consecutive memory locations.
• The number of elements in the array is fixed and it is not possible to change
the number of elements .
• Insertion and deletion operation in array are expensive. Since insertion is
performed by pushing the entire array one position down and deletion is
performed by shifting the entire array one position up.
Applications of arrays:

Arrays are particularly used in programs that require storing large collection of
similar type data elements

2. Linked-List Based Implementation

A linked list is essentially a series of nodes connected by links where each node
contains some data (any type) and a pointer to the next node in the list.
Each node contains two fields namely,
Data field-The data field contains the actual data of the elements to be stored in
the list
 Next
field- The next field contains the address of the next node in the list

Advantages of Linked list:

1. Insertion and deletion of elements can be done efficiently
2. It uses dynamic memory allocation
3. Memory utilization is efficient compared to arrays
Disadvantages of linked list:
[Link] list does not support random access
[Link] is required to store next field
[Link] takes time compared to arrays
Types of Linked List
1. Singly Linked List or One Way List
2. Doubly Linked List or Two-Way Linked List
3. Circular Linked List
1. Singly Linked List or One Way List
A singly linked list is a fundamental data structure in computer science and programming, it
consists of nodes where each node contains a data field and a reference to the next node in
the node. The last node points to null, indicating the end of the list. This linear structure
supports efficient insertion and deletion operations, making it widely used in various
applications.
Understanding Node Structure
In a singly linked list, each node consists of two parts: data and a pointer to the next node.
The data part stores the actual information, while the pointer (or reference) part stores the
address of the next node in the sequence. This structure allows nodes to be dynamically
linked together, forming a chain-like sequence.
In this representation, each box represents a node, with an arrow indicating the link to the
next node. The last node points to NULL, indicating the end of the list.
struct Node
{
int data;
Node* next;
Node(int data)
{
this->data = data;
this->next = nullptr;
}
};
Operations on Singly Linked List
● Traversal
● Searching
● Length
● Insertion:
Insert at the beginning
Insert at the end
Insert at a specific position
● Deletion:
Delete from the beginning
Delete from the end
Delete a specific node
Traversal in Singly Linked List
Traversal involves visiting each node in the linked list and performing some operation on the
data. A simple traversal function would print or process the data of each node.
Step-by-step approach:
1. Initialize a pointer current to the head of the list.
2. Use a while loop to iterate through the list until the current pointer reaches NULL.
3. Inside the loop, print the data of the current node and move the current pointer to the
next node.
void traverseLinkedList(Node* head)
{
// Start from the head of the linked list
Node* current = head;
// Traverse the linked list until reaching the end (nullptr)
while (current != nullptr)
{
// Print the data of the current node
cout << current->data << " ";
// Move to the next node
current = current->next;
}
cout << endl;
}
Searching in Singly Linked List
Searching in a Singly Linked List refers to the process of looking for a specific element or
value within the elements of the linked list.
Step-by-step approach:
1. Traverse the Linked List starting from the head.
2. Check if the current node's data matches the target value.
3. If a match is found, return true.
4. Otherwise, Move to the next node and repeat steps 2.
5. If the end of the list is reached without finding a match, return false.
// Function to search for a value in the Linked List
bool searchLinkedList(struct Node* head, int target)
{
// Traverse the Linked List
while (head != nullptr)
{
// Check if the current node's
 // data matches the target value
if (head->data == target)
{
return true; // Value found
}
// Move to the next node
head = head->next;
}
return false; // Value not found
}
Finding Length in Singly Linked List
Finding Length in Singly Linked List refers to the process of determining the total number of
nodes in a singly linked list.
Step-by-step approach:
1. Initialize a counter length to 0.
2. Start from the head of the list, assign it to current.
3. Traverse the list:
4. Increment length for each node.
5. Move to the next node (current = current->next).
6. Return the final value of length.
int findLength(Node* head)
{
// Initialize a counter for the length
int length = 0;
// Start from the head of the list
Node* current = head;
// Traverse the list and increment the length for each node
while (current != nullptr)
{
length++;
current = current->next;
}
// Return the final length of the linked list
return length;
}

Insertion in Singly Linked List

Insertion is a fundamental operation in linked lists that involves adding a new node to the
list. There are several scenarios for insertion:
a. Insertion at the Beginning of Singly Linked List:

Step-by-step approach:
1. Create a new node with the given value.
2. Set the next pointer of the new node to the current head.
3. Move the head to point to the new node.
4. Return the new head of the linked list.

Node* insertAtBeginning(Node* head, int value)

{
// Create a new node with the given value
Node* newNode = new Node(value);
// Set the next pointer of the new node to the current head
newNode->next = head;
// Move the head to point to the new node
head = newNode;
// Return the new head of the linked list
return head;
}
b. Insertion at the End of Singly Linked List:
To insert a node at the end of the list, traverse the list until the last node is reached, and then
link the new node to the current last node-
Step-by-step approach:
1. Create a new node with the given value.
2. Check if the list is empty:
3. If it is, make the new node the head and return.
4. Traverse the list until the last node is reached.
5. Link the new node to the current last node by setting the last node's next pointer to
the new node.
Node* insertAtEnd(Node* head, int value)
{
// Create a new node with the given value
Node* newNode = new Node(value);
// If the list is empty, make the new node the head
if (head == nullptr)
return newNode;
// Traverse the list until the last node is reached
Node* curr = head;
while (curr->next != nullptr)
{
curr = curr->next;
}
 // Link the new node to the current last node
curr->next = newNode;
return head;
}

c. Insertion at a Specific Position of the Singly Linked List:

To insert a node
at a specific position, traverse the list to the desired position, link the new node to the next
node, and update the links accordingly.

We mainly find the node after which we need to insert the new node. If we encounter a NULL
before reaching that node, it means that the given position is invalid.
Node* insertPos(Node* head, int pos, int data)
{
if (pos < 1) {
cout << "Invalid position!" << endl;
return head;
}
// Special case for inserting at the head
if (pos == 1)
{
Node* temp = new Node(data);
temp->next = head;
return temp;
 }
// Traverse the list to find the node before the insertion point
Node* prev = head;
int count = 1;
while (count < pos - 1 && prev != nullptr)
{
prev = prev->next;
count++;
}
// If position is greater than the number of nodes
if (prev == nullptr)
{
cout << "Invalid position!" << endl;
return head;
}
// Insert the new node at the specified position
Node* temp = new Node(data);
temp->next = prev->next;
prev->next = temp;
return head;
}
Deletion in Singly Linked List
Deletion involves removing a node from the linked list. Similar to insertion, there are different
scenarios for deletion:
a. Deletion at the Beginning of Singly Linked List:

To delete
the first node, update the head to point to the second node in the list.
Steps-by-step approach:
Check if the head is NULL.
1. If it is, return NULL (the list is empty).
Store the current head node in a temporary variable temp.
Move the head pointer to the next node.
Delete the temporary node.
Return the new head of the linked list.
Node* removeFirstNode(Node* head)
{
if (head == nullptr)
return nullptr;
// Move the head pointer to the next node
Node* temp = head;
head = head->next;
delete temp;
return head;
}
b. Deletion at the End of Singly Linked List:

To
delete the last node, traverse the list until the second-to-last node and update its next field to
None.
Step-by-step approach:
1. Check if the head is NULL.
If it is, return NULL (the list is empty).
2. Check if the head's next is NULL (only one node in the list).
If true, delete the head and return NULL.
3. Traverse the list to find the second last node (second_last).
4. Delete the last node (the node after second_last).
5. Set the next pointer of the second last node to NULL.
6. Return the head of the linked list.
Node* removeLastNode(Node* head)
{
if (head == nullptr)
return nullptr;
if (head->next == nullptr) {
delete head;
return nullptr;
}
// Find the second last node
Node* second_last = head;
while (second_last->next->next != nullptr)
second_last = second_last->next;
// Delete last node
delete (second_last->next);
// Change next of second last
second_last->next = nullptr;
return head;
}
c. Deletion at a Specific Position of Singly Linked List:
 To
delete a node at a specific position, traverse the list to the desired position, update the links to
bypass the node to be deleted.

Step-by-step approach:
1. Check if the list is empty or the position is invalid, return if so.
2. If the head needs to be deleted, update the head and delete the node.
3. Traverse to the node before the position to be deleted.
4. If the position is out of range, return.
5. Store the node to be deleted.
6. Update the links to bypass the node.
7. Delete the stored node.
Node* deleteAtPosition(Node* head, int position)
{
// If the list is empty or the position is invalid
if (head == nullptr || position < 1)
{
return head;
 }
// If the head needs to be deleted
if (position == 1)
{
Node* temp = head;
head = head->next;
delete temp;
return head;
}
// Traverse to the node before the position to be
// deleted
Node* current = head;
for (int i = 1; i < position - 1 && current != nullptr; i++)
{
current = current->next;
}
// If the position is out of range
if (current == NULL || current->next == nullptr)
{
return;
}
// Store the node to be deleted
Node* temp = current->next;
// Update the links to bypass the node to be deleted
current->next = current->next->next;
// Delete the node
delete temp;
return head;
}
Example Program using singly linked list
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
void insertStart(Node** head, int data)
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = *head;
*head = newNode;
cout << "\n" << newNode->data << " Inserted" << endl;
}
void deleteStart(Node** head)
{
Node* temp = *head;
if (*head == nullptr)
{
cout << "Linked List Empty, nothing to delete" << endl;
return;
}
*head = (*head)->next;
cout << "\n" << temp->data << " deleted" << endl;
delete temp;
}
void display(Node* node)
{
cout << "\nLinked List: ";
while (node != nullptr)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main()
{
Node* head = nullptr;
insertStart(&head, 100);
insertStart(&head, 80);
 insertStart(&head, 60);
insertStart(&head, 40);
insertStart(&head, 20);
display(head);
deleteStart(&head);
deleteStart(&head);
display(head);
return 0;
}
Output
100 Inserted
80 Inserted
60 Inserted
40 Inserted
20 Inserted
Linked List: 20 40 60 80 100
20 deleted
40 deleted
Linked List: 60 80 100
Disadvantages of singly linked list in CPP programming
• Members could be assigned anywhere in the memory.
• Each member shall include an address size member, hence it utilizes poor memory.
• Some operations like reversing a list is complicated when compared with arrays,
2. Doubly Linked List or Two-Way Linked List
A Doubly Linked List (DLL) is a two-way list in which each node has two pointers,
the next and previous that have reference to both the next node and previous node
respectively. Unlike a singly linked list where each node only points to the next
node, a doubly linked list has an extra previous pointer that allows traversal in both
the forward and backward directions.
Creating a Node in Doubly Linked List in C++

Each node of a doubly linked list (DLL) consists of three fields:

Item or Data: It is the value stored in the node.
 Next: A reference to the next node in the list.
Previous: A reference to the last node in the list.

Structure of the Doubly linked list

The following set of code is used to struct the nodes of a doubly linked list. Here we have
defined a doubly linked list that will store integer type data in it.
struct node {
int data;
struct node *next;
struct node *prev;
}
Operation on doubly linked list in C++
We can perform following operations on a doubly linked list in C++ programming language.
Insertion
Inserting at Beginning of the list.
Inserting at End of the list.
Inserting at Specific location in the list.
Deletion
Deleting from Beginning of the list.
Deleting from End of the list.
Deleting a Specific Node from the list
1. Add a node at the front of DLL: The new node is always added before the head
of the given Linked List. And the newly added node becomes the new head of
DLL & maintaining a global variable for counting the total number of nodes at
that time.
2. Traversal of a Doubly linked list
3. Insertion of a node: This can be done in three ways:
● At the beginning: The new created node is insert in before the head node
and head points to the new node.
● At the end: The new created node is insert at the end of the list and tail
points to the new node.
● At a given position: Traverse the given DLL to that position(let the node be
X) then do the following:
1. Change the next pointer of new Node to the next pointer of Node X.
2. Change the prev pointer of next Node of Node X to the new Node.
3. Change the next pointer of node X to new Node.
4. Change the prev pointer of new Node to the Node X.
4. Deletion of a node: This can be done in three ways:
 ● At the beginning: Move head to the next node to delete the node at the
beginning and make previous pointer of current head to NULL .
● At the last: Move tail to the previous node to delete the node at the end and
make next pointer of tail node to NULL.
● At a given position: Let the prev node of Node at position pos be Node X
and next node be Node Y, then do the following:
1. Change the next pointer of Node X to Node Y.
2. Change the previous pointer of Node Y to Node X.
Program using Doubly linked list
// C++ program to implement all functions used in Doubly Linked List
#include <iostream>
#include <stdlib.h>
using namespace std;
int i = 0;
// Node for Doubly Linked List
typedef struct node
{
int key;
struct node* prev;
struct node* next;
} node;
// Head, Tail, first & temp Node
node* head = NULL;
node* first = NULL;
node* temp = NULL;
node* tail = NULL;
// Function to add a node in the Doubly Linked List
void addnode(int k)
{
// Allocating memoryto the Node ptr
node* ptr= (node*)malloc(sizeof(node));
// Assign Key to value k
ptr->key = k;
// Next and prev pointer to NULL
ptr->next = NULL;
ptr->prev = NULL;
// If Linked List is empty
if (head == NULL)
{
head = ptr;
first = head;
tail = head;
}
// Else insert at the end of the Linked List
else
{
temp = ptr;
first->next = temp;
temp->prev = first;
first = temp;
tail = temp;
}
// Increment for number of Nodes in the Doubly Linked List
i++;
}
// Function to traverse the Doubly Linked List
void traverse()
{
// Nodes points towards head node
node* ptr = head;
// While pointer is not NULL traverse and print the node
while (ptr != NULL)
{
// Print key of the node
cout <<" " << ptr->key;
ptr = ptr->next;
}
cout <<"\n";
}
// Function to insert a node at the beginning of the linked list
void insertatbegin(int k)
{
// Allocating memory to the Node ptr
node* ptr= (node*)malloc(sizeof(node));
// Assign Key to value k
ptr->key = k;
// Next and prev pointer to NULL
ptr->next = NULL;
ptr->prev = NULL;
// If head is NULL
if (head == NULL)
{
first = ptr;
first = head;
tail = head;
}
// Else insert at beginning and change the head to current node
else
{
temp = ptr;
temp->next = head;
head->prev = temp;
head = temp;
}
i++;
}
// Function to insert Node at end
void insertatend(int k)
{
// Allocating memory to the Node ptr
node* ptr= (node*)malloc(sizeof(node));

// Assign Key to value k

ptr->key = k;
// Next and prev pointer to NULL
ptr->next = NULL;
ptr->prev = NULL;
// If head is NULL
if (head == NULL)
 {
first = ptr;
first = head;
tail = head;
}
// Else insert at the end
else {
temp = ptr;
temp->prev = tail;
tail->next = temp;
tail = temp;
}
i++;
}
// Function to insert Node at any position pos
void insertatpos(int k, int pos)
{
// For Invalid Position
if (pos < 1 || pos > i + 1)
{
cout <<"Please enter a valid position\n";
}
// If position is at the front, then call insertatbegin()
else if (pos == 1)
{
insertatbegin(k);
}

// Position is at length of Linked list + 1, then insert at the end

else if (pos == i + 1)
{
insertatend(k);
}
// Else traverse till position pos and insert the Node
else
{
 node* src = head;
// Move head pointer to pos
while (pos--)
{
src = src->next;
}
// Allocate memory to new Node
node **da, **ba;
node* ptr= (node*)malloc(sizeof(node));
ptr->next = NULL;
ptr->prev = NULL;
ptr->key = k;
// Change the previous and next pointer of the nodes inserted
// with previous and next node
ba = &src;
da = &(src->prev);
ptr->next = (*ba);
ptr->prev = (*da);
(*da)->next = ptr;
(*ba)->prev = ptr;
i++;
}
}
// Function to delete node at the beginning of the list
void delatbegin()
{
// Move head to next and
// decrease length by 1
head = head->next;
i--;
}
// Function to delete at the end of the list
void delatend()
{
// Mode tail to the prev and
// decrease length by 1
tail = tail->prev;
tail->next = NULL;
i--;
}
// Function to delete the node at a given position pos
void delatpos(int pos)
{
// If invalid position
if (pos < 1 || pos > i + 1)
{
cout <<"Please enter a valid position\n";
}
// If position is 1, then call delatbegin()
else if (pos == 1)
{
delatbegin();
}
// If position is at the end, then call delatend()
else if (pos == i)
{
delatend();
}

// Else traverse till pos, and delete the node at pos

else {
// Src node to find which node to be deleted
node* src = head;
pos--;
// Traverse node till pos
while (pos--)
{
src = src->next;
}
// previous and after node of the src node
node **pre, **aft;
pre = &(src->prev);
 aft = &(src->next);
// Change the next and prev pointer of pre and aft node
(*pre)->next = (*aft);
(*aft)->prev = (*pre);
// Decrease the length of the Linked List
i--;
}
}
// Driver Code
int main()
{
// Adding node to the linked List
addnode(2);
addnode(4);
addnode(9);
addnode(1);
addnode(21);
addnode(22);
// To print the linked List
cout <<"Linked List: ";
traverse();
cout <<"\n";
// To insert node at the beginning
insertatbegin(1);
cout <<"Linked List after inserting 1 at beginning: ";
traverse();
// To insert at the end
insertatend(0);
cout <<"Linked List after inserting 0 at end: ";
traverse();
// To insert Node with value 44 after 3rd Node
insertatpos(44, 3);
cout <<"Linked List after inserting 44 after 3rd Node: ";
traverse();
cout <<"\n";
// To delete node at the beginning
delatbegin();
cout <<"Linked List after deleting node at beginning: ";
traverse();
// To delete at the end
delatend();
cout <<"Linked List after deleting node at end: ";
traverse();
// To delete Node at position 5
cout <<"Linked List after deleting nodeat position 5: ";
delatpos(5);
traverse();
return 0;
}
Output:
Linked List: 2 4 9 1 21 22
Linked List after inserting 1 at beginning: 1 2 4 9 1 21 22
Linked List after inserting 0 at end: 1 2 4 9 1 21 22 0
Linked List after inserting 44 after 3rd Node: 1 2 4 44 9 1 21 22 0

Linked List after deleting node at beginning: 2 4 44 9 1 21 22 0

Linked List after deleting node at end: 2 4 44 9 1 21 22
Linked List after deleting node at position 5: 2 4 44 9 21 22

Advantages of a Doubly Linked List

Allows us to iterate in both directions.
We can delete a node easily as we have access to its previous node.
Reversing is easy.
Can grow or shrink in size dynamically.
Disadvantages of a Doubly Linked List
They use more memory than arrays because of the storage used by their pointers.
3. Circular Linked List
A circular linked list is a linear data structure similar to a singly linked list where each node
consists of two data members data and a pointer next, that stores the address of the next
node in the sequence but in a circular linked list, the last node of the list points to the first
node instead of NULL creating a circular chain of nodes.
Types of Circular Linked Lists
We can create a circular linked list from both singly linked lists and doubly linked lists. So,
circular linked list are basically of two types:
1. Circular Singly Linked List
In Circular Singly Linked List, each node has just one pointer called the “next” pointer. The
next pointer of last node points back to the first node and this results in forming a circle. In
this type of Linked list we can only move through the list in one direction.

2. Circular Doubly Linked List:

In circular doubly linked list, each node has two pointers prev and next, similar to doubly
linked list. The prev pointer points to the previous node and the next points to the next node.
Here, in addition to the last node storing the address of the first node, the first node will also
store the address of the last node.

Representation of a Circular Singly Linked List

Let’s take a look on the structure of a circular linked list.

Operations on the Circular Linked list:

We can do some operations on the circular linked list similar to the singly and doubly linked
 list which are:
• Insertion
Insertion at the empty list
Insertion at the beginning
Insertion at the end
Insertion at the given position
• Deletion
Delete the first node
Delete the last node
Delete the node from any position
• Searching
Syntax to Declare a Circular Linked List:
// Node structure
struct Node
{
int data;
Node* next;
Node(int value)
{
data = value;
next = nullptr;
}
};

In the code above, each node has data and a pointer to the next node. When we create
multiple nodes for a circular linked list, we only need to connect the last node back to
the first one.
Example of Creating a Circular Linked List
Here’s an example of creating a circular linked list with three nodes (2, 3, 4):

// Initilize and allocate memory for nodes

 first = new Node(2);
second = new Node(3);
last = new Node(4);

// Connect nodes
first->next = second;
second->next = last;

// Connect last node to first node

last->next = first;
In the above code, we have created three nodes first, second, and last having values 2, 3,
and 4 respectively.
● After creating three nodes, we have connected these node in a series.
● Connect the first node “first” to “second” node by storing the address of “second”
node into first’s next
● Connect the second node “second” to “second” node by storing the address of
“third” node into second’s next
● After connecting all the nodes, we reach the key characteristic of a circular linked
list: linking the last node back to the first node. Therefore, we store the address of
the “first” node in the “last” node.
1. Insertion in the circular linked list:
Insertion is a fundamental operation in linked lists that involves adding a new node
to the list. The only extra step is connecting the last node to the first one. In the
circular linked list mentioned below, we can insert nodes in four ways:
A. Insertion in an empty List in the circular linked list
To insert a node in empty circular linked list, creates a new node with the given
data, sets its next pointer to point to itself, and updates the last pointer to
reference this new node.

#include <iostream>
using namespace std;
struct Node
{
 int data;
Node *next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to insert a node into an empty circular singly linked list
Node *insertInEmptyList(Node *last, int data)
{
if (last != nullptr) return last;
// Create a new node
Node *newNode = new Node(data);
// Point newNode to itself
newNode->next = newNode;
// Update last to point to the new node
last = newNode;
return last;
}
void printList(Node* last)
{
if(last == NULL) return;
// Start from the head node
Node* head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
cout << endl;
}
int main()
 {
Node *last = nullptr;
// Insert a node into the empty list
last = insertInEmptyList(last, 1);
// Print the list
cout << "List after insertion: ";
printList(last);
return 0;
}
OUTPUT
List after insertion: 1
B. Insertion at the beginning in circular linked list
To insert a new node at the beginning of a circular linked list, we first create the
new node and allocate memory for it. If the list is empty (indicated by the last
pointer being NULL), we make the new node point to itself. If the list already
contains nodes then we set the new node’s next pointer to point to the current
head of the list (which is last->next), and then update the last node’s next pointer
to point to the new node. This maintains the circular structure of the list.

#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
 Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to insert a node at the beginning of the circular linked list
Node* insertAtBeginning(Node* last, int value)
{
// Allocate memory for the new node and set its data
Node* newNode = new Node(value);
// If the list is empty, make the new node point to itself and set it as last
if (last == nullptr)
{
newNode->next = newNode;
return newNode;
}
// Insert the new node at the beginning
newNode->next = last->next;
last->next = newNode;
return last;
}
void printList(Node* last)
{
if(last == NULL) return;
// Start from the head node
Node* head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next)
break;
}
 cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node* last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
// Insert 5 at the beginning
last = insertAtBeginning(last, 5);
cout << "List after inserting 5 at the beginning: ";
printList(last);
return 0;
}

Output
Original list: 2 3 4
List after inserting 5 at the beginning: 5 2 3 4
C. Insertion at the end in circular linked list
To insert a new node at the end of a circular linked list, we first create the new
node and allocate memory for it. If the list is empty (mean, last or tail pointer
being NULL), we initialize the list with the new node and making it point to itself
to form a circular structure. If the list already contains nodes then we set the
new node’s next pointer to point to the current head (which is tail->next), then
update the current tail’s next pointer to point to the new node. Finally, we update
the tail pointer to the new node. This will ensure that the new node is now the
last node in the list while maintaining the circular linkage.
#include <iostream>
using namespace std;
struct Node{
int data;
Node *next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to insert a node at the end of a circular linked list
Node *insertEnd(Node *tail, int value)
{
Node *newNode = new Node(value);
if (tail == nullptr){
// If the list is empty, initialize it with the new node
tail = newNode;
// Point to itself to form a circular structure
newNode->next = newNode;
}
 else{
// Insert new node after the current tail
// and update the tail pointer.
// New node points to the head node
newNode->next = tail->next;
// Tail node points to the new node
tail->next = newNode;
// Update tail to be the new node
tail = newNode;
}
return tail;
}
void printList(Node *last)
{
if(last == NULL) return;
// Start from the head node
Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next)
break;
}
cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node *first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node *last = first->next->next;
last->next = first;
 cout << "Original list: ";
printList(last);
// Insert elements at the end of the circular linked list
last = insertEnd(last, 5);
last = insertEnd(last, 6);
cout << "List after inserting 5 and 6: ";
printList(last);
return 0;
}
Output
Original list: 2 3 4
List after inserting 5 and 6: 2 3 4 5 6
D. Insertion at specific position in circular linked list
To insert a new node at a specific position in a circular linked list, we first check
if the list is empty. If it is and the position is not 1 then we print an error message
because the position doesn’t exist in the list. If the position is 1 then we create
the new node and make it point to itself. If the list is not empty, we create the
new node and traverse the list to find the correct insertion point. If the position is
1, we insert the new node at the beginning by adjusting the pointers accordingly.
For other positions, we traverse through the list until we reach the desired
position and inserting the new node by updating the pointers. If the new node is
inserted at the end, we also update the last pointer to reference the new node,
maintaining the circular structure of the list.

#include <iostream>
using namespace std;
struct Node
{
int data;
Node *next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to insert a node at a specific position in a circular linked list
Node *insertAtPosition(Node *last, int data, int pos)
{
if (last == nullptr)
{
// If the list is empty
if (pos != 1)
{
cout << "Invalid position!" << endl;
return last;
}
// Create a new node and make it point to itself
Node *newNode = new Node(data);
last = newNode;
last->next = last;
return last;
}
// Create a new node with the given data
Node *newNode = new Node(data);
// curr will point to head initially
Node *curr = last->next;
if (pos == 1)
{
// Insert at the beginning
 newNode->next = curr;
last->next = newNode;
return last;
}

// Traverse the list to find the insertion point

for (int i = 1; i < pos - 1; ++i)
{
curr = curr->next;
// If position is out of bounds
if (curr == last->next)
{
cout << "Invalid position!" << endl;
return last;
}
}
// Insert the new node at the desired position
newNode->next = curr->next;
curr->next = newNode;
// Update last if the new node is inserted at the end
if (curr == last) last = newNode;
return last;
}
void printList(Node *last)
{
if (last == NULL) return;
Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
 cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node *first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node *last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
// Insert elements at specific positions
int data = 5, pos = 2;
last = insertAtPosition(last, data, pos);
cout << "List after insertions: ";
printList(last);
return 0;
}
Output
Original list: 2 3 4
List after insertions: 2 5 3 4
2. Deletion from a Circular Linked List
Deletion involves removing a node from the linked list. The main difference is
that we need to ensure the list remains circular after the deletion. We can delete
a node in a circular linked list in three ways:
A. Delete the first node in circular linked list
To delete the first node of a circular linked list, we first check if the list is empty.
If it is then we print a message and return NULL. If the list contains only one
node (the head is the same as the last) then we delete that node and set the last
pointer to NULL. If there are multiple nodes then we update the last->next
pointer to skip the head node and effectively removing it from the list. We then
delete the head node to free the allocated memory. Finally, we return the updated
last pointer, which still points to the last node in the list.
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to delete the first node of the circular linked list
Node* deleteFirstNode(Node* last)
{
if (last == nullptr)
{
// If the list is empty
cout << "List is empty" << endl;
return nullptr;
}
Node* head = last->next;
if (head == last)
{
 // If there is only one node in the list
delete head;
last = nullptr;
}
else
{
// More than one node in the list
last->next = head->next;
delete head;
}
return last;
}
void printList(Node* last)
{
if(last == NULL) return ;
Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node* last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
 // Delete the first node
last = deleteFirstNode(last);
cout << "List after deleting first node: ";
printList(last);
return 0;
}
Output
Original list: 2 3 4 List after deleting first node: 3 4
B. Delete a specific node in circular linked list

To
delete a specific node from a circular linked list, we first check if the list is empty.
If it is then we print a message and return nullptr. If the list contains only one
node and it matches the key then we delete that node and set last to nullptr. If
the node to be deleted is the first node then we update the next pointer of the
last node to skip the head node and delete the head. For other nodes, we
traverse the list using two pointers: curr (to find the node) and prev (to keep
track of the previous node). If we find the node with the matching key then we
update the next pointer of prev to skip the curr node and delete it. If the node is
found and it is the last node, we update the last pointer accordingly. If the node
is not found then do nothing and tail or last as it is. Finally, we return the updated
last pointer.

#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
Node(int value)
 {
data = value;
next = nullptr;
}
};
// Function to delete a specific node in the circular linked list
Node* deleteSpecificNode(Node* last, int key)
{
if (last == nullptr)
{
// If the list is empty
cout << "List is empty, nothing to delete." << endl;
return nullptr;
}
Node* curr = last->next;
Node* prev = last;
// If the node to be deleted is the only node in the list
if (curr == last && curr->data == key)
{
delete curr;
last = nullptr;
return last;
}
// If the node to be deleted is the first node
if (curr->data == key)
{
last->next = curr->next;
delete curr;
return last;
}
// Traverse the list to find the node to be deleted
while (curr != last && curr->data != key)
{
prev = curr;
 curr = curr->next;
}
// If the node to be deleted is found
if (curr->data == key)
{
prev->next = curr->next;
if (curr == last) {
last = prev;
}
delete curr;
}
else
{
// If the node to be deleted is not found
cout << "Node with data " << key
<< " not found." << endl;
}
return last;
}
// Function to print the circular linked list
void printList(Node* last)
{
if (last == NULL)
{
cout << "List is Empty";
return;
}
Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
 cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node* last = first->next->next;
last->next = first;

cout << "Original list: ";

printList(last);
// Delete a specific node
int key = 3;
last = deleteSpecificNode(last, key);
cout << "List after deleting node " << key << ": ";
printList(last);
return 0;
}
Output
Original list: 2 3 4
List after deleting node 3: 2 4
C. Deletion at the end of Circular linked list

To
delete the last node in a circular linked list, we first check if the list is empty. If it
is, we print a message and return nullptr. If the list contains only one node (where
the head is the same as the last), we delete that node and set last to nullptr. For
lists with multiple nodes, we need to traverse the list to find the second last
node. We do this by starting from the head and moving through the list until we
reach the node whose next pointer points to last. Once we find the second last
node then we update its next pointer to point back to the head, this effectively
removing the last node from the list. We then delete the last node to free up
memory and return the updated last pointer, which now points to the last node.

#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to delete the last node in the circular linked list
Node* deleteLastNode(Node* last)
{
if (last == nullptr)
{
// If the list is empty
cout << "List is empty, nothing to delete." << endl;
return nullptr;
}
Node* head = last->next;
// If there is only one node in the list
if (head == last)
{
delete last;
 last = nullptr;
return last;
}
// Traverse the list to find the second last node
Node* curr = head;
while (curr->next != last)
{
curr = curr->next;
}
// Update the second last node's next pointer
// to point to head
curr->next = head;
delete last;
last = curr;
return last;
}
void printList(Node* last)
{
if(last == NULL) return;
Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
 Node* last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
// Delete the last node
last = deleteLastNode(last);
cout << "List after deleting last node: ";
printList(last);
return 0;
}
Output
Original list: 2 3 4
List after deleting last node: 2 3

3. Searching in Circular Linked list

Searching in a circular linked list is similar to searching in a regular linked list. We
start at a given node and traverse the list until you either find the target value or
return to the starting node. Since the list is circular, make sure to keep track of
where you started to avoid an infinite loop.
To search for a specific value in a circular linked list, we first check if the list is
empty. If it is then we return false. If the list contains nodes then we start from the
head node (which is the last->next) and traverse the list. We use a pointer curr to
iterate through the nodes until we reach back to the head. During traversal, if we find
a node whose data matches the given key then we return true to indicating that the
value was found. After the loop, we also check the last node to ensure we don’t
miss it. If the key is not found after traversing the entire list then we return false.
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
Node(int value)
{
data = value;
next = nullptr;
}
};
// Function to search for a specific value in the circular linked list
bool search(Node* last, int key)
{
if (last == nullptr)
{
// If the list is empty
return false;
}
Node* head = last->next;
Node* curr = head;
// Traverse the list to find the key

while (curr != last)

{
if (curr->data == key)
{
// Key found
return true;
}
curr = curr->next;
}
// Check the last node
if (last->data == key)
{
// Key found
return true;
}
// Key not found
return false;
}
void printList(Node* last)
{
if(last == NULL) return;
 Node *head = last->next;
while (true)
{
cout << head->data << " ";
head = head->next;
if (head == last->next) break;
}
cout << endl;
}
int main()
{
// Create circular linked list: 2, 3, 4
Node* first = new Node(2);
first->next = new Node(3);
first->next->next = new Node(4);
Node* last = first->next->next;
last->next = first;
cout << "Original list: ";
printList(last);
// Search for a specific value
int key = 3;
bool found = search(last, key);
if (found)
{
cout << "Value " << key << " found in the list." << endl;
} else {
cout << "Value " << key << " not found in the list." << endl;
}
return 0;
}
Output
Original list: 2 3 4
Value 3 found in the list.
What Are The Operations Supported by Linked List?
The operations supported by the linked list data structure are as follows:
1. Traversal
Traversal operations are used to visit each node in a data structure in a specific
order. This technique is typically employed for printing, searching, displaying, and
reading the data stored in a data structure.
2. Insertion
This operation is beneficial for adding a new element to the linked list, which can
be done at any position in the list, including the tail or the head.
3. Deletion
This operation is beneficial for removing an element from a linked list data
 structure. This can also be done at any position on the list.
4. Display
With this operation, one can visit each element in the linked list in a specific order
from head to tail.
5. Search
This operation allows one to search for a particular element in the linked list data
structure. This can be done by crossing the list and comparing every element to
the target.
6. Sort
Sort operations are used to arrange the data elements in a data structure in a
specific order. This can be done using various sorting algorithms, such as
insertion sort, bubble sort, merge sort, and quick sort.
7. Merge
Merge operations are used to combine two data structures into one. This
operation is typically used when two data structures need to be combined into a
single structure.
8. Copy
Copy operations are used to create a duplicate of a data structure. This can be
done by copying each element in the original data structure to the new one.
Applications of List
The linked list data structure is used to work on various computer science and
programming projects.
● Implementation of Data Structures: Hash tables, stacks in data structures, and
queues are just a few of the significant data structures that may be implemented
using the linked list data structures.
● Memory Management: To efficiently allocate and reallocate memory, Linked
Lists data structures can be utilised in memory management systems.
● File Systems: File systems can be represented using linked lists data
structures. A node represents each file or directory; the links signify the parent-
child relationships between the files and directories.
● Graphs and Charts: Graphs can be represented by Linked Lists data structure,
where each node is a vertex, and the links are the edges that connect them.
● Making music playlists: Linked List data structures are frequently used to build
music playlists. A node represents each song, and the connections between the
nodes indicate the order in which the songs are played.
● Picture Processing Method: Picture processing methods can be implemented
using linked lists, where a node represents each pixel.
Polynomial Manipulation
Polynomial manipulations are one of the most important applications of linked lists.
Polynomials are an important part of mathematics not inherently supported as a data
type by most languages. A polynomial is a collection of different terms, each
comprising coefficients, and exponents. It can be represented using a linked list. This
representation makes polynomial manipulation efficient.
Each node of a linked list representing polynomial constitute three parts:
● The first part contains the value of the coefficient of the term.
● The second part contains the value of the exponent.
● The third part, LINK points to the next term (next node).
The structure of a node of a linked list that represents a polynomial is shown below:

4 3 2
Consider a polynomial P(x) = 7x + 15x - 2 x + 9. Here 7, 15, -2, and 9 are the
coefficients, and 4,3,2,0 are the exponents of the terms in the polynomial. On
representing this polynomial using a linked list, we have

Observe that the number of nodes equals the number of terms in the polynomial. So
we have 4 nodes. Moreover, the terms are stored to decrease exponents in the linked
list. Such representation of polynomial using linked lists makes the operations like
subtraction, addition, multiplication, etc., on polynomial very easy.
Addition of Polynomials:
To add two polynomials,
● we traverse the list P and Q. We take corresponding terms of the list P and Q
and compare their exponents.
● If the two exponents are equal, the coefficients are added to create a new
coefficient.
o If the new coefficient is equal to 0, then the term is dropped, and if it is not
zero, it is inserted at the end of the new linked list containing the resulting
polynomial.
● If one of the exponents is larger than the other, the corresponding term is
immediately placed into the new linked list, and the term with the smaller
exponent is held to be compared with the next term from the other list. If one list
ends before the other, the rest of the terms of the longer list is inserted at the
end of the new linked list containing the resulting polynomial.
Let us consider an example an example to show how the addition of two polynomials is
performed,
4 3 2
P(x) = 3x + 2x - 4 x + 7
3 2
Q (x) = 5x + 4 x - 5

These polynomials are represented using a linked list in order of decreasing exponents as
follows:

To generate a new linked list for the resulting polynomials that is formed on the
addition of given polynomials P(x) and Q(x), we perform the following steps,
1. Traverse the two lists P and Q and examine all the nodes.
2. We compare the exponents of the corresponding terms of two polynomials.
The first term of polynomials P and Q contain exponents 4 and 3, respectively.
Since the exponent of the first term of the polynomial P is greater than the other
polynomial Q, the term having a larger exponent is inserted into the new list. The
new list initially looks as shown below:
 3. We then compare the exponent of the next term of the list P with the exponents
of the present term of list Q. Since the two exponents are equal, so their
coefficients are added and appended to the new list as follows:

4.

Then we move to the next term of P and Q lists and compare their exponents.
Since exponents of both these terms are equal and after addition of their
coefficients, we get 0, so the term is dropped, and no node is appended to the
new list after this,

5.

Moving to the next term of the two lists, P and Q, we find that the corresponding
terms have the same exponents equal to 0. We add their coefficients and
append them to the new list for the resulting polynomial as shown below:
Example:
C++ program to add two polynomials
Input:
 2 1 0
1st number = 5x + 4x + 2x
1 0
2nd number = -5x - 5x
Output:
2 1 0
5x -1x -3x

-1 -3

// C++ program for addition of two // polynomials using Linked Lists

#include <bits/stdc++.h>
using namespace std;
struct Node
{
int coeff;
int pow;
struct Node* next;
};
// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL)
{
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
else
{
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
// Function Adding two polynomial numbers
void polyadd(struct Node* poly1,struct Node* poly2, struct Node* poly)
{
while (poly1->next &&
poly2->next)
{
// If power of 1st polynomial is greater // than 2nd, then store 1st as it is and
// move its pointer
if (poly1->pow > poly2->pow)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
// If power of 2nd polynomial is greater // than 1st, then store 2nd as it is and
// move its pointer
else if (poly1->pow < poly2->pow)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
// If power of both polynomial numbers // is same then add their coefficients
else
{
poly->pow = poly1->pow;
poly->coeff = (poly1->coeff + poly2->coeff);
poly1 = poly1->next;
poly2 = poly2->next;
}
// Dynamically create new node
poly->next = (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
while (poly1->next || poly2->next)
{
if (poly1->next)
{
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
 poly1 = poly1->next;
}
if (poly2->next)
{
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next = (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}

// Display Linked list

void show(struct Node* node)
{
while (node->next != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->coeff >= 0)
{
if (node->next != NULL)
printf("+");
}
}
}

// Driver code
int main()
{
struct Node *poly1 = NULL,
*poly2 = NULL,
 *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0
create_node(5, 2, &poly1);
create_node(4, 1, &poly1);
create_node(2, 0, &poly1);
// Create second list of -5x^1 - 5x^0
create_node(-5, 1, &poly2);
create_node(-5, 0, &poly2);
printf("1st Number: ");
show(poly1);
printf("2nd Number: ");
show(poly2);
poly = (struct Node*)malloc(sizeof(struct Node));
// Function add two polynomial // numbers
polyadd(poly1, poly2, poly);

// Display resultant List

printf("Added polynomial: ");
show(poly);
return 0;
}
Output:
1st Number: 5x^2+4x^1+2x^0
2nd Number: -5x^1-5x^0
Added polynomial: 5x^2-1x^1-3x^0

Additional Resources
1. [Link]
2. [Link]
using-linked-list/
3. [Link] -strudtures/
4. [Link]
Practice Questions:
1. Define data, Information.
2. Define data structure.
3. What are the operations we can do in data structure?
4. What do you mean by non-linear data structure? Give example.
5. What do you linear data structure? Give example.
6. List the various operations that can be performed on data structure.
7. What is abstract data type?
8. Explain Features of ADT.
9. What is a linked list?
10. Define doubly linked list.
11. Difference between arrays and lists.
12. Write a program to implement list based on array.
13. What are the types of Linked List?
14. State the advantages of circular lists over doubly linked list.
15. What are the advantages of doubly linked list over singly linked list?
16. Why is the linked list used for polynomial arithmetic?
17. What is the advantage of linked list over arrays?
18. What is the circular linked list?
19. What is the advantage of an ADT?
20. Define Node.
21. What are the different types of data structure?
22. Write a program to implement singly linked list using c++.
23. Write a program to implement Doubly linked list using c++.
24. Write a program to implement Circular linked list using c++.
25. Explain Polynomial Manipulation.
 MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS)
VANIYAMBADI
PG and Department of Computer Applications
st
1 B.C.A – Semester - II

E-Notes (Study Material)

Core Course -1: Data Structure Code:24UCAC21

Unit: 2 - Stack ADT-Operations- Applications- Evaluating arithmetic expressions –

Conversion of infix to postfix expression-Queue ADT-Operations-Circular Queue-
Priority Queue- deque applications of queues.
Learning Objectives: Students will learn the basic concepts of stacks and queues
as abstract data types, including their core operations like push/pop (stack) and
enqueue/dequeue (queue).
Course Outcomes: Understand the implementation of Stacks and Queues using Arrays and
their applications.

Overview
- Stack ADT Operations and Applications
- Evaluating arithmetic expressions
- Conversion of infix to postfix expression
- Queue ADT-Operations
- Circular Queue
- Priority Queue
- deQueue
- Applications of queues.
STACK
√Stack is a Linear Data Structure that follows Last In First Out (LIFO) principle.
√Insertion and deletion can be done at only one end of the stack called TOP of
the stack.
STACK ADT:

TOP pointer
- It will always point to the last element inserted in the stack.
- For empty stack, top will be pointing to -1. (TOP = -1)
Implementation of Stack
Stack can be implemented in 2 ways.
1. Static Implementation (Array implementation of Stack)
2. Dynamic Implementation (Linked List Implementation of Stack)
1. Implement Stack using Array:
To implement a stack using an array, initialize an array and treat its end as the
stack’s top. Implement push (add to end), pop (remove from end), and peek (check
end) operations, handling cases for an empty or full stack.
Operations on Stack (Stack ADT)
Basic operations performed on the stack are:
1. Push Operation on Stack: Adds an item to the stack. If the stack is full, then
it is said to be an Overflow condition.
1. Push :
√ Before pushing the element to the stack, we check if the stack is full .
√ If the stack is full (top == size-1) , then Stack Overflows and we cannot
insert the element to the stack.
√ Otherwise, we increment the value of top by 1 (top = top + 1) and the new
value is inserted at top position .
√ The elements can be pushed into the stack till we reach the capacity of the
stack.

void push(int x)
{
top++;
arr[top] = x;
}

2. Pop: Removes an item from the stack. The items are popped in the
reversed order in which they are pushed. If the stack is empty, then it is said
to be an Underflow condition.
Pop Operation:
√ Before popping the element from the stack, we check if the stack is
empty .
√ If the stack is empty (top == -1), then Stack Underflows and we cannot
remove any element from the stack.
√ Otherwise, we store the value at top, decrement the value of top by 1
(top = top – 1) and return the stored top value.
 int pop()
{
int x = arr[top];
top--;
return x;
}
3. Top or Peek : Returns the top element of the stack.
Top Operation:
√ Before returning the top element from the stack, we check if the stack is
empty.
√ If the stack is empty (top == -1), we simply print “Stack is empty”.
√ Otherwise, we return the element stored at index = top.

int Top()
{
return arr[top];
}
 4. isEmpty: Returns true if the stack is empty, else false.
isEmpty Operation:
√ Check for the value of top in stack.
√ If (top == -1), then the stack is empty so return true .
√ Otherwise, the stack is not empty so return false.

int isempty()
{
If(arr[top]==-1)
return 1;
else
return 0;
}
5. isFull: Returns true if the stack is full, else false.
isFull Operation:
√ Check for the value of top in stack.
√

If (top == size-1), then the stack is

full so return true.
√ Otherwise, the stack is not full so return false.
int isfull()
 {
If(arr[top] >= size-1)
return 1;
else
return 0;
}
6. Size():method is used to find the number of elements in the stack. This
function does not take any parameters. Returns the number of element
present in the stack container.
int Size()
{
return top + 1;
}
Write a C++ program to implement Stack using array
#include <iostream>
using namespace std;
int arr[100], n=100, top=-1;
void push(int x)
{
top++;
arr[top] = x;
cout<arr[top];
cout<<”\t”;
}
void display()
{
for(int i=0; i<=top;i++)
{
cout<arr[i];
cout<”\t”;
}
}
int pop()
{
 int x = arr[top];
top--;
return x;
}

int Top()
{
return arr[top];
}
int Size()
{
return top + 1;
}
int main()
{
push(6);
push(3);
push(7);
cout << "Elements of the stack is :" << endl;
display();
cout << "Top of stack is before deleting any element " << [Link]() << endl;
cout << "Size of stack before deleting any element " << [Link]() << endl;
cout << "The element deleted is " << [Link]() << endl;
cout << "Size of stack after deleting an element " << [Link]() << endl;
cout << "Top of stack after deleting an element " << [Link]() << endl;
return 0;
}
OUTPUT:
Elements of the stack is : 6 3 7
Top of stack is before deleting any element 7
Size of stack before deleting any element 3
The element deleted is 7
Size of stack after deleting an element 2
Top of stack after deleting an element 3

2. Implement Stack using Linked List:

To implement a stack using the singly linked list concept, all the singly linked list
operations should be performed based on Stack operations LIFO(last in first out)
and with the help of that knowledge, we are going to implement a stack using a
singly linked list.
In the stack Implementation, a stack contains a top pointer. which is the “head” of
the stack where pushing and popping items happens at the head of the list. The
first node has a null in the link field and second node-link has the first node address
in the link field and so on and the last node address is in the “top” pointer.
Advantage of using a linked list over arrays is that it is possible to implement a
stack that can shrink or grow as much as needed. Using an array will put a
restriction on the maximum capacity of the array which can lead to stack overflow.
Here each new node will be dynamically allocated. so overflow is not possible.

Stack Operations:
1. push(): Insert a new element into the stack i.e just insert a new element at
the beginning of the linked list.
2. pop(): Return the top element of the Stack i.e simply delete the first element
from the linked list.
3. peek(): Return the top element.
4. display(): Print all elements in Stack.
1. Push Operation:
√ Initialise a node
 √ Update the value of that node by data i.e. node->data = data
√ Now link this node to the top of the linked list
√ And update top pointer to the current node
2. Pop Operation:
√ First Check whether there is any node present in the linked list or not, if
not then return
√ Otherwise make pointer let say temp to the top node and move forward
the top node by 1 step
√ Now free this temp node
3. Peek Operation:
√ Check if there is any node present or not, if not then return.
√ Otherwise return the value of top node of the linked list
4. Display Operation:
√ Take a temp node and initialize it with top pointer
√ Now start traversing temp till it encounters NULL
√ Simultaneously print the value of the temp node
Write C++ program to implement stack using Linked list
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
node* next;
};
struct node* head = NULL;
void push(int x)
{
node* temp;
temp = new node();
temp->data = x;
temp->next = head;
head = temp;
}
bool isEmpty()
{
if (head == NULL)
return true;
else
return false;
}
int top_element()
{

if (head == NULL)
{
cout << "stack is empty" << endl;
}
else
return head->data;
}
void pop()
{
node* temp;
if (isEmpty())
{
cout << "stack is empty" << endl;
}
else
{
temp = head;
head = head->next;
delete(temp);
}
}
void print_stack()
{
struct node* curr;
 if (isEmpty())
{
cout << "stack is empty" << endl;
}
else
{
curr = head;
cout << "Elements are: ";
while (curr != NULL)
{
cout << curr->data << " ";
curr = curr->next;
}
cout << endl;
}
}
int main()
{
push(5);
push(3);
push(6);
print_stack();
isEmpty();
cout << "Top: "
<< top_element() << endl;
pop();
print_stack();
cout << "Top: "
<< top_element() << endl;
return 0;
}
OUTPUT:
Elements are: 6 3 5
Top: 6
Elements are: 3 5
Top: 3
Benifits of Linked List Stack in C++
The following are the major benifits of the linked list implementation over the array
implementation:
√ The dynamic memory management of linked list provide dynamic size to
the stack that changes with the change in the number of elements.
√ Rarely reaches the condition of the stack overflow.
APPLICATIONS of STACK
1. Reversing a list
2. Parentheses Checking
3. Conversion of an infix expression into a postfix expression
4. Evaluation of a postfix expression
5. Conversion of an infix expression into a prefix expression
6. Evaluation of a prefix expression
7. Recursion
Evaluation of Arithmetic Expressions
The stack organization is very effective in evaluating arithmetic expressions.
Arithmetic expressions can be represented in 3 forms:
√ Infix Expression: Operators are written between the operands they operate
on,
E.g. A + B.
√ Postfix Expression: Operators are written after operands. E.g A B +
√ Prefix Expression: Operators are written before the operands, E.g + A B
Conversion of Infix to Postfix expression
● An infix and postfix are the expressions. An expression consists of
constants, variables, and symbols. Symbols can be operators or parenthesis.
●

All these
components must be arranged according to a set of rules so that all these
expressions can be evaluated using the set of rules.
In the algebraic expression, the order of the operator precedence is given in the
below table:
The first preference is given to the parenthesis; then next preference is given to the
exponents. In the case of multiple exponent operators, then the operation will be
applied from right to left.

Write a program to convert an Infix expression to Postfix form.

Infix expression: The expression of the form “a operator b” (a + b) i.e., when an
operator is in-between every pair of operands.
Postfix expression: The expression of the form “a b operator” (ab+) i.e., When every
pair of operands is followed by an operator.
Examples:
1. Input: A + B * C + D
Output: ABC*+D+
2. Input: A + B * C
= A + (BC*)
Output: ABC*+
Approach: To convert Infix expression to Postfix
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, Print it.
3. Else,
● If the precedence of the scanned operator is greater than the precedence of
the operator in the stack or the stack is empty or the stack contains a ‘(‘,
push the character into the stack.
● Else, Pop all the operators from the stack which are greater than or equal to
in precedence than that of the scanned operator. After doing that Push the
scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it into the stack.
5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is
encountered, and discard both the parenthesis.
6. Repeat steps 2-5 until the entire infix expression is scanned.
7. Print the output.
8. Pop and print the output from the stack until it is not empty.
Example:

Infix
expression: K + L - M*N + (O^P) * W/U/V * T + Q
The final postfix expression of infix expression(K + L - M*N + (O^P) * W/U/V * T + Q) is
KL+MN*-OP^W*U/V/T*+Q+.

Write a C++ program to convert infix expression to postfix expression

// C++ Program to illustrate how to use a stack to convert an infix expression to a
postfix expression
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int precedence(char op)
{
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
}
string infixToPostfix(string infix)
{
stack<char> st;
string postfix = "";
for (int i = 0; i < infi[Link](); i++) {
char c = infix[i];
if (isalnum(c))
postfix += c;
else if (c == '(')
[Link]('(');
else if (c == ')')
{
while ([Link]() != '(')
{
postfix += [Link]();
[Link]();
}
[Link]();
}
else
{
while (![Link]()&& precedence(c)<= precedence([Link]()))
{
postfix += [Link]();
[Link]();
 }
[Link](c);
}
}
while (![Link]())
{
postfix += [Link]();
[Link]();
}
return postfix;
}
int main()
{
string infix = "A+B*C";
cout << "Infix Expression: " << infix << endl;
cout << "Postfix Expression: " << infixToPostfix(infix)
<< endl;
return 0;
}
Output
Infix Expression: A+B*C
Postfix Expression: ABC*+

QUEUE
Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first
element inserted is the first to be popped out.

FIFO Principle states that the first element added to the Queue will be the first one to be
removed or processed. So, Queue is like a line of people waiting to purchase tickets, where
the first person in line is the first person served. (i.e. First Come First Serve).
Basic Terminologies of Queue
● Front: Position of the entry in a queue ready to be served, that is, the first
entry that will be removed from the queue, is called the front of the queue. It
is also referred as the head of the queue.
● Rear: Position of the last entry in the queue, that is, the one most recently
added, is called the rear of the queue. It is also referred as the tail of the
queue.
● Size: Size refers to the current number of elements in the queue.
● Capacity: Capacity refers to the maximum number of elements the queue
can hold.
Representation of Queue
Operations on Queue
1. Enqueue: Enqueue operation adds (or stores) an element to the end of the
queue.
Steps:
√ Check if the queue is full. If so, return an overflow error and exit.
√ If the queue is not full, increment the rear pointer to the next available
position.
√

Insert the element at the rear.

2. Dequeue: Dequeue operation removes the element at the front of the queue.
The following steps are taken to perform the dequeue operation:
√ Check if the queue is empty. If so, return an underflow error.
√ Remove the element at the front.
√ Increment the front pointer to the next element.
 3. Peek or Front Operation: This operation returns the element at the front end
without removing it.
4. Size Operation: This operation returns the numbers of elements present in
the queue.
5. isEmpty Operation: This operation returns a boolean value that indicates
whether the queue is empty or not.
6. isFull Operation: This operation returns a boolean value that indicates
whether the queue is full or not.

Implementation of Queue Data Structure

Queue can be implemented using following data structures:
1. Implementation of Queue using Arrays
2. Implementation of Queue using Linked List
[Link] of Queue using Arrays
Basic Operations on Queue:
√ enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
√ dequeue(): This operation removes and returns an element that is at the
 front end of the queue.
√ front(): This operation returns the element at the front end without
removing it.
√ rear(): This operation returns the element at the rear end without removing
it.
√ isEmpty(): This operation indicates whether the queue is empty or not.
√ isFull(): This operation indicates whether the queue is full or not.
√ size(): This operation returns the size of the queue i.e. the total number of
elements it contains.
Steps for enqueue:
√ Check the queue is full or not
√ If full, print “Queue is full” and exit.
√ If the queue is not full
1. Add the new element at the index front + size (this is the rear of the
queue).
2. Increment the size of the queue by 1 (i.e., size++).
Steps for dequeue:
√ Check queue is empty or not
√ If empty, print “Queue is empty” and exit
√ If the queue is not empty:
1. Print and return the front element (which is queue[front]).
2. Shift all elements in the queue to the left by one position (i.e., move each
element queue[i] to queue[i - 1] for i from 1 to size - 1).
3. Decrement the size by 1 (i.e., size--).
Write C++ program to implement Queue using array
#include<iostream>
#define SIZE 10

void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main()
{
 int value, choice;
clrscr();
while(1)
{
cout<<"\n\n***** MENU *****\n";
cout<<"1. Insertion\n2. Deletion\n3. Display\n4. Exit";
cout<<"\nEnter your choice: ";
cin>>choice;
switch(choice)
{
case 1: cout<<”Enter the value to be insert: ";
cin>>value;
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default:cout<<”\nWrong selection!!! Try again!!!";
}
}
}
void enQueue(int value)
{
if(rear == SIZE-1)
cout<<"\nQueue is Full!!! Insertion is not possible!!!";
else
{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
 cout<<"\nInsertion success!!!";
}
}
void deQueue()
{
if(front == rear)
cout<<”\nQueue is Empty!!! Deletion is not possible!!!";
else{
cout<<"\nDeleted : ", queue[front];
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
cout<<"\nQueue is Empty!!!";
else
{
int i;
cout<<”\nQueue elements are:\n";
for(i=front; i<=rear; i++)
cout<<"\t",queue[i];
}
}
 OUTPUT

[Link] of Queue using Linked List

The major problem with the queue implemented using an array is, It will work for
an only fixed number of data values,the amount of data must be specified at the
beginning itself.
Queue using an array is not suitable when we don't know the size of data which we
are going to use.
A queue data structure can be implemented using a linked list data structure. The
queue which is implemented using a linked list can work for an unlimited number
of values. That means, queue using linked list can work for the variable size of data
(No need to fix the size at the beginning of the implementation).
Example: Queue using linked list
In the example, the last inserted node is 50 and it is pointed by 'rear' and the first
inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10,
15, 22 and 50.
Operations
To implement queue using linked list, we need to set the following things before
implementing actual operations.
√ Step 1 - Include all the header files which are used in the program. And
declare all the user defined functions.
√ Step 2 - Define a 'Node' structure with two members data and next.
√ Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
√ Step 4 - Implement the main method by displaying Menu of list of
operations and make suitable function calls in the main method to perform
user selected operation.
1. enQueue(value) - Inserting an element into the Queue
We can use the following steps to insert a new node into the queue...
√ Step 1 - Create a newNode with given value and set 'newNode next'
to NULL.
√ Step 2 - Check whether queue is Empty (rear == NULL)
√ Step 3 - If it is Empty then, set front = newNode and rear = newNode.
√ Step 4 - If it is Not Empty then, set rear next = newNode and rear =
newNode.
2. deQueue() - Deleting an Element from Queue
We can use the following steps to delete a node from the queue...
√ Step 1 - Check whether queue is Empty (front == NULL).
√ Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not
possible!!!" and terminate from the function
√ Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to
'front'.
√ Step 4 - Then set 'front = front next' and delete 'temp' (free(temp)).
3. display() - Displaying the elements of Queue
We can use the following steps to display the elements (nodes) of a queue...
√ Step 1 - Check whether queue is Empty (front == NULL).
√ Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the
function.
 √ Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize
with front.
√ Step 4 - Display 'temp data --->' and move it to the next node. Repeat
the same until 'temp' reaches to 'rear' (temp next != NULL).
√ Step 5 - Finally! Display 'temp data ---> NULL'.
Implementation of Queue using Linked List – C++ Programming
#include<iostream>
struct Node
{
int data;
struct Node *next;
}*front = NULL,*rear = NULL;
void insert(int);
void delete();
void display();

void main()
{
int choice, value;
clrscr();
cout<<"\n:: Queue Implementation using Linked List ::\n";
while(1)
{
cout<<"\n****** MENU ******\n";
cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n";
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1: cout<<"Enter the value to be insert: ";
cin>>value;
insert(value);
break;
case 2: delete(); break;
 case 3: display(); break;
case 4: exit(0);
default: cout<<"\nWrong selection!!! Please try again!!!\n";
}
}
}
void insert(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;
else{
rear -> next = newNode;
rear = newNode;
}
cout<<"\nInsertion is Success!!!\n";
}
void delete()
{
if(front == NULL)
cout<<"\nQueue is Empty!!!\n";
else
{
struct Node *temp = front;
front = front -> next;
cout<<"\nDeleted element: %d\n", temp->data;
free(temp);
}
}
void display()
{
if(front == NULL)
cout<<"\nQueue is Empty!!!\n";
else{
struct Node *temp = front;
while(temp->next != NULL){
cout<< temp->data <<"--->";
temp = temp -> next;
}
cout<< temp->data <<"--->NULL\n",;
}
}

OUTPUT

Types of Queues
Queue data structure can be classified into 4 types:
1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only
insert the element at the back and remove the element from the front of the
 queue.
2. Double-Ended Queue (Deque): In a double-ended queue the insertion and
deletion operations, both can be performed from both ends. They are of two
types:
√ Input Restricted Queue: This is a simple queue. In this type of queue, the
input can be taken from only one end but deletion can be done from
any of the ends.
√ Output Restricted Queue: This is also a simple queue. In this type of
queue, the input can be taken from both ends but deletion can be done
from only one end.
3. Circular Queue: This is a special type of queue where the last position is
connected back to the first position. Here also the operations are performed
in FIFO order.
4. Priority Queue: A priority queue is a special queue where the elements are
accessed based on the priority assigned to them. They are of two types:
√ Ascending Priority Queue: In Ascending Priority Queue, the elements are
arranged in increasing order of their priority values. Element with
smallest priority value is popped first.
√ Descending Priority Queue: In Descending Priority Queue, the elements
are arranged in decreasing order of their priority values. Element with
largest priority is popped first.
Circular Queue
In a normal Queue Data Structure, we can insert elements until queue becomes
full. But once the queue becomes full, we cannot insert the next element until all
the elements are deleted from the queue. For example, consider the queue below...
The queue after inserting all the elements into it is as follows...

Now consider the following situation after deleting three elements from the queue...
This situation also says that Queue is Full and we cannot insert the new element because
'rear' is still at last position. In the above situation, even though we have empty positions in
the queue we can not make use of them to insert the new element. This is the major problem
in a normal queue data structure. To overcome this problem we use a circular queue data
structure.
What is Circular Queue?
A Circular Queue can be defined as follows...
A circular queue is a linear data structure in which the operations are performed based on
FIFO (First In First Out) principle and the last position is connected back to the first position
to make a circle.

Graphical representation of a circular queue is as follows...

The circular queue work as follows:
√ two pointers FRONT and REAR
√ FRONT track the first element of the queue
√ REAR track the last elements of the queue
√ initially, set value of FRONT and REAR to -1
1. Enqueue Operation
√ check if the queue is full
√ for the first element, set value of FRONT to 0
√ circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would
be at the start of the queue)
√ add the new element in the position pointed to by REAR
2. Dequeue Operation
√ check if the queue is empty
√ return the value pointed by FRONT
√ circularly increase the FRONT index by 1
√ for the last element, reset the values of FRONT and REAR to -1
Implementation of Circular Queue
Circular Queue can be implemented using following data structures:
1. Implementation of Circular Queue using Arrays
2. Implementation of Circular Queue using Linked List
[Link] of Circular Queue using Arrays
Operations
 √ Front : From where nodes are to be popped out.
√ Back : Back or Rear, where nodes are pushed into.
√ Enqueue : Pushing a new node at the back.
√ Dequeue : Popping out nodes from front, if any.
√ Overflow : If the Circular Queue has predefined storage and is full.
√ Underflow : If the Circular Queue is empty.
√ Size : Number of nodes present.
Implementation of Circular Queue using array – C++ Programming
//Circular queue C++ program
#include<iostream>
#define MAX_SIZE 100 // Maximum size of the queue
using namespace std;
class CircularQueue
{
private:
int front, rear;
int arr[MAX_SIZE];
public:
CircularQueue ()
{
front = -1;
rear = -1;
}
bool isFull ()
{
if ((front == 0 && rear == MAX_SIZE - 1) || (rear == (front - 1) % (MAX_SIZE - 1)))
{
return true;
}
return false;
}
bool isEmpty ()
{
if (front == -1)
{
return true;
 }
return false;
}
void enQueue (int value)
{
if (isFull ())
{
cout << "Queue is full." << endl;
}
else
{
if (front == -1)
{
front = 0;
}
rear = (rear + 1) % MAX_SIZE;
arr[rear] = value;
cout << "Enqueued element: " << value << endl;
}
}
int deQueue ()
{
int element;
if (isEmpty ())
{
cout << "Queue is empty." << endl;
return -1;
}
else
{
element = arr[front];
if (front == rear)
{
front = -1;
rear = -1;
}
else
{
front = (front + 1) % MAX_SIZE;
}
cout << "Dequeued element: " << element << endl;
return element;
}
}
void display ()
{
if (isEmpty ())
{
cout << "Queue is empty." << endl;
}
else
{
cout << "Elements in the queue: ";
int i;
for (i = front; i != rear; i = (i + 1) % MAX_SIZE)
{
cout << arr[i] << " ";
}
cout << arr[i] << endl;
}
}
};

int main ()
{
CircularQueue q;
[Link] (10);
[Link] (20);
[Link] (30);
[Link] (40);
[Link] ();
[Link] ();
 [Link] ();
[Link] ();
[Link] (50);
[Link] (60);
[Link] ();
return 0;
}
Output:
Enqueued element: 10
Enqueued element: 20
Enqueued element: 30
Enqueued element: 40
Elements in the queue: 10 20 30 40
Dequeued element: 10
Dequeued element: 20
Elements in the queue: 30 40
Enqueued element: 50
Enqueued element: 60
Elements in the queue: 30 40 50 60

[Link] of Circular Queue using Linked list

Operations:
√Front(): return the front node’s value if not null. Otherwise return -1.
√Rear(): return the rear node’s value if not null. Otherwise return -1.
√EnQueue(int value): Create a new node and set its value. If front is null, then set front = rear =
newNode. Otherwise, set tail->next = newNode, tail = newNode, tail->next = front.
√DeQueue(): If list is empty, return -1. Otherwise get the front node’s value and remove it from
the list. If the list contains only one node, then set front = rear = null. Otherwise update head
= head->next and rear->next = head.
Circular queue C++ program using Linked list
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
class CircularQueue
{
private:
Node * front;
Node *rear;
public:
CircularQueue ()
{
front = rear = nullptr;
}

void enqueue (int data)

{
Node *newNode = new Node ();
newNode->data = data;
newNode->next = nullptr;
if (front == nullptr)
{
front = rear = newNode;
rear->next = front;
}
else
{
rear->next = newNode;
rear = newNode;
rear->next = front;
}
cout << data << " has been enqueued." << endl;
}
void dequeue ()
{
if (front == nullptr)
{
cout << "Queue is empty." << endl;
}
else if (front == rear)
{
Node *temp = front;
front = rear = nullptr;
delete temp;
}
else
{
Node *temp = front;
front = front->next;
rear->next = front;
delete temp;
}
 }
void display ()
{
if (front == nullptr)
{
cout << "Queue is empty." << endl;
}
else
{
Node *temp = front;
cout << "Circular Queue: ";
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != front);
cout << endl;
}
}
};
int main ()
{
CircularQueue q;
[Link] (10);
[Link] (20);
[Link] (30);
[Link] (40);
[Link] ();
[Link] ();
[Link] ();
[Link] ();
[Link] (50);
[Link] (60);
[Link] ();
return 0;
 }
Output:
10 has been enqueued.
20 has been enqueued.
30 has been enqueued.
40 has been enqueued.
Circular Queue: 10 20 30 40
Circular Queue: 30 40
50 has been enqueued.
60 has been enqueued.
Circular Queue: 30 40 50 60
Applications of Circular Queue
√ Buffer in Computer Systems: Computer systems supply a holding area for
maintaining communication between two processes, two programs, or even two
systems. This memory area is also known as a ring buffer.
√ CPU Scheduling: In the Round-Robin Scheduling Algorithm, a circular queue is
utilized to maintain processes that are in a ready state.
√ Traffic System: Circular queue is also utilized in traffic systems that are controlled by
computers. Each traffic light turns ON in a circular incrementation pattern in a
constant interval of time.

Priority Queue:
What is a priority queue?
A priority queue is an abstract data type that behaves similarly to the normal queue
except that each element has some priority, i.e., the element with the highest priority would
come first in a priority queue. The priority of the elements in a priority queue will determine
the order in which elements are removed from the priority queue.
Characteristics of a Priority queue
A priority queue is an extension of a queue that contains the following characteristics:
√ Every element in a priority queue has some priority associated with it.
√ An element with the higher priority will be deleted before the deletion of the lesser
priority.
√ If two elements in a priority queue have the same priority, they will be arranged using
the FIFO principle.
Example:
The hospital emergency queue is an ideal real-life example of a priority queue. In this queue
 of patients, the patient with the most critical situation is the first in a queue, and the patient
who doesn’t need immediate medical attention will be the last. In this queue, the priority
depends on the medical condition of the patients.

Implementation of Priority Queue

Priority queue can be implemented using an array, a linked list, a heap data structure, or a
binary search tree. Among these data structures, heap data structure provides an efficient
implementation of priority queues.
Priority Queue Applications
Some of the applications of a priority queue are:
√ Dijkstra's algorithm
√ for implementing stack
√ for load balancing and interrupt handling in an operating system
√ for data compression in Huffman code

Types of Priority Queue

There are two types of priority queues based on the priority of elements.
√If the element with the smallest value has the highest priority, then that priority queue is called
the min priority queue.
√If the element with a higher value has the highest priority, then that priority queue is known as
 the max priority queue.
√Furthermore, you can implement the min priority queue using a min heap, whereas you can
implement the max priority queue using a max heap.
Priority Queue Operations
√Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item according to its
order. Here we're assuming that data with high value has low priority.
√Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using item count.
Once element is removed. Item count is reduced by one.
√Peek in a Priority Queue
This operation helps to return the maximum element from Max Heap or the minimum
element from Min Heap without deleting the node from the priority queue.
Difference between Priority Queue and Normal Queue?
There is no priority attached to elements in a queue, the rule of first-in-first-out(FIFO) is
implemented whereas, in a priority queue, the elements have a priority. The elements with higher
priority are served first.
Double Ended Queue (De-Queue):
Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert
and delete at both ends.
Operations on Deque: Below is a table showing some basic operations along with their time
complexity, performed on deques.

Operation Description
push_front() Inserts the element at the beginning.
push_back() Adds element at the end.
pop_front() Removes the first element from the deque.
pop_back() Removes the last element from the deque.
front() Gets the front element from the deque.
back() Gets the last element from the deque.
empty() Checks whether the deque is empty or not.
size() Determines the number of elements in the deque.

Applications of Deque Data Structure

√In undo operations on software.
√To store history in browsers.
√For implementing both stacks and queues.
Implementation of Circular Queue
De-Queue can be implemented using following data structures:
 1. Implementation of De-Queue using Arrays
2. Implementation of De-Queue using Linked List
Implementation of De-Queue using Arrays
#include <iostream>
using namespace std;
#define MAX 100
class Deque
{
int arr[MAX];
int front;
int rear;
int size;
public:
Deque(int size)
{
front = -1;
rear = 0;
this->size = size;
}
void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();
};
bool Deque::isFull()
{
return ((front == 0 && rear == size - 1)
|| front == rear + 1);
}
bool Deque::isEmpty()
{
return (front == -1);
}
void Deque::insertfront(int key)
{
if (isFull())
{
cout << "Overflow\n" << endl;
return;
}
if (front == -1)
{
front = 0;
rear = 0;
}
else if (front == 0)
front = size - 1;
else
front = front - 1;
arr[front] = key;
}
void Deque ::insertrear(int key)
{
if (isFull())
{
cout << " Overflow\n " << endl;
return;
}
if (front == -1)
{
front = 0;
rear = 0;
}
else if (rear == size - 1)
rear = 0;
else
rear = rear + 1;
arr[rear] = key;
}
void Deque ::deletefront()
{
if (isEmpty())
{
cout << "Queue Underflow\n" << endl;
return;
}
if (front == rear)
{
front = -1;
rear = -1;
}
else
if (front == size - 1)
front = 0;
else
front = front + 1;
}
void Deque::deleterear()
{
if (isEmpty())
{
cout << " Underflow\n" << endl;
return;
}
if (front == rear)
 {
front = -1;
rear = -1;
}
else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
int Deque::getFront()
{
if (isEmpty())
{
cout << " Underflow\n" << endl;
return -1;
}
return arr[front];
}

int Deque::getRear()
{
// check whether Deque is empty or not
if (isEmpty() || rear < 0) {
cout << " Underflow\n" << endl;
return -1;
}
return arr[rear];
}
int main()
{
Deque dq(5);
cout << "Insert element at rear end : 5 \n";
[Link](5);
 cout << "insert element at rear end : 10 \n";
[Link](10);
cout << "get rear element "<< " " << [Link]() << endl;
[Link]();
cout << "After delete rear element new rear"<< " become " << [Link]() << endl;
cout << "inserting element at front end \n";
[Link](15);
cout << "get front element "<< " " << [Link]() << endl;
[Link]();
cout << "After delete front element new "<< "front become " << [Link]() <<
endl;
return 0;
}
Output
Insert element at rear end : 5
insert element at rear end : 10
get rear element 10
After delete rear element new rear become 5
inserting element at front end
get front element 15
After delete front element new front become 5
Applications of Queue
√Task Scheduling: Queues can be used to schedule tasks based on priority or the order in
which they were received.
√Resource Allocation: Queues can be used to manage and allocate resources, such as printers
or CPU processing time.
√Batch Processing: Queues can be used to handle batch processing jobs, such as data
analysis or image rendering.
√Message Buffering: Queues can be used to buffer messages in communication systems, such
as message queues in messaging systems or buffers in computer networks.
√Event Handling: Queues can be used to handle events in event-driven systems, such as GUI
applications or simulation systems.
√Traffic Management: Queues can be used to manage traffic flow in transportation systems,
such as airport control systems or road networks.
√Operating systems: Operating systems often use queues to manage processes and resources.
For example, a process scheduler might use a queue to manage the order in which
processes are executed.
√Printer queues :In printing systems, queues are used to manage the order in which print jobs
 are processed. Jobs are added to the queue as they are submitted, and the printer processes
them in the order they were received.
Advantages of Queue:
√A large amount of data can be managed efficiently with ease.
√Operations such as insertion and deletion can be performed with ease as it follows the first in
first out rule.
√Queues are useful when a particular service is used by multiple consumers.
√Queues are fast in speed for data inter-process communication.
√Queues can be used in the implementation of other data structures.
Disadvantages of Queue:
√The operations such as insertion and deletion of elements from the middle are time
consuming.
√In a classical queue, a new element can only be inserted when the existing elements are
deleted from the queue.
√Searching an element takes O(N) time.
√Maximum size of a queue must be defined prior in case of array implementation.

Practice questions

Section – A

[Link]fine stack.
[Link] out the any two applications of Stack?
[Link]fine PUSH.
[Link]fine POP.
[Link]fine Infix Expression.
[Link]fine Prefix(or)Polish notation.
[Link]fine Postfix(or)Reverse Polish notation.
[Link] the postfix and prefix forms for the expression A+B*(C-D)/(P-R)?
[Link] are the types of Queue?
[Link]fine Queue.
[Link] are the operations on a Queue?
[Link] the application of Queue.
[Link] do you test for an empty Queue?
[Link]fine Circular Queue.
[Link] the advantage and disadvantages of Circular Queue.
 [Link] the applications of circular Queue.
[Link] between a Stack and a Queue.
[Link] is Priority Queue?
[Link] the advantage and disadvantages of dequeue.
[Link] are the operations that can be performed on Double ended Queue?
[Link] between Queue and Double ended Queue.
[Link] is Double ended Queue?

Section – B AND C

[Link] an algorithm to convert infix expression to postfix expression.

[Link] the concept of stack with illustrations.
[Link] the operations performed on a Stack.
[Link]fly explain the application of Stack.
[Link] the concept of Queue with illustrations.
[Link] the operations of Queue.
[Link] the applications of Queue.
[Link]fly explain circular Queue.
[Link]fly explain Queue.
[Link]fly explain priority Queue.
[Link] is a Stack?Explain any two operations on Stack with required algorithm.
[Link] the concept of Queue and also write algorithms to insert and delete an element
in a queue.
[Link] various operations available on a Queue.
[Link] is an infix expression converted to postfix [Link] the expression A+B*C+
(D*E+F)*G to postfix form.

Additional References
[Link]://[Link]/
[Link]://[Link]/
[Link]://[Link]/dsa
[Link]://[Link]/gate/difference-stack-and-queue-data-structures
 MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS)
VANIYAMBADI
PG and Department of Computer Applications
st
1 B.C.A – Semester - II
E-Notes (Study Material)

Core Course -1: Data Structure Code:24UCAC22

Unit: 3 - Tree ADT-tree traversals-Binary Tree ADT-expression trees-applications of

trees- binary search tree ADT- Heap-Applications of heap.
Learning Objectives: To learn Tree structures and application of trees
Course Outcomes: Solve problem involving in trees and heaps.

Overview

- Tree ADT-
- Tree traversals
- Binary Tree ADT
- Expression trees
- applications of trees
- binary search tree ADT
- Heap
- Applications of heap.
Tree ADT

√ A tree is a non-linear abstract data type with a hierarchy-based structure. It consists

of nodes (where the data is stored) that are connected via links. The tree data
structure stems from a single node called a root node and has subtrees connected to
the root.

√ A tree is a non-linear data structure that consists of a root node and potentially many
levels of additional nodes that form a hierarchy. A tree can be empty with no nodes
called the null or empty tree or a tree is a structure consisting of one node called the
root and one or more subtrees.

√ Tree data structure is a hierarchical structure that is used to represent and organize
data in the form of parent child relationship.

√ The topmost node of the tree is called the root, and the nodes below it are called the
child nodes. Each node can have multiple child nodes, and these child nodes can also
have their own child nodes, forming a recursive structure.

Structu
re of Tree
Why Tree is considered a non-linear data structure?

The data in a tree are not stored in a sequential manner i.e., they are not stored linearly.
Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For
this reason, the tree is considered to be a non-linear data structure.

Basic Terminologies of a Tree

1. Root

√ In a tree data structure, the root is the first node of the tree. The root node is the initial
node of the tree in data structures.
√ In the tree data structure, there must be only one root node.

2. Edge

√ In a tree in data structures, the connecting link of any two nodes is called the edge of
the tree data structure.
√ In the tree data structure, N number of nodes connecting with N -1 number of edges.
3. Parent

In the tree in data structures, the node that is the predecessor of any node is known as a
parent node, or a node with a branch from itself to any other successive node is called the
parent node.

4. Child

√The node, a descendant of any node, is known as child nodes in data structures.
√In a tree, any number of parent nodes can have any number of child nodes.
√In a tree, every node except the root node is a child node.
5. Siblings

In trees in the data structure, nodes that belong to the same parent are called siblings.

6. Leaf

√ Trees in the data structure, the node with no child, is known as a leaf node.
√ In trees, leaf nodes are also called external nodes or terminal nodes.

7. Internal nodes

√ Trees in the data structure have at least one child node known as internal nodes.
√ In trees, nodes other than leaf nodes are internal nodes.
√ Sometimes root nodes are also called internal nodes if the tree has more than one
node.
8. Degree

√ In the tree data structure, the total number of children of a node is called the degree
of the node.
√ The highest degree of the node among all the nodes in a tree is called the Degree of
Tree.

9. Level

√ In tree data structures, the root node is said to be at level 0, and the root node's
children are at level 1, and the children of that node at level 1 will be level 2, and so on.
10. Height

√ In a tree data structure, the number of edges from the leaf node to the particular node
in the longest path is known as the height of that node.
√ In the tree, the height of the root node is called "Height of Tree".
√ The tree height of all leaf nodes is 0.

[Link]

√ In a tree, many edges from the root node to the particular node are called the depth of
the tree.
√ In the tree, the total number of edges from the root node to the leaf node in the
longest path is known as "Depth of Tree".
√ In the tree data structures, the depth of the root node is 0.
12. Path

√ In the tree in data structures, the sequence of nodes and edges from one node to
another node is called the path between those two nodes.
√

The length of a path is the total number

of nodes in a path. zx

13. Subtree

√ In the tree in data structures, each child from a node shapes a sub-tree recursively
and every child in the tree will form a sub-tree on its parent node.
Types of Tree in Data Structures

Here are the different kinds of tree in data structures:

1. Binary Tree

A binary tree has the following properties:

Properties

√ Follows all properties of the tree data structure.

√ Binary trees can have at most two child nodes.
√ These two children are called the left child and the right child.
2. Binary Search Tree

A binary search tree is a type of tree that is a more constricted extension of a binary tree data
structure.

Properties
√ Follows all properties of the tree data structure.

√ The binary search tree has a unique property known as the binary search property.
This states that the value of a left child node of the tree should be less than or equal
to the parent node value of the tree. And the value of the right child node should be
greater than or equal to the parent value.

3. Expression Tree
[Link]

The expression tree is a binary tree in which each internal node corresponds to the operator
and each leaf node corresponds to the operand so for example expression tree for 3 +
((5+9)*2) would be:
Binary Tree

Binary Tree is a non-linear and hierarchical

data structure where each node has at most two children referred to as the left child and the right
child. The topmost node in a binary tree is called the root, and the bottom-most nodes are called
leaves.

Representation of Binary Tree

Each node in a Binary Tree has three parts:

 √ Data
√ Pointer to the left child
√ Pointer to the right child

Create/Declare a Node of a Binary Tree

Syntax to declare a Node of Binary Tree

struct Node
{
int data;
Node * left, * right;
};

Types of Binary Tree

1. Complete Binary Tree

2. Left and Right Skewed Binary Tree
3. Strictly Binary Tree
4. Extended Binary Tree

1. Complete Binary Tree

What is a Complete Binary Tree?

A complete binary tree is a special type of binary tree where all the levels of the tree are filled
completely except the lowest level nodes which are filled from as left as possible.
 h
For a given height h, the maximum number of nodes is 2 +1-1.

A complete binary tree of height h is a perfect binary tree up to height h-1, and in the last level
element are stored in left to right order.

Example 1:
The height of the given binary tree is 2 and the maximum number of nodes in that tree is
h+1
n= 2
2+1
n=2 -1
3
n= 2 -1 = 7.

2. Skewed Binary Tree

A skewed binary tree is a type of binary tree in which all the nodes have only either one child
or no child.

Types of Skewed Binary trees

There are 2 special types of skewed tree:

1. Left Skewed Binary Tree:

These are those skewed binary trees in which all the nodes are having a left child or no child
at all. It is a left side dominated tree. All the right children remain as null.

2. Right Skewed Binary Tree:

These are those skewed binary trees in which all the nodes are having a right child or no child
at all. It is a right side dominated tree. All the left children remain as null.
 3. Strictly Binary Tree

A complete binary tree is another name for the strict binary tree. Only if each node has either
0 or 2 offspring can the tree be regarded as strict binary tree. The term "strict binary tree" can
also refer to a tree where all nodes, save the leaf nodes, must have two children.

4. Extended Binary Tree

Extended binary tree is a type of binary tree in which all the

null sub tree of the original tree are replaced with special nodes called external nodes
whereas other nodes are called internal nodes

Representation of Binary Trees

There are two primary ways to represent binary trees:

1. Linked Node Representation

2. Array Representation

Array representation of a binary tree

Array Representation is another way to represent binary trees, especially useful when the tree
is complete (all levels are fully filled except possibly the last, which is filled from left to right).
In this method:
 √ The tree is stored in an array.
√ For any node at index i:
● Left Child: Located at 2 * i + 1
● Right Child: Located at 2 * i + 2
√

Root Node: Stored at index 0

Advantages:

● Easy to navigate parent and child nodes using index calculations, which is fast
● Easier to implement, especially for complete binary trees.
Disadvantages:

● You have to set a size in advance, which can lead to wasted space.
● If the tree is not complete binary tree then then many slots in the array might be
empty, this will result in wasting memory.
● Not as flexible as linked representations for dynamic trees.
Linked representation of a binary tree

This is the simplest way to represent a binary tree. Each node contains data and pointers to its left
and right children.

This representation is mostly used to represent binary

tree with multiple advantages. The most common advantages are given below.
Advantages:
● It can easily grow or shrink as needed, so it uses only the memory it needs.
● Adding or removing nodes is straightforward and requires only pointer adjustments.
● Only uses memory for the nodes that exist, making it efficient for sparse trees.
Disadvantages:
● Needs extra memory for pointers.
● Finding a node can take longer because you have to start from the root and follow
pointers.

Create/Declare a Node of a Binary Tree:

Syntax to declare a node of "linked list representation of binary tree”
struct Node
{

int data;
Node* left, * right;
Node(int val)
{
 data = val;
left = nullptr;
right = nullptr;
}
};

Binary Search Tree

A binary search tree follows some order to arrange the elements. In a Binary search tree, the value of
left node must be smaller than the parent node, and the value of right node must be greater than the
parent node. This rule is applied recursively to the left and right subtrees of the root.
Binary Search Trees (BSTs) have the following properties:

●Each node has a value.

●The left subtree of a node contains only nodes with values less than the node's value.
●The right subtree of a node contains only nodes with values greater than the node's value.
●Both the left and right subtrees must also be binary search trees.
●There must be no duplicate nodes.
●These properties ensure that all nodes in the left subtree are smaller than the current node, and
all nodes in the right subtree are larger, allowing for efficient search and insertion operations.

Basic Operations of BST

[Link]: creates an empty tree.
[Link]: insert a node in the tree.
[Link]: Searches for a node in the tree.
[Link]: deletes a node from the tree.
[Link] : Traverse each node
√ Inorder: in-order traversal of the tree.
√ Preorder: pre-order traversal of the tree.
√ Postorder: post-order traversal of the tree.
Example of creating a binary search tree
Now, let's see the creation of binary search tree using an example.
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
● First, we have to insert 45 into the tree as the root of the tree.
● Then, read the next element; if it is smaller than the root node, insert it as the root of
the left subtree, and move to the next element.
●

Otherwise, if the element is larger than the root node, then insert it as the root
of the right subtree.
Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left

subtree.

Step 3 - Insert 79.

 As 79 is greater than 45, so insert it as the root node of
the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.

Step 5 - Insert 10.

 10 is smaller than 45 and 15, so it will be
inserted as a left subtree of 15.

Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of
10.

Step 8 - Insert 20.

20 is smaller than 45 but greater than 15,

so it will be inserted as the right subtree of 15.
 Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it

will be inserted as a left subtree of 55.

Now, the creation of binary search tree is completed. After that, let's move towards the
operations that can be performed on Binary search tree.
Deletion Operation

There are three cases for deleting a node from a binary search tree.
Case I
In the first case, the node to be deleted is the leaf node. In such a case,
 simply delete the node from the tree. 4 is to be deleted

4 child deleted
Case II
In the second case, the node to be deleted lies has a single child node. In such a case follow the
steps below:
●Replace that node with its child node.
●

Remove the child node from its

original position.

6 is to be deleted copy the value of its child to the Final Tree

node and delete the child
Case III
In the third case, the node to be deleted has two children. In such a case follow the steps below:
Get the inorder successor of that node.
●Replace the node with the inorder successor.
●

Remove the inorder

successor from its original position.

3 is to be Copy the value of the inorder Delete the inorder successor

Deleted successor (4) to the node
Search Operation
The algorithm depends on the property of BST that if each left subtree has values below root and
each right subtree has values above the root.
If the value is below the root, we can say for sure that the value is not in the right subtree; we need
to only search in the left subtree and if the value is above the root, we can say for sure that the
value is not in the left subtree; we need to only search in the right subtree.
Write a C++ program to implement Bianry search tree operations
#include <iostream>
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
};
Node* createNode(int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->left = newNode->right = nullptr;
return newNode;
}
Node* insertNode(Node* root, int data)
{
if (root == nullptr)
{
return createNode(data);
}
if (data < root->data)
{
root->left = insertNode(root->left, data);
}
else if (data > root->data)
{
root->right = insertNode(root->right, data);
}
return root;
}
void inorderTraversal(Node* root)
{
if (root != nullptr)
{
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
}
Node* searchNode(Node* root, int key)
{
if (root == nullptr || root->data == key)
{
return root;
}
if (root->data < key)
{
return searchNode(root->right, key);
}
return searchNode(root->left, key);
}
Node* minValueNode(Node* node)
{
Node* current = node;
while (current && current->left != nullptr)
{
current = current->left;
}
return current;
}
Node* deleteNode(Node* root, int data)
{
if (root == nullptr)
return root;
if (data < root->data)
{
root->left = deleteNode(root->left, data);
}
else if (data > root->data)
 {
root->right = deleteNode(root->right, data);
}
else
{
if (root->left == nullptr)
{
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr)
{
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
int main()
{
Node* root = nullptr;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 70);
root = insertNode(root, 60);
root = insertNode(root, 80);
cout << "Inorder traversal of the given Binary Search Tree is: ";
inorderTraversal(root);
cout << endl;
root = deleteNode(root, 20);
cout << "After deletion of 20: ";
 inorderTraversal(root);
cout << endl;
root = insertNode(root, 25);
cout << "After insertion of 25: ";
inorderTraversal(root);
cout << endl;
Node* found = searchNode(root, 25);
if (found != nullptr)
{
cout << "Node 25 found in the BST." << endl;
}
else
{
cout << "Node 25 not found in the BST." << endl;
}
return 0;
}
Output
Inorder traversal of the given Binary Search Tree is: 20 30 40 50 60 70 80
After deletion of 20: 30 40 50 60 70 80
After insertion of 25: 25 30 40 50 60 70 80
Node 25 found in the BST.
Tree Traversals

Traversal is a process to visit all the nodes of a tree and may print their values too. Because,
all nodes are connected via edges (links) we always start from the root (head) node. That is,
we cannot randomly access a node in a tree.

Tree Traversal Techniques:

A Tree Data Structure can be traversed in following ways:

● Inorder Traversal
● Preorder Traversal
 ●

Postorder Traversal

1.1Inorder Traversal

● First, visit all the nodes in the left subtree

● Then the root node
● Visit all the nodes in the right subtree

1.2Preorder Traversal

● Visit root node

● Visit all the nodes in the left subtree
● Visit all the nodes in the right subtree

1.3

Postorder Traversal
● Visit all the nodes in the left subtree
● Visit all the nodes in the right subtree
● Visit the root node

Steps to find the Preorder

 ● If root is NULL, return NULL.
●

Print the node.

● Visit left subtree.
● Visit right subtree.
Steps to find the Inorder
● If root is NULL, return NULL.
● Visit the left subtree.
● Print the node.
● Visit right subtree.
Steps to find the Inorder
● If root is NULL, return NULL.
● Visit the left subtree.
● Visit the right subtree
● Print the data.
Write C++ program to implement tree traversal

#include<bits/stdc++.h>
using namespace std;
class Tree
{
public:
int data;
Tree *left = NULL, *right = NULL;
// Constructor initialised
Tree (int x)
{
data = x;
left = NULL;
right = NULL;
 }
};
void preorder_traversal (Tree * root)
{
if (root == NULL)
return;
// Print the data
cout << root->data << " ";
// Visit Left subtree
preorder_traversal (root->left);
// Visit right subtree
preorder_traversal (root->right);
}
void inorder_traversal (Tree * root)
{
if (root == NULL)
return;
// Visit Left subtree
inorder_traversal (root->left);
// Print the data
cout << root->data << " ";
// Visit right subtree
inorder_traversal (root->right);
}
void postorder_traversal (Tree * root)
{
if (root == NULL)
return;
// Visit Left subtree
postorder_traversal (root->left);
// Visit right subtree
postorder_traversal (root->right);
// Print the data
cout << root->data << " ";
}
int main ()
 {
Tree *root = new Tree (17);
root->left = new Tree (10);
root->right = new Tree (11);
root->left->left = new Tree (7);
root->right->left = new Tree (27);
root->right->right = new Tree (9);
cout << "Preorder => ";
preorder_traversal (root);
cout << endl;
cout << "Inorder => ";
inorder_traversal (root);
cout << endl;
cout << "Postorder => ";
postorder_traversal (root);
cout << endl;
return 0;
}

Output:

Preorder => 17 10 7 11 27 9
Inorder => 7 10 17 27 11 9
Postorder => 7 10 27 9 11 17

Expression Tree

The expression tree is a binary tree with each internal node representing an operand, and
each leaf node representing an operator.

Properties of an expression tree

Properties of Expression Tree in Data Structure

● The operands are always represented by the leaf nodes. These operands are always
used in the operations.
● The operator at the root of the tree is always given top priority.
 ● When compared to the operators at the bottom of the tree, the operator at the bottom
is always given the lowest priority.
● Because the operand is always present at a depth of the tree, it is given the highest
priority of all operators.
● The expression tree can be traversed to evaluate prefix expressions, postfix
expressions, and infix expressions.

The given expression can be evaluated using the expression tree in data structure.

a + (b * c) + d * (e + f)

For example, the expression (a - b) * (c+d) can be represented as an expression tree where:

● The root is the multiplication operator ‘*’.

● The left child is the addition operator ‘-’, with operands ‘a’ and ‘b’ as its children.
● The right child is the subtraction operator’ +’, with operands ‘c’ and ‘d’ as its children.
Prefix expression is - *-ab+cd =( similar to preorder traversal
Postfix expression is : - ab-cd+* =( similar to postorder traversal

Applications of Tree Data Structures

● File System
Tree is prevalent used in file system of computer where thre and multiple files and
folder to locate a data and access it. The folder structure can be broken down to
understand in the form of an hierarchical tree data structure.
● Searching for Key
Speacial type of tree known as Binary Search Tree or BST can be used to find key
comparatively faster than other data structures like Array or Linked List.
● Finding Minimum Cost
Spanning trees are used to find the path in a tree with minimum cost such that all the
nodes are covered.
● Storage of elements
Unlike arrays, trees do not have an upper bound for the number of elements like linked
list as it stores the address to nodes are stored in heap that are allocated dynamically.
● XML/HTML Data
Data used in the website that is composed in the hierarchical form is a general
application of tree in data structure that has a usage in website architecture.
● Priority Queue
Priority queue data structure is implemented with the help of heap, a specialized form
of tree used to extract the highest priority element that is found at the root of the tree.
● Indexing in Databases
B Tree and B+ Tree, an advanced form of tree, are used to implement indexing in
 MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS)
VANIYAMBADI
PG and Department of Computer Applications
st
1 B.C.A – Semester - II
E-Notes (Study Material)

Core Course -1: Data Structure Code:24UCAC22

Unit: 4 - Definition- Representation of Graph- Types of graph-Breadth first traversal

– Depth first traversal- Applications of graphs.
Learning Objectives: To learn graph structures and application of graphs.
Course Outcomes: Solve problem involving in graphs.

Overview

- Graph: Definition
- Representation of Graph
- Types of graph
- Breadth first traversal
- Depth first traversal
- Applications of graphs.
Graph:

A Graph is a non-linear data structure consisting of vertices and edges. The vertices are
sometimes also referred to as nodes and the edges are lines or arcs that connect any two
nodes in the graph. More formally a Graph is composed of a set of vertices ( V ) and a set of
edges( E ). The graph is denoted by G(V, E).

It consists of two sets:

Vertices (V): Represent the entities themselves, also called nodes or points.
Edges (E): Represent the relationships between the entities, also called links or lines.

This graph has a set of vertices V= {1,2,3,4,5} and

set of edges E= { (1,2),(1,3),(2,3),(2,4),(2,5),(3,5),(4,50 }

Types of Graphs with Examples

There are different types of graphs, such as:

1. Un-Directed Graph

An Undirected graph is one in which the edges do not have a direction is called Un-
directed graph.

For example, the edge between vertex A and vertex B doesn't have any direction,
so we cannot determine whether the edge between vertex A and vertex B starts
 from vertex A or vertex B. Similarly, we can't determine the ending vertex of this
edge between these nodes.

2. Directed Graph

Another name for the directed graphs is digraphs. An directed graph is one in which
the edges do not have a direction is called Un-directed graph.

A graph in which the edges have a direction, indicating a

one-way
relationship between vertices.

[Link]
structure#types_of_graphs_in_data_structures
[Link]
202003242118236659shruti_saxena_Data%[Link]
3. Symmetric Digraph

Graph in which every node has as an edge in the reverse direction also called as
symmetric digraph. For every edge (u,v) in the graph, there must be one edge with (v,u).

4. Weighted Graph

A graph G= (V, E) is called a labeled or weighted graph because each edge has a value
or weight representing the cost of traversing that edge.
Basic Terminologies to Graph:

● Adjacency: A vertex is said to be adjacent to another vertex if there is an edge

connecting them. Vertices 2 and 3 are not adjacent because there is no edge between
them.
● Path: A sequence of edges that allows you to go from vertex A to vertex B is called a
path. 0-1, 1-2 and 0-2 are paths from vertex 0 to vertex 2.
● Directed Graph: A graph in which an edge (u,v) doesn't necessarily mean that there is
an edge (v, u) as well. The edges in such a graph are represented by arrows to show
the direction of the edge.
● Refer Book.

Graph Representation

Graphs are commonly represented in two ways:

1. Adjacency Matrix
2. Adjacency List

[Link] Matrix

An adjacency matrix is a 2D array of V x V vertices. Each row and column represent a vertex.

If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i
and vertex j.

The adjacency matrix for the graph we created above is

Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the
adjacency matrix symmetric about the diagonal.

Edge lookup(checking if an edge exists between vertex A and vertex B) is extremely fast in
adjacency matrix representation but we have to reserve space for every possible link between
all vertices(V x V), so it requires more space.

2. Adjacency List

An adjacency list represents a graph as an array of linked lists.

The index of the array represents a vertex and each element in its linked list represents the
other vertices that form an edge with the vertex.

The adjacency list for the graph we made in the first example is as follows:

An adjacency list is efficient in terms of storage because we only need to store the values for
the edges. For a graph with millions of vertices, this can mean a lot of saved space.

Graph Traversal

Graph traversal is a technique used for searching a vertex in a graph. The graph
traversal is also used to decide the order of vertices is visited in the search process. A
graph traversal finds the edges to be used in the search process without creating
loops. That means using graph traversal we visit all the vertices of the graph without
getting into looping path.

The two most common ways a Graph can be traversed are:

 1. Depth First Search (DFS)
2. Breadth First Search (BFS)

Breadth First Search (BFS) Algorithm

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion to search a
graph data structure for a node that meets a set of criteria. It uses a queue to remember the
next vertex to start a search, when a dead end occurs in any iteration.

Breadth First Search (BFS) algorithm starts at the tree root and explores all nodes at the
present depth prior to moving on to the nodes at the next depth level.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C
and G lastly to D. It employs the following rules.

Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.

Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Ste
Traversal Description
p
1 Initialize the queue.
We start from
2
visiting S (starting node),
 and mark it as visited.

We then see an unvisited

adjacent node from S. In
this example, we have
3 three nodes but
alphabetically we
choose A, mark it as visited
and enqueue it.

Next, the unvisited

adjacent node from S is B.
4
We mark it as visited and
enqueue it.

Next, the unvisited

adjacent node from S is C.
5
We mark it as visited and
enqueue it.

Now, S is left with no

6 unvisited adjacent nodes.
So, we dequeue and find A.
 From A we have D as
unvisited adjacent node.
7
We mark it as visited and
enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the
program is over.

Write a C++ to implement Breadth First Traversal or Breadth First Search

#include<iostream>
#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
int main()
{
int m;
cout <<"Enter no of vertices:";
cin >> n;
cout <<"Enter no of edges:";
cin >> m;
cout <<"\nEDGES \n";
for(k=1; k<=m; k++)
{
cin >>i>>j;
cost[i][j]=1;
}
cout <<"Enter initial vertex to traverse from:";
cin >>v;
cout <<"Visitied vertices:";
cout <<v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=1; j<=n; j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rare++]=j;
}
v=qu[front++];
cout<<v <<" ";
 k++;
visit[v]=0;
visited[v]=1;
}
return 0;
}

Output:

Enter no of vertices:4
Enter no of edges:4
EDGES
12
13
24
34
Enter initial vertex to traverse from:1
Visited vertices:1 2 3 4
12

BFS Algorithm Applications

● To build index by search index

● For GPS navigation
● Path finding algorithms
● In Ford-Fulkerson algorithm to find maximum flow in a network
● Cycle detection in an undirected graph
● In minimum spanning tree

Depth First Search (DFS) Algorithm

Depth First Search (DFS) algorithm is a recursive algorithm for searching all the vertices of a
graph or tree data structure. This algorithm traverses a graph in a depthward motion and
uses a stack to remember to get the next vertex to start a search, when a dead end occurs in
any iteration.

.
As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first,
then to F and lastly to C. It employs the following rules.

Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the
vertices from the stack, which do not have adjacent vertices.)

Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

Ste
Traversal Description
p

1 Initialize the stack.

Mark S as visited and put it

onto the stack. Explore any
unvisited adjacent node
from S. We have three nodes
2
and we can pick any of
them. For this example, we
shall take the node in an
alphabetical order.

Mark A as visited and put it

onto the stack. Explore any
unvisited adjacent node
3 from A. Both S and D are
adjacent to A but we are
concerned for unvisited
nodes only.

4 Visit D and mark it as visited

 and put onto the stack. Here,
we have B and C nodes,
which are adjacent to D and
both are unvisited. However,
we shall again choose in an
alphabetical order.

We choose B, mark it as
visited and put onto the
5 stack. Here B does not have
any unvisited adjacent node.
So, we pop B from the stack.

We check the stack top for

return to the previous node
and check if it has any
6
unvisited nodes. Here, we
find D to be on the top of the
stack.

Only unvisited adjacent

node is from D is C now. So
7
we visit C, mark it as visited
and put it onto the stack.

As C does not have any unvisited adjacent node so we keep popping the stack until we find a
node that has an unvisited adjacent node. In this case, there's none and we keep popping
until the stack is empty.

Write a C++ to implement Depth First Traversal or Depth First Search

#include<iostream>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
int main()
{
int m;
cout<<"Enter no of vertices:";
cin>> n;
cout<<"Enter no of edges:";
cin>> m;
cout<<"\nEDGES \n";
for(k=1; k<=m; k++)
{
cin>>i>>j;
cost[i][j]=1;
}
cout<<"Enter initial vertex to traverse from:";
cin>>v;
cout<<"DFS ORDER OF VISITED VERTICES:";
cout<< v <<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n; j>=1; j--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[--top];
cout<<v << " ";
k++;
visit[v]=0;
visited[v]=1;
}
return 0;
}

OUTPUT

Enter no of vertices:4
Enter no of edges:4
EDGES
12
13
24
34
Enter initial vertex to traverse from:1
DFS ORDER OF VISITED VERTICES:1 2 4 3

Application of DFS Algorithm

● For finding the path

● To test if the graph is bipartite
● For finding the strongly connected components of a graph
● For detecting cycles in a graph

Advantages of Graph Traversal

Here are the advantages of graph traversal:

● The BFS algorithm helps in finding the shortest path in an unweighted graph.
● DFS is more memory efficient than BFS as it doesn't need to store all the nodes at the
current level.
● Both BFS and DFS can be used to explore all nodes of a graph systematically,
ensuring complete traversal.

Disadvantages of Graph Traversal

Here are the disadvantages of graph traversal:

● The BFS is not ideal for deep graph traversal or pathfinding in weighted graphs.
● DFS can get stuck in infinite loops if the graph contains cycles unless cycle detection
is implemented.

Applications of Graph Traversal

Here are some of the applications of how graph traversal is used in real-world scenarios:

● Graph traversal is used to analyze social networks, identify communities, and detect
influential users.
● Graph traversal is used in search engines to index and rank web pages.
● GPS navigation systems use graph traversal to find the shortest path between two
points.
● Graph traversal is used to optimize database queries and improve query performance.
● Amazon’s recommendation system uses graph traversal to suggest products based
on user interactions and preferences.

Difference between BFS and DFS

Key BFS DFS

BFS stands for Breadth
Definition DFS stands for Depth First Search.
First Search.
 BFS uses a Queue to find DFS uses a Stack to find the
Data structure
the shortest path. shortest path.
BFS is better when target is DFS is better when target is far from
Source
closer to Source. source.
DFS is more suitable for decision
As BFS considers all
tree. As with one decision, we need
Suitability for neighbor so it is not
to traverse further to augment the
decision tree suitable for decision tree
decision. If we reach the conclusion,
used in puzzle games.
we won.
Speed BFS is slower than DFS. DFS is faster than BFS.
Time Complexity of BFS = Time Complexity of DFS is also
Time
O(V+E) where V is vertices O(V+E) where V is vertices and E is
Complexity
and E is edges. edges.
BFS requires more memory
Memory DFS requires less memory space.
space.
Tapping in In BFS, there is no problem In DFS, we may be trapped into
loops of trapping into finite loops. infinite loops.
BFS is implemented using
DFS is implemented using LIFO
Principle FIFO (First In First Out)
(Last In First Out) principle.
principle.

Practice Questions

SECTION-(A)

1. Define graph.
2. Define directed graph or digraph.
3. Define undirected graph.
4. Define a weighted graph.
5. Define adjacency matrix.
6. What does traversing a graph mean? State the different ways of traversing a graph.
7. What is a simple graph?
8. When a graph is said to be bi-connected?
9. What are the applications of graph?
10. How a graph is represented?
11. Define indegree and out degree of a graph.
12. What is breadth-first search?
13. Give the applications of DFS.
14. Differentiate BFS and DFS.
15. Define cut vertices.
16. Define Euler graph or Define Euler circuit.

SECTION-(B)

[Link] in detail about various types of graphs.

[Link] in detail different ways of representation of graphs.
[Link] graph traversal with suitable algorithm with example.
[Link] breadth first search algorithm for traversal of any graph with suitable examples.
[Link] depth first search algorithm for traversal of any graph with suitable examples.
[Link] about the applications of graphs.
 SECTION-(C)

[Link] about graph and their various types of graphs.

[Link] in detail about the graph traversals and their methods.

Additional Resources

1. [Link]
2. [Link]
3. [Link]
4. [Link]
structure
 MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS)
VANIYAMBADI
PG and Department of Computer Applications
st
1 B.C.A – Semester - II
E-Notes (Study Material)

Core Course -1: Data Structure Code:24UCAC22

Unit: 5 - Searching: Linear search-Binary search- Sorting: Bubble sort-Selection sort-

Insertion sort- Hashing: Hash functions-Separate chaining- Open Addressing-
Rehashing Extendible Hashing.
Learning Objectives: To understand various sorting, searching and Hashing.
Course Outcomes: Apply Algorithm for solving problems like sorting, searching,
insertion and deletion of data.

Overview

Searching
- Linear Search
- Binary Search
Sorting
- Bubble sort
- Selection sort
- Insertion sort
Hashing
- Hash functions
- Separate chaining
- Open Addressing
- Rehashing Extendible Hashing.

1
Searching
Searching algorithms are methods or procedures used to find a specific item or element
within a collection of data. These algorithms are widely used in computer science and are
crucial for tasks like searching for a particular record in a database, finding an element in a
sorted list, or locating a file on a computer.

There are two categories these searching techniques fall into. They are −
● Sequential Searching
● Interval Searching
Sequential Searching
As the name suggests, the sequential searching operation traverses through each element of
the data sequentially to look for the desired data. The data need not be in a sorted manner
for this type of search.
Example − Linear Search

Program:

#include <iostream>
#include <vector>
using namespace std;

2
int search(vector<int>& arr, int x) {
for (int i = 0; i < [Link](); i++)
if (arr[i] == x)
return i;
return -1;
}

int main() {
vector<int> arr = {2, 3, 4, 10, 40};
int x = 10;
int res = search(arr, x);
if (res == -1)
cout << "Not Present";
else
cout << "Present at Index " << res;
return 0;
}
Output
Present at Index 3
Advantages of Linear Search Algorithm:
● 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.
Disadvantages of Linear Search Algorithm:
● Linear search has a time complexity of O(N), which in turn makes it slow for large
datasets.
● Not suitable for large arrays.
When to use Linear Search Algorithm?
● When we are dealing with a small dataset.
● When you are searching for a dataset stored in contiguous memory.

Interval Searching

Unlike sequential searching, the interval searching operation requires the data to be in a
sorted manner. This method usually searches the data in intervals; it could be done by either
dividing the data into multiple sub-parts or jumping through the indices to search for an
element.

Example − Binary Search.

3
What is Binary Search Algorithm?

Binary search is a search algorithm used to find the position of a target value within a sorted
array. It works by repeatedly dividing the search interval in half until the target value is found
or the interval is empty. The search interval is halved by comparing the target element with
the middle value of the search space.

Conditions to apply Binary Search Algorithm in a Data Structure

To apply Binary Search algorithm:

4
 ● The data structure must be sorted.
● Access to any element of the data structure should take constant time.

Binary Search Algorithm

Below is the step-by-step algorithm for Binary Search:

1. Divide the search space into two halves by finding the middle index “mid”.
2. Compare the middle element of the search space with the key.
3. If the key is found at middle element, the process is terminated.
4. If the key is not found at middle element, choose which half will be used as the next
search space.
● If the key is smaller than the middle element, then the left side is used for
next search.
● If the key is larger than the middle element, then the right side is used for
next search.
5. This process is continued until the key is found or the total search space is
exhausted.

Advantages of Binary Search

● Binary search is faster than linear search, especially for large arrays.
● More efficient than other searching algorithms with a similar time complexity, such
as interpolation search or exponential search.
● Binary search is well-suited for searching large datasets that are stored in external
memory, such as on a hard drive or in the cloud.
Disadvantages of Binary Search
● The array should be sorted.
● Binary search requires that the data structure being searched be stored in contiguous
memory locations.
● Binary search requires that the elements of the array be comparable, meaning that
they must be able to be ordered.

Program:

#include<iostream>
using namespace std;
int main()
{
int len, i, arr[50], num, j, temp, first, last, middle;
cout<<"Enter the Size: ";
cin>>len;
cout<<"Enter "<<len<<" Elements: ";
for(i=0; i<len; i++)
5
 cin>>arr[i];
// sort the array first
for(i=0; i<(len-1); i++)
{
for(j=0; j<(len-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
// print the sorted array
cout<<"\nThe New Sorted Array is:\n";
for(i=0; i<len; i++)
cout<<arr[i]<<" ";
// now back to binary search
cout<<"\n\nEnter Element to be Search: ";
cin>>num;
first = 0;
last = (len-1);
middle = (first+last)/2;
while(first <= last)
{
if(arr[middle]<num)
first = middle+1;
else if(arr[middle]==num)
{
cout<<"\nThe number, "<<num<<" found at Position "<<middle+1;
break;
}
else
last = middle-1;
middle = (first+last)/2;
}
if(first>last)
cout<<"\nThe number, "<<num<<" is not found in given Array";
cout<<endl;
return 0;
}

6
Sorting

Sorting refers to rearrangement of a given array or list of elements according to a

comparison operator on the elements. The comparison operator is used to decide the new
order of elements in the respective data structure.

Why Sorting Algorithms are Important?

7
The sorting algorithm is important in Computer Science because it reduces the complexity
of a problem. There is a wide range of applications for these algorithms, including searching
algorithms, database algorithms, divide and conquer methods, and data structure
algorithms.

● When you have hundreds of datasets you want to print, you might want to arrange
them in some way.
● Once we get the data sorted, we can get the k-th smallest and k-th largest item in
O(1) time.
● Searching any element in a huge data set becomes easy. We can use Binary search
method for search if we have sorted data. So, Sorting become important here.
● They can be used in software and in conceptual problems to solve more advanced
problems.

Types of Sorting Techniques

There are various sorting algorithms are used in data structures. The following two types of
sorting algorithms can be broadly classified:

1. Comparison-based: We compare the elements in a comparison-based sorting

algorithm)
2. Non-comparison-based: We do not compare the elements in a non-comparison-
based sorting algorithm)

8
 Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the
adjacent elements if they are in the wrong order. This algorithm is not suitable for large data
sets as its average and worst-case time complexity are quite high.

● We sort the array using multiple passes. After the first pass, the maximum element
goes to end (its correct position). Same way, after second pass, the second largest
element goes to second last position and so on.
● In every pass, we process only those elements that have already not moved to
correct position. After k passes, the largest k elements must have been moved to the
last k positions.
● In a pass, we consider remaining elements and compare all adjacent and swap if
larger element is before a smaller element. If we keep doing this, we get the largest
(among the remaining elements) at its correct position.

How does Bubble Sort Work?

9
Program:
10
#include<iostream>
using namespace std;
int main()
{
int n, i, arr[50], j, temp;
cout<<"Enter the Size (max. 50): ";
cin>>n;
cout<<"Enter "<<n<<" Numbers: ";
for(i=0; i<n; i++)
cin>>arr[i];
cout<<"\nSorting the Array using Bubble Sort Technique..\n";
for(i=0; i<(n-1); i++)
{
for(j=0; j<(n-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
cout<<"\nArray Sorted Successfully!\n";
cout<<"\nThe New Array is: \n";
for(i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}

Output:

Enter the Size (max. 50): 5

Enter 5 Numbers: 5
1
4
2
3
Sorting the Array using Bubble Sort Technique..
Array Sorted Successfully!
The New Array is:
12345

11
Insertion Sort

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element
of an unsorted list into its correct position in a sorted portion of the list. It is like sorting
playing cards in your hands. You split the cards into two groups: the sorted cards and the
unsorted cards. Then, you pick a card from the unsorted group and put it in the right place in
the sorted group.

● We start with second element of the array as first element in the array is assumed to
be sorted.
● Compare second element with the first element and check if the second element is
smaller then swap them.
● Move to the third element and compare it with the first two elements and put at its
correct position
● Repeat until the entire array is sorted.

12
Program:

#include<iostream>
using namespace std;
int main()
{
intarr[50], tot, i, j, k, elem, index;
cout<<"Enter the Size for Array: ";
cin>>tot;
cout<<"Enter "<<tot<<" Array Elements: ";
for(i=0; i<tot; i++)
cin>>arr[i];
for(i=1; i<tot; i++)
{
elem = arr[i];
if(elem<arr[i-1])
{
for(j=0; j<=i; j++)
{
if(elem<arr[j])
{
index = j;
for(k=i; k>j; k--)
arr[k] = arr[k-1];
break;
}
}
}
else
continue;
arr[index] = elem;
cout<<"\nStep "<<i<<": ";
for(j=0; j<tot; j++)
cout<<arr[j]<<" ";
}
cout<<"\n\nThe New Array (Sorted Array):\n";
for(i=0; i<tot; i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}

Output:
Enter the Size for Array: 10
13
Enter 10 Array Elements: 10 1 9 2 8 3 7 4 6 5

Step 1: 1 10 9 2 8 3 7 4 6 5
Step 2: 1 9 10 2 8 3 7 4 6 5
Step 3: 1 2 9 10 8 3 7 4 6 5
Step 4: 1 2 8 9 10 3 7 4 6 5
Step 5: 1 2 3 8 9 10 7 4 6 5
Step 6: 1 2 3 7 8 9 10 4 6 5
Step 7: 1 2 3 4 7 8 9 10 6 5
Step 8: 1 2 3 4 6 7 8 9 10 5
Step 9: 1 2 3 4 5 6 7 8 9 10

The New Array (Sorted Array):

1 2 3 4 5 6 7 8 9 10

Quick Sort

QuickSort is a sorting algorithm based on the Divide and Conquer 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.

How does QuickSort Algorithm work?

QuickSort works on the principle of divide and conquer, breaking down the problem into
smaller sub-problems.

There are mainly three steps in the algorithm:

1. Choose a value in the array to be the pivot element.

2. Order the rest of the array so that lower values than the pivot element are on the left,
and higher values are on the right.
3. Swap the pivot element with the first element of the higher values so that the pivot
element lands in between the lower and higher values.
4. Do the same operations (recursively) for the sub-arrays on the left and right side of
the pivot element.

14
15
Program:

#include<iostream>
using namespace std;
void swap(intarr[] , int pos1, int pos2)
{
int temp;
temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
int partition(intarr[], int low, int high, int pivot)
{
int i = low;
int j = low;
while( i <= high)
{
if(arr[i] > pivot)
{
i++;
}
else
{
swap(arr,i,j);
i++;
j++;
}
}
return j-1;
}
void quickSort(intarr[], int low, int high)
{
if(low < high)
{
16
 int pivot = arr[high];
intpos = partition(arr, low, high, pivot);
quickSort(arr, low, pos-1);
quickSort(arr, pos+1, high);
}
}
int main()
{
int n ;
cout<< " Enter the size of array:";
cin>>n;
intarr[n];
for(int i = 0 ; i < n; i++)
{
cin>>arr[i];
}
quickSort(arr, 0 , n-1);
cout<<"The sorted array is: ";
for(int i = 0 ; i < n; i++)
{
cout<<arr[i]<<"\t";
}
}

Output:
Enter the size of array:5
32
21
54
76
45
The sorted array is: 21 32 45 54 76
Selection Sort

Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly

selecting the smallest (or largest) element from the unsorted portion and swapping it with
the first unsorted element. This process continues until the entire array is sorted.

1. First we find the smallest element and swap it with the first element. This way we
get the smallest element at its correct position.
2. Then we find the smallest among remaining elements (or second smallest) and

17
swap it with the second element.
3. We keep doing this until we get all elements moved to correct position.

18
19
Program:

#include<iostream>
using namespace std;
void swapping(int &a, int &b)
{ //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
void selectionSort(int *array, int size)
{
int i, j, imin;
for(i = 0; i<size-1; i++)
{
imin = i; //get index of minimum data
for(j = i+1; j<size; j++)
if(array[j] < array[imin])
imin = j;
//placing in correct position
swap(array[i], array[imin]);
}
}
int main()
{
int n;
n = 5;
int arr[5] = {12, 19, 55, 2, 16}; // initialize the array
cout << "Array before Sorting: ";
for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
selectionSort(arr, n);
cout << "Array after Sorting: ";
20
 for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
}
OUTPUT:

Array before Sorting: 12 19 55 2 16

Array after Sorting: 2 12 16 19 55

Hashing

Hashing is a technique used in data structures that efficiently stores and retrieves data in a
way that allows for quick access.

● Hashing involves mapping data to a specific index in a hash table (an array of
items) using a hash function that enables fast retrieval of information based on its
key.
● The great thing about hashing is, we can achieve all three operations (search, insert
and delete) in O(1) time on average.
● Hashing is mainly used to implement a set of distinct items and dictionaries (key
value pairs).

21
Key: A key can be any text or number provided as input to the hash function, which
determines an item’s index or storage position within a data structure. In this scenario, Jane
is the key.

Hash Table: It is a type of data structure that stores data in an array format. The table maps
keys to values using a hash function.

What is Collision?

Collision in hashing is when two or more elements are fighting for the same slot in the hash
table. In simple terms, we can say that If the hash function returns the same index for more
than one element then the collision will occur.

Hash Functions:

It performs the mathematical operation of accepting the key value as input and
producing the hash code or hash value as the output. Some of the characteristics of an ideal
hash function are as follows:
● It must produce the same hash value for the same hash key to be deterministic.
● Every input has a unique hash code. This feature is known as the hash property.
● It must be collision-friendly.
● A little bit of change leads to a drastic change in the output.
● The calculation must be quick

Types of Hash Functions

There are many hash functions that use numeric or alphanumeric keys. This article focuses
on discussing different hash functions:

1. Division Method.
2. Mid-Square Method

Division Method

The easiest and quickest way to create a hash value is through division. The k-value is
divided by M in this hash function, and the result is used.
Formula:
h(K) = k mod M

(where k = key value and M = the size of the hash table)

22
Advantages:

● This method is effective for all values of M.

● The division strategy only requires one operation, thus it is quite quick.

Disadvantages:

● Since the hash table maps consecutive keys to successive hash values, this
could result in poor performance.
● There are times when exercising extra caution while selecting M's value is
necessary.

Mid Square Method

23
The computation of the hash value requires two steps. With a (key, value) pair, a hash
function is computed by calculating the key’s square, or key*key. The code then selects some
digits from the center of the integer to generate the hash value.

k*k, or square the value of k

Using the middle r digits, calculate the hash value.
Formula:
h(K) = h(k x k)

(where k = key value)

Advantages:

● This technique works well because most or all of the digits in the key value affect the
result. All of the necessary digits participate in a process that results in the middle
digits of the squared result.
● The result is not dominated by the top or bottom digits of the initial key value.
Disadvantages:

● The size of the key is one of the limitations of this system; if the key is large, its
square will contain twice as many digits.
● Probability of collisions occurring repeatedly.

24
Separate chaining

Separate Chaining is a collision handling technique. Separate chaining is one of the most
popular and commonly used techniques in order to handle collisions. In this article, we will
discuss about what is Separate Chain collision handling technique, its advantages,
disadvantages, etc.

There are mainly two methods to handle collision:

1. Separate Chaining
2. Open Addressing

How Separate Chaining Works

1. Hash Table Structure: The hash table is an array of a fixed size. Each element of this
array is a head pointer to a linked list.
2. Hash Function: The hash function takes a key and computes an index in the array.
3. Insertion:
● Apply the hash function to the key to get the index.
● Insert the key-value pair at the head of the linked list at this index.
4. Searching:
● Compute the index for the key using the hash function.
● Search through the linked list at that index for the desired key.
5. Deletion:
● Find the index using the hash function.
● Search the linked list for the key and remove the corresponding node.

Algorithm for Implementing Separate Chaining

Separate Chaining - Insert

Algorithm 1

function INSERT (hash table, key, hash value)

if hash table[hash_value] = null then
hash_table[hash_value] = new LinkedList (key)
else
hash_table[hash_value). headInsert(key)
Separate Chaining - Insert Without Duplicates

25
 Algorithm 2

function INSERT_NO_DUPLICATES (hash_table, key, hash_value)

if Search (hash_table, key, hash_value) != -1 then
return
if hash_table[hash_value] = null then
hash_table[hash_value] = new LinkedList(key)
else
hash_table[hash_value].headInsert(key)

Separate Chaining - Search

Algorithm 3

function SEARCH(hash_table, key, hash_value)

list hash_table[hash_value]
for i 0 to [Link] -1 do
if [Link](i) = key then
return i
return -1

Advantages of Separate Chaining

● Simplicity: It is straightforward to implement.

● Less Sensitive to Hash Function: It works relatively well even with a poor hash
function.
● Performance: The performance gracefully degrades as the load factor increases (the
ratio of the number of elements to the number of buckets).

Disadvantages of Separate Chaining

● Memory Overhead: Every element requires extra memory for the pointers in the linked
list.
● Cache Performance: Poor cache performance compared to open addressing due to
the use of linked lists.
● Variable Length: The length of the chains can vary, leading to potentially poor
performance if one chain becomes significantly longer than others.

Open addressing

Open addressing is a collision resolution technique used in hash tables. In open addressing,
all elements are stored directly in the hash table itself. When a collision occurs (i.e., two items
hash to the same slot), the method seeks to find another slot to accommodate one of the
items using a probing sequence.

26
Linear probing

Linear probing is a type of open addressing where the probing sequence is linear.

How Linear Probing Works

1. Hash Function: Like any hash table, linear probing starts with a hash function that
computes an initial index for a given key.
2. Insertion:
● Compute the hash for the key to find the initial index.
● If the slot at the computed index is empty, insert the item there.
● If the slot is occupied, check the next slot (i.e., move linearly forward) until an
empty slot is found.
● If the end of the table is reached, wrap around to the beginning.

3. Searching:
● Compute the hash for the key to find the initial index.
● If the slot is empty, the key is not in the table.
● If the slot contains the key, return the item.
● If the slot contains a different key, move linearly forward until the key is found or
an empty slot is encountered.

27
 4. Deletion:

● Find the item using the search operation.

● Remove the item and mark the slot as deleted (a special marker different from
empty and occupied).
● Note: Deletion complicates the search and insert operations because the search
must continue past deleted items, and insert can use slots marked as deleted.

Advantages of Linear Probing

1. Memory Efficiency: All data is stored in the hash table, no extra space for pointers like
in separate chaining.
2. Cache-Friendly: Linear memory access pattern is good for cache performance.

Disadvantages of Linear Probing

1. Clustering: One of the significant drawbacks of linear probing is clustering. Clusters

of occupied slots tend to grow, increasing the average search time.
2. Load Factor: As the table becomes more filled, performance degrades. It’s essential to
keep the load factor (ratio of items to table size) relatively low.
3. Deletion Complexity: Deleted slots must be marked specially and complicate the
search process.

Quadratic probing

Quadratic probing is another method of open addressing used in hash tables to resolve
collisions. Unlike linear probing, where the interval between probes is fixed, quadratic probing
28
uses a quadratic function to calculate the interval between probes. This approach helps to
reduce the clustering problem seen in linear probing.

How Quadratic Probing Works

1. Insertion using Quadratic Probing:

● Use the hash function hash(key) to calculate the initial index for the given key.
● Check if the slot at the calculated initial index is empty.
● If it's empty, place the key-value pair in that slot, and the insertion is complete.
● If the slot at the initial index is occupied (collision occurred), quadratic probing
comes into play.
● Initialize a variable i to 1 (for the first iteration). Calculate the next probe index
using the quadratic probing formula:
● next_index = (initial_index + (i2)) % table_size
● Check if the slot at the calculated next_index is empty.
● If it's empty, place the key-value pair in that slot, and the insertion is complete.
● If the slot is occupied, repeat the probing process by incrementing i and
recalculating the next_index until an empty slot is found.

2. Search using Quadratic Probing:

● Use the hash function hash(key) to calculate the initial index for the given key.
● Check if the slot at the calculated initial index contains the key you're searching
for.
● If it does, return the associated value or indicate that the key is present.
● If the slot at the initial index does not contain the key (collision occurred), use
quadratic probing.
29
 ● Initialize a variable i to 1 (for the first iteration). Calculate the next probe index
using the quadratic probing formula:
● next_index = (initial_index + (i2)) % table_size
● Check if the slot at the next_index contains the key you're searching for.
● If it does, return the associated value or indicate that the key is present.
● If it doesn't, increment i and repeat the probing process until an empty slot is
found or the key is located.
● If the entire probing process completes without finding the key (i.e., an empty slot
is encountered), indicate that the key is not found in the table.

Advantages of Quadratic Probing

● Reduces Clustering: Compared to linear probing, quadratic probing significantly
reduces primary clustering, as the probe sequence spreads out more quickly.
● Better Cache Performance: It can offer better cache performance than more
randomized probing methods, although not as good as linear probing.
● Utilizes Hash Table Efficiently: Quadratic probing tends to utilize the hash table more
efficiently than linear probing before the performance degrades due to clustering.

Disadvantages of Quadratic Probing

● Secondary Clustering: Although it solves primary clustering, quadratic probing can

suffer from secondary clustering where different keys that hash to the same initial
index follow the same probe sequence.

30
 ● Complexity in Calculation: The probe sequence calculation is more complex than in
linear probing.
● Table Size Constraints: For quadratic probing to work correctly, the table size should
be a prime number, and even then, it does not guarantee that all slots can be probed.
● Load Factor Sensitivity: Like other open addressing methods, as the load factor
increases, performance tends to degrade due to an increase in collisions.

Double hashing

Double hashing is a technique used in hash tables to resolve collisions through open
addressing. Unlike linear or quadratic probing, double hashing uses a second hash function
to calculate the probe sequence. This approach significantly reduces the clustering issues
seen in other probing methods.

Definition of Double Hashing

Double hashing employs two hash functions. When a collision occurs (i.e., two keys hash to
the same index), the second hash function is used to determine the interval between probes.

How Double Hashing Works

1. Initial Hash Function: The first hash function computes an initial index. Let's denote
this as hash1(key).
2. Second Hash Function: A second, independent hash function computes another hash
value. Let's denote this as hash2(key). It's crucial that hash2(key) never evaluates to
zero to ensure that the probe sequence advances.
3. Collision Resolution:
a. Upon collision, the next index to probe is calculated using the formula:
(hash1(key) + i * hash2(key)) % table_size, where i is the ith probe (starting at 0).
b. This process repeats, incrementing i, until an empty slot is found or the table
is deemed full.
Advantages of Double Hashing

1. Reduces Clustering: Double hashing significantly reduces both primary and

secondary clustering.
2. Efficient Table Utilization: It tends to utilize the hash table efficiently, ensuring that
empty slots are found even when the table starts getting full.
3. Improved Performance: Offers better average-case performance for searching
compared to linear and quadratic probing.
Disadvantages of Double Hashing

1. Complexity: Requires the computation of two hash functions, which might be more
computationally intensive.
2. Design of Hash Functions: It's crucial to design both hash functions carefully to
ensure they are independent and that the second hash function never produces zero.
31
 3. Sensitivity to Hash Function Quality: The performance of double hashing is highly
reliant on the quality of both hash functions.

Rehashing

Rehashing is a concept primarily used in computer science and data structures, specifically
in the context of hash tables or hash maps. Hash tables are data structures that allow
efficient storage and retrieval of key-value pairs. They work by using a hash function to map
keys to specific locations (buckets) in an array, where the associated values are stored.

Rehashing is the process of resizing a hash table and redistributing its elements when the
current size of the table no longer efficiently accommodates the number of elements it
contains. The primary goal of rehashing is to maintain a low load factor, which is the ratio of
the number of stored elements to the total number of buckets in the hash table. A low load
factor helps ensure that the hash table remains efficient in terms of time complexity for
insertion, retrieval, and deletion operations.

Here's how rehashing typically works:

1. Check the Load Factor: Periodically or after each insertion operation, the hash table
checks its load factor. If the load factor exceeds a predefined threshold (often around
0.7 or 0.8), it indicates that the table is becoming crowded, and rehashing is needed.
2. Create a New Hash Table: A new, larger hash table (usually with double the number
of buckets) is created. The number of buckets is increased to reduce the load factor
and make the table more efficient.
3. Rehashing Process: Each element in the old hash table is rehashed, meaning their
keys are mapped to new bucket positions in the larger table using the updated hash
function. This process redistributes the key-value pairs among the new buckets.
4. Transfer Elements: The key-value pairs are transferred from the old table to the new
table based on their new hash values. This involves copying the data from the old
table to the appropriate locations in the new table.
5. Update References: Any references or pointers to the old hash table are updated to
point to the new hash table.
6. Dispose of the Old Table: Once all elements have been transferred, the old hash table
can be deallocated or discarded.

Extendible hashing
32
Extendible hashing is a dynamic hashing technique used in computer science and database
systems to efficiently organize and search data. It is designed to provide a compromise
between static hashing (which requires a fixed number of buckets) and dynamic hashing
(which may involve frequent rehashing). Extendible hashing dynamically adapts the number
of buckets as data grows, minimizing the overhead associated with rehashing.

Here's how extendible hashing works:

1. Initialization: Initially, there is a single directory that contains a fixed number of empty
buckets. The directory acts as an index or directory of the available buckets.
2. Hashing: When a new key-value pair needs to be inserted or searched for, a hash
function is applied to the key to determine the bucket in which the pair should be
stored or searched. The hash function generates an index into the directory.
3. Directory Structure: The directory contains entries, each of which corresponds to a
specific bucket. Initially, all entries point to the same bucket. These pointers are
usually represented as binary strings or integers.
4. Bucket Splitting: When a bucket becomes full (i.e., it reaches a predefined load
factor), it is split into two new buckets. This splitting operation is done by adding a
single bit to the binary string associated with the directory entry that pointed to the full
bucket. This effectively doubles the number of buckets available for storing data.
5. Directory Expansion: As buckets are split and new ones are created, the directory's
structure grows dynamically. The directory entries are updated to reflect the new
bucket locations as they are created.
6. Search and Insertion: When searching for a key or inserting a new key-value pair, the
hash function generates an index into the directory. The directory entry at that index is
used to determine the appropriate bucket to search or insert into.
7. Merging: Over time, if some buckets become empty due to deletions or if the directory
becomes sparsely populated, extendible hashing allows for merging. This involves
reducing the number of buckets by removing a bit from directory entries and merging
adjacent buckets to maintain a balanced structure.

33
Extendible hashing offers several advantages:

● It adapts dynamically to the data distribution, avoiding the need for frequent
rehashing.
● It provides a good balance between space usage and search efficiency.
● It offers predictable performance for search, insertion, and deletion operations.

Additional Resources

1. [Link]
2. [Link]
Practice Questions:

SECTION-(A)
[Link] is meant by sorting and searching?
[Link] the types of [Link] it.
[Link] are the types of sorting?
[Link]fine insertion sort.
[Link] is the time complexity of insertion sort?
[Link]fine selection sort.
[Link] are the advantages and disadvantages of selection sort?
[Link]fine shell sort.
[Link] is the time complexity of shell sort?
[Link]fine bubble sort.
[Link]fine radix sort.
[Link] are the types of searching?
[Link]fine Linear search.
[Link]fine binary search.
[Link] linear and binary search.
[Link] is the time complexity of binary search?

34
[Link] is hashing?List its techniques.
[Link] is hash function?
[Link]fine hash table.
[Link]fine separate chaining.
[Link] is open addressing?
[Link]fine probing.
[Link] is rehashing?
[Link] is the collision in hashing?
[Link]fine extendible hashing.
SECTION-(B)
[Link] an algorithm to sort n numbers using insertion sort.
[Link] an algorithm to sort n numbers using selection sort.
[Link] an algorithm to sort n numbers using shell sort.
[Link] an algorithm to sort n numbers using bubble sort.
[Link] short notes on hashing and the various types of hash function.
[Link] a short notes on hashing and the various collision resolution techniques.
[Link] the rehashing technique.
[Link] the extensible hashing.
SECTION-(C)
[Link] in detail about the sorting and their types.
[Link] in detail about linear search with example program.
[Link] in detail about binary search with example program.
[Link] to implement Separate chaining.
5. Explain Rehashing techniques.
6. Explain Extendible rehashing techniques.

35
 MARUDHAR KESARI JAIN COLLEGE FOR WOMEN (AUTONOMOUS),
VANIYAMBADI

PG DEPARTMENT OF COMPUTER APPLICATIONS

QUESTION BANK

SUBJECT NAME: Data Structure

SUB CODE : 24UCAC22

REGULATION : 2024-2025
YEAR : I BCA

Prepared By Approved By

[Link]

[Link]

UNIT I
2-Marks Questions:

1. Define data structure.

 2. What are the difference between linear and non-linear data structure?

3. Define array?

4. Define abstract data type?

5. List out the ADT operations?

6. What is the advantage of ADT?

7. Define list. How it is implemented?

8. Define linked list?

9. Define doubly linked list?

10. Define singly linked list?

11. Define circularly linked list?

12. List the operations of linked list?

13. List out the application of linked list?

14. Compare linked list over arrays?

15. State the types of linked list?

16. Write the nodes structure for doubly linked list?

17. Define polynomial manipulation?

18. Differentiate between singly linked list and doubly linked list?

19. Explain the various positions. Where a node can be inserting in singly linked list?

20. Differentiate between primitive data structure and Non-primitive data structure?

5-Marks Questions:

1. What are the differences between linear and non-linear data structure?

2. Write about abstract data type.

 3. Write about the applications of list.

4. What are the advantages of linked list implementation of list?

5. List the limitation in array based implementation of list ADT.

6. Explain the singly linked list and its operations.

7. Explain the procedure to insert a node in a singly linked list.

8. Write a note on doubly linked list.

9. Define circular linked list. Write the routine for its operations.

10. Define polynomial. How it is represented using linked list?

10-Marks Questions:

1. Write a program to implement singly linked list using c++.

2. Write a program to implement Doubly linked list using c++.

3. Write a program to implement Circular linked list using c++.

4. Explain types CLL in detail.

5. Explain Polynomial Manipulation.

6. Explain the operations available for a singly linked list?

7. Explain the doubly linked list and its operations in detail?

8. Define circular double linked list. Write the routine for its operations.

9. Explain the procedure to add two polynomials using linked list?

UNIT II
2-Marks Questions:

1. Define stack.
2. List out the any two applications of Stack?
 3. Define PUSH.
4. Define POP.
5. Define Infix Expression.
6. Define Prefix(or)Polish notation.
7. Define Postfix(or)Reverse Polish notation.
8. Write the postfix and prefix forms for the expression A+B*(C-D)/(P-R)?
9. What are the types of Queue?
10. Define Queue.
11. What are the operations on a Queue?
12. List the application of Queue.
13. How do you test for an empty Queue?
14. Define Circular Queue.
15. Give the advantage and disadvantages of Circular Queue.
16. List the applications of circular Queue.
17. Distinguish between a Stack and a Queue.
18. What is Priority Queue?
19. Give the advantage and disadvantages of dequeue.
20. What are the operations that can be performed on Double ended Queue?
21. Differentiate between Queue and Double ended Queue.
22. What is Double ended Queue?

5 & 10-Marks Questions:

1. Write an algorithm to convert infix expression to postfix expression.

2. Explain the concept of stack with illustrations.
3. Explain the operations performed on a Stack.
4. Briefly explain the application of Stack.
5. Explain the concept of Queue with illustrations.
6. Discuss the operations of Queue.

7. Explain the applications of Queue.

8. Briefly explain circular Queue.
9. Briefly explain Queue.
10. Briefly explain priority Queue.
11. What is a Stack?Explain any two operations on Stack with required algorithm.
12. Describe the concept of Queue and also write algorithms to insert and delete an
 element in queue.
13. Explain various operations available on a Queue.
14. How is an infix expression converted to postfix [Link] the expression
A+B*C+(D*E+F)*G to postfix form.

UNIT III

2-Marks Questions:

1. Define tree.
2. Define Height of tree.
3. Define depth of tree.
4. Define sibling.
5. What are the different types of traversing?
6. What are the types of binary trees.
7. List the application of tree.
8. Define complete binary tree.
9. Define binary search tree.
10. What are the various operation performed in the binary search tree.
11. Define expression tree.
12. Define construction of expression trees.
13. Define heap.
14. What are the types of heap?
15. List the applications of heaps.

5 & 10-Marks Questions:

1. Explain in detail about binary tree data structure.

2. Discuss about the types of binary tree.
3. Explain in detail about the binary tree traversal and their typestypes.
4. Explain in detail about types tree in data structure.
 5. Explain in detail about binary tree data structure.
6. Discuss about the types of binary tree.
7. Explain implementation of biary tree.
8. How Expression tree works ? explain its operations.
9. Explain Basic Terminologoes of Tree
10. Explain in detail about the binary Search tree.
11. Discuss Tree traversal techniques.
12. Explain Heap Techniques.

UNIT IV

2-Marks Questions:

1. Define graph.
2. Define directed graph or digraph.
3. Define undirected graph.
4. Define a weighted graph.
5. Define adjacency matrix.
6. What does traversing a graph mean? State the different ways of traversing a graph.
7. What is a simple graph?
8. When a graph is said to be bi-connected?
9. What are the applications of graph?
10. How a graph is represented?
11. Define indegree and out degree of a graph.
12. What is breadth-first search?
13. Give the applications of DFS.
14. Differentiate BFS and DFS.
15. Define cut vertices.
16. Define Euler graph or Define Euler circuit.

5 -Marks Questions:

1. Explain in detail about various types of graphs.

2. Explain in detail different ways of representation of graphs.
3. Explain graph traversal with suitable algorithm with example.
4. Explain breadth first search algorithm for traversal of any graph with suitable
 examples.
5. Explain depth first search algorithm for traversal of any graph with suitable examples.
6. Write about the applications of graphs.

10-Marks Questions:

1. Explain about graph and their various types of graphs.

2. Explain in detail about the graph traversals and their methods.

UNIT IV
2-Marks Questions:

1. What is meant by sorting and searching?

2. Give the types of [Link] it.
3. What are the types of sorting?
4. Define insertion sort.
5. What is the time complexity of insertion sort?
6. Define selection sort.
7. What are the advantages and disadvantages of selection sort?
8. Define bubble sort.
9. What are the types of searching?
10. Define Linear search.
11. Define binary search.
12. Differentiate linear and binary search.
13. What is the time complexity of binary search?
14. What is hashing?List its techniques.
15. What is hash function?
16. Define hash table.

17. Define separate chaining.

18. What is open addressing?
19. Define probing.
20. What is rehashing?
21. What is the collision in hashing?
 22. Define extendible hashing.

5-Marks Questions:

1. Write an algorithm to sort n numbers using insertion sort.

2. Write an algorithm to sort n numbers using selection sort.
3. Write an algorithm to sort n numbers using shell sort.
4. Write an algorithm to sort n numbers using bubble sort.
5. Write short notes on hashing and the various types of hash function.
6. Write a short notes on hashing and the various collision resolution techniques.
7. Explain the rehashing technique.
8. Explain the extensible hashing.

10-Marks Questions:

1. Explain in detail about the sorting and their types.

2. Explain in detail about linear search with example program.
3. Explain in detail about binary search with example program.
4. How to implement Separate chaining.
5. Explain Rehashing techniques.
6. Explain Extendible rehashing techniques.
 DATA STRUCTURE
Subject Code: 24UCAC22 | I BCA | Regulation: 2024-2025
MOST IMPORTANT QUESTIONS – ALL UNITS

UNIT I – Lists & Linked Lists

2-Mark Questions
1. Define data structure.
2. Differentiate between linear and non-linear data structure.
3. Define abstract data type (ADT) and list its operations.
4. Define linked list. State its types.
5. Differentiate between singly linked list and doubly linked list.
6. Write the node structure for doubly linked list.
7. Define polynomial manipulation.

5-Mark Questions
1. Explain Abstract Data Type (ADT) with its advantages.
2. Explain singly linked list and its operations.
3. Write a note on doubly linked list.
4. Define circular linked list and write routines for its operations.
5. Define polynomial and explain how it is represented using linked list.

10-Mark Questions
1. Write a C++ program to implement singly linked list.
2. Write a C++ program to implement doubly linked list.
3. Write a C++ program to implement circular linked list.
4. Explain polynomial manipulation using linked list in detail.

UNIT II – Stack & Queue

2-Mark Questions
1. Define Stack. List any two applications.
2. Define PUSH and POP operations.
3. Define Infix, Prefix, and Postfix expressions.
4. Write postfix and prefix forms for A+B*(C-D)/(P-R).
5. Define Queue and list its operations.
6. Define Circular Queue. Give its advantages and disadvantages.
7. What is a Priority Queue?
8. Differentiate between Stack and Queue.
9. What is a Double Ended Queue (Deque)? List its operations.

5-Mark Questions
1. Write an algorithm to convert infix expression to postfix expression.
2. Explain the concept of Stack with illustrations and operations.
3. Explain the concept of Queue with illustrations and operations.
4. Briefly explain Circular Queue.
5. Briefly explain Priority Queue.

10-Mark Questions
1. Explain any two operations on Stack with algorithm.
2. Describe Queue and write algorithms to insert and delete elements.
3. How is an infix expression converted to postfix? Convert A+B*C+(D*E+F)*G to
postfix.
4. Explain all operations available on a Queue in detail.

UNIT III – Trees & Heaps

2-Mark Questions
1. Define tree, height of tree, depth of tree, and sibling.
2. What are the types of binary trees?
3. Define complete binary tree and binary search tree.
4. What are the different types of tree traversals?
5. Define heap and its types.
6. Define expression tree.
7. List the applications of trees and heaps.
5-Mark Questions
1. Explain binary tree data structure with types.
2. Explain binary tree traversal techniques in detail.
3. Explain binary search tree and its operations.
4. Explain expression tree and its operations.
5. Explain heap and heap techniques.

10-Mark Questions
1. Explain binary tree data structure and its implementation in detail.
2. Discuss all tree traversal techniques with examples.
3. Explain binary search tree with operations in detail.
4. Explain heap data structure and its techniques in detail.

UNIT IV – Graphs
2-Mark Questions
1. Define graph. Differentiate directed and undirected graph.
2. Define weighted graph, adjacency matrix, and indegree/outdegree.
3. What is Breadth-First Search (BFS)?
4. Differentiate BFS and DFS.
5. Define cut vertex and Euler circuit.
6. List the applications of graphs.

5-Mark Questions
1. Explain various types of graphs in detail.
2. Explain the different ways of representing a graph.
3. Explain BFS algorithm with example.
4. Explain DFS algorithm with example.

10-Mark Questions
1. Explain graphs and their various types in detail.
2. Explain graph traversal methods (BFS and DFS) with examples.
 UNIT V – Sorting, Searching & Hashing
2-Mark Questions
1. Define sorting and searching. Give types of each.
2. Define insertion sort and its time complexity.
3. Define selection sort. Give its advantages and disadvantages.
4. Define bubble sort.
5. Differentiate linear and binary search. Give time complexity of binary search.
6. What is hashing? List its techniques.
7. Define hash function, hash table, and collision.
8. Define separate chaining, open addressing, and probing.
9. What is rehashing and extendible hashing?

5-Mark Questions
1. Write an algorithm for insertion sort.
2. Write an algorithm for selection sort.
3. Write an algorithm for bubble sort.
4. Write short notes on hashing and various hash functions.
5. Explain collision resolution techniques in hashing.
6. Explain rehashing and extendible hashing.

10-Mark Questions
1. Explain sorting techniques (insertion, selection, bubble) in detail.
2. Explain linear search and binary search with example programs.
3. Explain separate chaining in hashing.
4. Explain rehashing and extendible hashing techniques in detail.