BSC MPCS III SEM DATA STRUCTURES USING C++

UNIT – II

Recursion is a programming technique where a function calls itself to solve a problem. It breaks down a
complex problem into smaller sub-problems of the same type.

A recursive function has:

1. Base Case – when the function stops calling itself.

2. Recursive Case – when the function continues calling itself.

Every recursion must have a base case to avoid infinite loops.

Common examples using recursion: Factorial, Fibonacci series, Tree traversals, Tower of Hanoi,
Binary search

Example: Factorial Calculation

The factorial of a non-negative integer n (written as n!) is the product of all positive integers less
than or equal to n.
For example:
5! = 5 × 4 × 3 × 2 × 1 = 120
This can be expressed recursively:
Base case: factorial(0) = 1
Recursive case: factorial(n) = n × factorial(n - 1)
Recurrence:-
Recurrence is like a mathematical rule or formula that explains how a problem can be
broken down into smaller parts, showing how each step depends on the previous one. It describes
the relationship between a big problem and smaller versions of the same problem.
Think of it as a way to express how the solution to a problem depends on the solutions to
smaller pieces of that problem.
Explanation:-
If you know the previous one (or a few previous) terms in a series, the recurrence tells you how to
get the next one.
Recurrence relations are widely used in mathematics and computer science—especially when
analyzing recursive algorithms.
General Form
A simple (first-order) recurrence looks like:

xn+1=f(xn)

1 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
A second-order recurrence (depends on two previous terms) looks like:

Xn+1=f(xn, xn-1)

Examples
1. Factorial
n!=n×(n−1)! With 0!=1
This means the factorial of any number n is the product of n and the factorial of (n−1).
2. Fibonacci Sequence

Fn=Fn−1+Fn−2 with F0=0, F1=1

Each term is the sum of the previous two. The sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, ....
Use of Stack in Recursion:
The stack is a special area of memory where temporary variables are stored. It acts on the
LIFO principle. To understand how recursive functions use the stack, let us discuss Program Code
The core steps are given in the following code:
int factorial(int n)
{
if(n ==0)
return 1;
else
return n * Factorial(n − 1);
}
Let n = 3; that is, let us compute the value of 3!, which is 3 * 2 * 1 = 6. When the function is
called for the first time, n holds the value 3, so the else statement is executed. The function knows
the value of n but not of Factorial(n − 1), so it pushes n (value = 3) onto the stack and calls itself
for the second time with the value 2. This time, the else statement is again executed, and n (value
= 2) is pushed onto the stack as the function calls itself for the third time with the value 1. Now,
the if statement is executed and as n = 1, the function returns 1
Since the value of Factorial(1) is now known, it reverts to its second execution by popping
the last value 2 from the stack and multiplying it by 1. This operation gives the value of
Factorial(2), so the function reverts to its first execution by popping the next value 3 from the
stack and multiplying it with the factorial, giving the value 6, which the function finally returns.

2 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Variants(Types) of Recursion:
Depending on the following characterization, the recursive functions are categorized as direct,
indirect, linear, tail and tree recursions.
Recursion may have any one of the following forms:
1. A function calls itself.
2. A function calls another function which in turn calls the caller function.
3. The function call is part of the same processing instruction that makes a recursive function call.
Direct recursion: Recursion is when a function calls itself. Recursion is said to be direct when a function
calls itself directly. The Factorial() function we discussed in above is an example of direct recursion
Example code for Direct recursion:
int Factorial(int n)
{
if(n ==0)
return 1;
else
return n * Factorial(n − 1);
}

Indirect recursion: A function is said to be indirectly recursive if it calls another function, which in turn
calls it.
Example code for Indirect recursion:
int Fact(int n)
{
if(n <= 1)
return 1;
else
return (n * Dummy(n - 1));
}
void Dummy(int n)
{
Fact(n);
}

3 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Binary recursion:
Binary recursion is a type of recursion in which a function makes two recursive calls to itself
during its execution. This approach is natural for problems that can be divided into two distinct
sub problems of similar nature. It's especially useful for processing structures like trees or for
certain mathematical sequences.
The Fibonacci sequence is a well-known example of binary recursion. Each term (after the first
two) is the sum of the previous two terms:

int Fibonacci(n)
{
if(n == 1 ||n == 2)
return 1;
else
return(Fibonacci (n - 1) + Fibonacci (n - 2));
}
Step-by-step:
1. fibonacci(4)
→ needs fibonacci(3) and fibonacci(2)
2. fibonacci(3)
→ needs fibonacci(2) and fibonacci(1)
3. Base cases reached (fibonacci(1) and fibonacci(2) both return 1)
4. Results bubble back up and get added.

Tail end recursion(Tail recursive):

Tail end recursion (commonly called tail recursion) is a form of recursion where the recursive call
is the very last thing performed by the function before it returns. There are no further operations or
calculations to perform after the recursive call.
Simple Example: Print Numbers from n to 0 Tail Recursive Version:
print_down(int n)
{
if n < 0:
return
print(n)
print_down(n - 1) # Recursive call is last action
}
4 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
The function prints n, then recursively calls itself with n-1.
Nothing is left to do after the recursive call except to return.

Tree Recursion: Tree recursion occurs when a function makes more than one recursive call to itself
within its body, not just one. This splits the computation into several branches at each step, forming a
tree-like structure of calls. Each recursive call may itself make multiple further recursive calls, which
rapidly increases the number of total calls as the recursion deepens.
Example: Fibonacci Sequence

The Fibonacci sequence is a classic case of tree recursion.

Each term (after the first two) is calculated as the sum of its two predecessors:

int fibonacci(int n) {
if (n == 1 || n == 2) // base cases
return 1;
return fibonacci(n - 1) + fibonacci(n - 2); // two recursive calls
}
Every call to fibonacci(n) makes two recursive calls: fibonacci(n-1) and fibonacci(n-2).
This branching continues until the base cases are met.
If n= 4

Fibonacci(4)

Fibonacci(3) Fibonacci(2)

Fibonacci(2) Fibonacci(1) Fibonacci(1) Fibonacci(0)

1 0 1 1 0

5 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
EXECUTION OF RECURSIVE CALLS:
Recursive calls occur when a function calls itself either directly or indirectly, breaking a problem into
smaller subproblems. Each recursive call gets its own memory space (often called a stack frame),
allowing the function to progress towards a solution and then return those solutions up the chain until
the original call completes.

Consider the following two lines from the Factorial() function in Program Code:
int Factorial( int n)
{
if(n <= 1)
return 1;
else
return n * Factorial(n - 1);
}
Consider the first call as Factorial(4). Now,
1. n = 4
Hence, statement 4 in Factorial function, which is a recursive call, is executed.
Push 4 onto the stack and call Factorial(4 − 1).

2. n = 3
Hence, push 3 onto the stack and call Factorial(2).

3. n = 2
Hence, push 2 onto the stack and call Factorial(1).

4. n = 1 Now execute statement 2 in Factorial function, which returns 1.

5. Pop the contents and n = 2, so now the expression becomes 2 * 1.

6. Now, n = 3 after popping the top of the stack contents. Therefore, the expression is 3 * 2 * 1.
7. After popping the top of the stack contents applying n = 4, the expression is 4 * 3 * 2 * 1 = 24.
8. After popping the top of the stack contents, we get to know that the stack is empty, and the answer is
4! = 24.

At the end condition, when no more recursive calls are made, the following steps are performed:
1. If the stack is empty, then execute a normal return.
2. Otherwise, pop the stack frame, that is, take the values of all the parameters that are on the top of the
stack and assign these values to the corresponding variables.
3. Use the return address to locate the place where the call was made.
4. Execute all the statements from that place (address) where the call was made.
5. Go to step 1.

6 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Recursive Functions:
A recursive function is a function that solves a problem by calling itself on smaller instances of the
same problem, usually until it reaches a simple "base case" that can be solved directly.

Towers of Hanoi: is one example of Recursion

The Towers of Hanoi puzzle consists of three rods and a number of disks of different sizes that can slide
onto any rod. The puzzle starts with the disks stacked in ascending order on one rod (the largest at the
bottom). The goal is to move the entire stack to another rod, following these rules:
1. Only one disk may be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another
stack or an empty rod.
3. No disk may be placed on top of a smaller disk.
Program code:
#include <iostream.h>
void towerOfHanoi(int n, char A, char B, char C)
{
if (n == 1)
{
cout << "Move disk 1 from rod " << A <<" to rod " << B<<endl;
return;
}
towerOfHanoi(n - 1, A, C, B);
cout << "Move disk " << n <<" from rod "<<A<<" to rod" <<B<< endl;
towerOfHanoi(n - 1, C, B, A);
}

int main()
{
int n = 4;
towerOfHanoi(n, 'A', 'C', 'B');
return 0;
}

7 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++

Iteration versus Recursion:

The Recursion and Iteration both repeatedly execute the set of instructions. Recursion is when a
statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the
controlling condition becomes false. The primary difference between recursion and iteration is
that recursion is a process, always applied to a function and iteration is applied to the set of
instructions which we want to get repeatedly executed.

Recursion Iteration

1. Recursion uses selection structure. 1. Iteration uses repetition structure.

2. Infinite recursion occurs if the recursion 2. An infinite loop occurs with iteration if the
step does not reduce the problem in a loop condition test never becomes false and
manner that converges on some condition Infinite looping uses CPU cycles repeatedly.
(base case) and Infinite recursion can
crash the system.
3. An iteration terminates when the loop
3. Recursion terminates when a base case is
condition fails.
recognized.

8 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++

4. Recursion is usually slower than 4. An iteration does not use the stack so
iteration due to the overhead of it's faster than recursion.
maintaining the stack.
5. Recursion uses more memory than
5. Iteration consumes less memory.
iteration.
6. Recursion makes the code smaller. 6. Iteration makes the code longer.

Applications of recursion:
The following are the major areas where the process of recursion can be applied:
1. Artificial intelligence
2. Search techniques
3. Game playing
4. Computational linguistics and natural language processing
5. Expert systems
6. Pattern recognition and computer vision
7. Robotics

Sample Programs
program code to find nth term of the Fibonacci Sequence

#include<iostream.h>

int fibonacci(int n)
{
if((n==1)||(n==0))
{
return(n);
}
else
{
return(fibonacci(n-1)+fibonacci(n-2));
}
}
int main()
{
int n,i=0;
cout<<"\nHow many terms for Fibonacci Series :: ";
cin>>n;
cout<<"\nFibonacci Series for [ "<<n<<" ] Terms as follows :: \n\n";

9 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
while(i<n)
{
cout<<" "<<fibonacci(i);
i++;
}
cout<<"\n"; return 0;
}

program code to find Factorial of +ve Integer program code to find GCD of two numbers
#include<iostream.h> #include <iostream.h>
int factorial(int n);
int main() int hcf(int n1, int n2);
{ int main()
int n; {
cout << "Enter a positive integer: "; cin >> n; int n1, n2;
cout << "Factorial of " << n << " = " << cout << "Enter two positive integers: ";
factorial(n); cin >> n1 >> n2;
return 0; cout << "H.C.F of " << n1 << " & " << n2 << " is: "
} << hcf(n1, n2);
int factorial(int n) return 0;
{ }
if(n > 1) int hcf(int n1, int n2)
return n * factorial(n - 1); {
else if (n2 != 0)
return 1; return hcf(n2, n1 % n2);
} else
return n1;
}

10 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Queues

Queue: Queue is a linear data structure in which the insertion and deletion operations are performed at
two different ends. In a queue data structure, the insertion operation is performed at a position which is
known as 'rear' (back) and the deletion operation is performed at a position which is known as 'front'.
In queue data structure, the insertion and deletion operations are performed based on FIFO (First In
First Out) principle.

In a queue data structure, the insertion operation is performed using a function called "enQueue()" and
deletion operation is performed using a function called "deQueue()".

Example
Queue after inserting 25, 30, 51, 60 and 85.

Representation of Queue:
Let us consider a queue, which can hold maximum of five elements.
Initially the queue is empty.
Index -1 0 1 2 3 4
Element
Position Front Rear
F RO NT = REA R = -1
Now, insert 11 to the queue. Then queue status will be:
Index -1 0 1 2 3 4
Element 11
Position Front Rear
REA R = REA R + 1 = 0 F RO NT = 0
Next, insert 22 to the queue. Then the queue status is:

Index -1 0 1 2 3 4
Element 11 22
Position Front Rear
REA R = REA R + 1 = 1 F RO NT = 0

11 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Again insert another element 33 to the queue. The status of the queue is:
Index -1 0 1 2 3 4
Element 11 22 33
Position Front Rear
Now, delete an element. The element deleted is the element at the front of the queue. So the status of the queue is:
Index -1 0 1 2 3 4
Element 22 33
Position Front Rear
REA R = 2 F RO NT = F RO NT + 1 = 1
Again, delete an element. The element to be deleted is always pointed to by the FRONT pointer. So, 22 is deleted.
The queue status is as follows:
Index -1 0 1 2 3 4
Element 33
Position Front Rear
REA R = 2 F RO NT = F RO NT + 1 = 2
Now, insert new elements 44 and 55 into the queue. The queue status is:
Index -1 0 1 2 3 4 5
Element 33 44 55
Position Front Rear
REA R = 4 F RO NT = 2
Next insert another element, say 66 to the queue. We cannot insert 66 to the queue as the rear crossed the
maximum size of the queue (i.e., 5). There will be queue full signal. The queue status is as follows:
Index -1 0 1 2 3 4 5
Element 33 44 55
Position Front Rear
This difficulty can overcome if we treat queue position with index 0 as a position that comes after position with
index 4 i.e., we treat the queue as a circular queue.

QUEUE as Abstract Data Type:

To realize a queue as an abstract data type (ADT), we need a suitable data structure for storing the
elements in the queue and the functions operating on it. The basic operations performed on the queue
include adding and deleting an element, traversing the queue, checking whether the queue is full or
empty, and finding who is at the front and who is at the rear ends.
A minimal set of operations on a queue is as follows:
1. create()—creates an empty queue, Q
2. add(i,Q)—adds the element i to the rear end of the queue, Q and returns the new queue
3. delete(Q)—takes out an element from the front end of the queue and returns the resulting queue
4. getFront(Q)—returns the element that is at the front position of the queue
5. Is_Empty(Q)—returns true if the queue is empty; otherwise returns false

Realization of Queues Using Arrays: (Operations of Queue ADT)

A queue is a linear data structure that follows the FIFO (First In First Out) principle, where elements are
added from one end called the rear and removed from the other end called the front.
Let us see the implementation of the various operations on the queue using arrays.
Create: This operation should create an empty queue. Here max is the maximum initial size that is
defined.
#define max 50 int Queue[max];
12 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
int Front = Rear = −1;

In addition to a one-dimensional array Queue, we need two more variables, Front and Rear. This
declaration creates an empty queue of size max. The two variables Front and Rear are initialized to
represent an empty queue.
Is_Empty: This function checks whether the queue is empty or not. If Front = Rear, then Is_Empty
returns true, else returns false.
bool Is_Empty()
{
if(Front == Rear) return 1;
else
return 0;
}

Is_Full: This function is used before insertion, the queue must be checked for the Queue_Full state.
When Rear points to the last location of the array, it indicates that the queue is full, that is, there is no
space to accommodate any more elements.
bool Is_Full()
{
if(Rear == max − 1)
return 1;
else
return 0;
}
enQueue (Add): In a queue data structure, enQueue() is a function used to insert a new
element into the queue. In a queue, the new element is always inserted at rear position. The
enQueue() function takes one integer value as a parameter and inserts that value into the queue.
We can use the following steps to insert an element into the queue...

 Step 1 - Check whether queue is FULL. (rear == SIZE-1)

 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate
the function.
 Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and
set queue[rear] = value.

void enQueue(int Element)

{
if(Is_Full())
cout << “Error, Queue is full”; else
Queue[Rear++] = Element;
}

deQueue()(Delete):-
In a queue data structure, deQueue() is a function used to delete an element from the queue. In a queue,
the element is always deleted from front position. The deQueue() function does not take any value as
parameter. We can use the following steps to delete an element from the queue...

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
13 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
 Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then
display queue[front] as deleted element. Then check whether both front and rear are equal
(front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).

void dequeue()
{
if (isEmpty())
{
cout << "Queue Underflow! Nothing to dequeue." << endl;
return;
}
cout << "Removed " << arr[front++] << endl;
if (front = rear)
{
front = rear = -1;
}
}

getFront: The function used to returns the element at the front, but unlike delete, this does not
update the value of Front.
int getFront()
{
if(Is_Empty())
cout << “Sorry, queue is Empty”; else
return(Queue[Front + 1]);
}

Implementation of Queue:-
Queue data structure can be implemented in two ways. They are as follows...

1. Using Array
2. Using Linked List

When a queue is implemented using an array, that queue can organize an only limited number of
elements. When a queue is implemented using a linked list, that queue can organize an unlimited number
of elements.

Queue Datastructure Using Array

A queue data structure can be implemented using one dimensional array. The queue implemented using
array stores only fixed number of data values. The implementation of queue data structure using array is
very simple. Just define a one dimensional array of specific size and insert or delete the values into that
array by using FIFO (First In First Out) principle with the help of variables 'front' and 'rear'. Initially
both 'front' and 'rear' are set to -1. Whenever, we want to insert a new value into the queue, increment
'rear' value by one and then insert at that position. Whenever we want to delete a value from the queue,
then delete the element which is at 'front' position and increment 'front' value by one.

14 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Program Code for queue ADT using arrays:
#include <iostream> void dequeue() int main()
using namespace std; { {
if (isEmpty()) Queue q;
#define SIZE 5 { int choice, value;
cout << "Queue Underflow!
class Queue { Nothing to dequeue." << endl; do
int arr[SIZE]; return; {
int front, rear; } cout << "\nQueue Operations
cout << "Removed " << Menu:\n";
public: arr[front++] << endl; cout << "1. Enqueue (Insert
Queue() if (front > rear) element)\n";
{ { cout << "2. Dequeue
front = rear = -1; (Remove element)\n";
front = -1;
} cout << "3. Display
rear = -1;
} Queue\n";
}
cout << "4. Exit\n";
void display() cout << "Enter your choice: ";
bool isEmpty()
{ cin >> choice;
{
return front == -1 || front > if (isEmpty())
{ switch (choice)
rear;
cout << "Queue is empty." {
}
<< endl; case 1:
return; cout << "Enter value to
bool isFull()
} insert: ";
{
cout << "Queue elements: "; cin >> value;
return rear == SIZE - 1;
for (int i = front; i <= rear; q.enqueue(value);
}
i++) break;
{ case 2:
void enqueue(int value)
cout << arr[i] << " "; q.dequeue();
{
} break;
if (isFull())
cout << endl; case 3:
{
} q.display();
cout << "Queue Overflow!
}; break;
Cannot insert " << value << endl;
case 4:
return;
cout << "Exiting
}
program.\n";
if (front == -1)
break;
{
default:
front = 0;
cout << "Invalid choice!
}
Please try again.\n";
arr[++rear] = value; }
cout << "Inserted " << value } while (choice != 4);
<< endl;
return 0;
}
}

15 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++

Circular Queue:-

In a normal Queue Data Structure, we can insert elements until queue becomes full. But once the queue
becomes full, we can not 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...

Implementation of Circular Queue

To implement a circular queue data structure using an array,

enQueue(value) - Inserting value into the Circular Queue

In a circular queue, enQueue() is a function which is used to insert an element into the circular queue. In
a circular queue, the new element is always inserted at rear position. The enQueue() function takes one

16 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
integer value as parameter and inserts that value into the circular queue. We can use the following steps
to insert an element into the circular queue...

 Step 1 - Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front == rear+1))
 Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate
the function.
 Step 3 - If it is NOT FULL, then check rear == SIZE - 1 && front != 0 if it is TRUE, then set rear =
-1.
 Step 4 - Increment rear value by one (rear++), set queue[rear] = value and check 'front == -1' if
it is TRUE, then set front = 0.

deQueue() - Deleting a value from the Circular Queue

In a circular queue, deQueue() is a function used to delete an element from the circular queue. In a
circular queue, the element is always deleted from front position. The deQueue() function doesn't take
any value as a parameter. We can use the following steps to delete an element from the circular queue...

 Step 1 - Check whether queue is EMPTY. (front == -1 && rear == -1)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
 Step 3 - If it is NOT EMPTY, then display queue[front] as deleted element and increment
the front value by one (front ++). Then check whether front == SIZE, if it is TRUE, then set front
= 0. Then check whether both front - 1 and rear are equal (front -1 == rear), if it TRUE, then set
both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Circular Queue

We can use the following steps to display the elements of a circular queue...

 Step 1 - Check whether queue is EMPTY. (front == -1)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
 Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
 Step 4 - Check whether 'front <= rear', if it is TRUE, then display 'queue[i]' value and increment
'i' value by one (i++). Repeat the same until 'i <= rear' becomes FALSE.
 Step 5 - If 'front <= rear' is FALSE, then display 'queue[i]' value and increment 'i' value by one
(i++). Repeat the same until'i <= SIZE - 1' becomes FALSE.
 Step 6 - Set i to 0.
 Step 7 - Again display 'cQueue[i]' value and increment i value by one (i++). Repeat the same until
'i <= rear' becomes FALSE.
17 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Program code for circular queue operations, using array:
#include <iostream> if (isEmpty()) void display()
using namespace std; { {
#define SIZE 5 front = 0; if (isEmpty())
class CircularQueue rear = 0; {
{ } cout << "Circular
int arr[SIZE]; else Queue is Empty!" << endl;

int front, rear; { return;

public: rear = (rear + 1) % SIZE; }

CircularQueue() } cout << "Circular Queue

{ arr[rear] = value; elements are: ";

front = -1; rear = -1; cout << "Inserted " << value << int i = front;

} endl; while (true)

bool isFull() } {

{ void dequeue() cout << arr[i] << " ";

return (front == (rear + 1) % { if (i == rear)

SIZE); if (isEmpty()) break;

} { i = (i + 1) % SIZE;

bool isEmpty() cout << "Circular Queue is Empty! }

{ Deletion not possible!" << endl; cout << endl;

return (front == -1); return; }

} } };

void enqueue(int value) cout << "Deleted element: " <<

{ arr[front] << endl;

if (isFull()) if (front == rear)

{
{ front = rear = -1;
cout << "Circular Queue is Full! }
else
Insertion not possible!" << endl;
{
return; front = (front + 1) % SIZE;
} }
}

18 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
int main()

CircularQueue q;

int choice, value;

do

cout << "\nMenu:\n";

cout << "1. Enqueue (Insert element)\n";

cout << "2. Dequeue (Remove element)\n";

cout << "3. Display Queue\n";

cout << "4. Exit\n";

cout << "Enter your choice: ";

cin >> choice;

switch (choice)

case 1:

cout << "Enter value to insert: ";

cin >> value;

q.enqueue(value);

break;

case 2:

q.dequeue();

break;

case 3:

q.display();

break;
19 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
case 4:

cout << "Exiting program." << endl;

break;

default:

cout << "Invalid choice! Please try again." << endl;

while (choice != 4);

return 0;

Advantages of Using Circular Queues:

1. Efficient memory utilization by reusing empty spaces.

2. Eliminates the need to shift elements during dequeue operations.

3. Constant time complexity (O(1)) for both enqueue and dequeue.
4. Handles continuous data streams effectively (ideal for buffering).
5. Simplifies wrap-around management of front and rear pointers.
6. Fully utilizes fixed-size array capacity without wasted space.
7. Suitable for real-time systems like CPU scheduling and resource sharing.
DeQueue (or) Deque[ double-ended queue]:

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

The following are the four operations associated with deque:

EnqueueFront()—adds elements at the front end of the queue
EnqueueRear ()—adds elements at the rear end of the queue
DequeueFront ()—deletes elements from the front end of the queue
DequeueRear ()—deletes elements from the rear end of the queue
For stack implementation using deque, EnqueueFront and DequeueFront are used as push and pop
functions, respectively.
20 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Applications of Deque (Double-Ended Queue):
1. Palindrome Checking: Efficiently check if a string or number reads the same forward and
backward by comparing elements from both ends.
2. Implementing Both Stacks and Queues: Deque can act as a stack (LIFO) or a queue (FIFO) by
restricting insertion/deletion to one end or both ends.
3. Task Scheduling: Used in operating systems and real-time systems for scheduling tasks with
priorities.
4. Undo/Redo Operations in Software: Allows easy insertion and deletion of operations from both
ends for maintaining history.
5. Handling Sliding Window Problems: Widely used in algorithms requiring access to elements
within a moving window.
6. Browser History Management: Store and navigate back and forth between web pages efficiently.
7. Memory Buffering and Data Streams: Useful in buffering data where data can be added or
removed from both front and rear.
8. Breadth-First Search (BFS): Helps implement BFS in graphs and trees when flexible ends
manipulation is needed.

Priority Queue:-
A Priority Queue is an abstract data type similar to a regular queue, but where each element is
associated with a priority. Elements with higher priority are served before elements with lower priority,
regardless of the order in which they arrive.
 Unlike normal queues that operate on FIFO (First In First Out) basis, priority queues dequeue
elements in order of their priority.
 The highest priority element is always dequeued first.
 If two elements have the same priority, they may be served according to their order in the queue
(FIFO within the same priority).
Priority queues are used for implementing job scheduling by the operating system where jobs with
higher priority are to be processed first. Another application of priority queues is in simulation systems
where the priority corresponds to event times.
The following are some examples of a priority queue:
1. A list of patients in an emergency room; each patient might be given a ranking that depends on the
severity of the patient’s illness.
2. A list of jobs carried out by a multitasking operating system; each background job is given a priority
level. Suppose in a computer system, jobs are assigned three priorities, namely, P, Q, R as first, second,
and third, respectively. According to the priority of the job, it is inserted at the end of the other jobs
having the same priority.

21 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Linked Lists
 Linked lists and arrays are similar since they both store collections of data.
 An array is a linear data structure that stores a fixed number of elements of the same data type in
contiguous memory locations. Each element is accessible by its index, allowing fast, direct access.
The Disadvantages of arrays are:
 Fixed size: Cannot change size during runtime; resizing requires creating a new array.
 Inefficient insertions/deletions: Adding or removing elements (especially inside the array) is
slow due to shifting data.
 Wasted memory: Overestimating size wastes space; underestimating can cause overflow.
 Same data type only: Can store only one type of data, limiting flexibility.
 No built-in dynamic methods: Lacks convenient functions for resizing or manipulating elements.
 Risk of out-of-bounds access: Accessing invalid indexes can lead to errors or security bugs
To overcome the above drawbacks using linked list
Linked List:-
When we want to work with an unknown number of data values, we use a linked list data
structure to organize that data. The linked list is a linear data structure that contains a sequence of
elements such that each element links to its next element in the sequence. Each element in a
linked list is called "Node".
Each Node contains two parts:
Data: The stored information.
Pointer/Reference: The address of the next node in the sequence.

A linked list Is formed by connecting nodes as shown below.

As shown above, the first node of the linked list is called “head” while the last node is called “Tail”. As we
see, the last node of the linked list will have its next pointer as null since it will not have any memory
address pointed to.
22 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Since each node has a pointer to the next node, data items in the linked list need not be stored at
contiguous locations. The nodes can be scattered in the memory. We can access the nodes anytime as
each node will have an address of the next node.

Primitive Operations on linked lists:

The following are basic operations associated with the linked list as a data structure:
1. Creating an empty list
2. Inserting a node
3. Deleting a node
4. Traversing the list
Some more operations, which are based on the basic operations, are as follows:
5. Searching a node
6. Updating a node
7. Printing the node or list
8. Counting the length of the list
9. Reversing the list
10. Sorting the list using pointer manipulation
11. Concatenating two lists
12. Merging two sorted lists into a third sorted list

Advantages of linked lists:

1. Dynamic size: Linked lists can grow or shrink during runtime by allocating or deallocating
memory as needed, unlike arrays which have a fixed size.
2. Efficient insertions and deletions: Adding or removing elements is fast, especially at the
beginning or end of the list, because only pointers need to be updated, without shifting elements.
3. No memory wastage: Unlike arrays that may have unused pre-allocated space, linked lists use
memory efficiently by only allocating what is needed.
4. Flexibility in memory allocation: Nodes can be stored anywhere in memory because they are
connected through pointers, so no need for contiguous memory blocks.
5. Easy implementation of abstract data structures: Linked lists form the basis for stacks, queues,
and other complex data structures.
6. Efficient rearrangement: Elements can be reordered easily without moving large blocks of data.
7. Scalability: Linked lists can grow or shrink dynamically to accommodate large datasets or
changing data needs.
Disadvantages of linked lists are:
1. Slow access time: Linked lists require traversal from the head to reach a specific element,
resulting in O(n) time complexity for access, unlike arrays' direct indexing.
2. Extra memory usage: Each node stores a pointer/reference to the next node, using more
memory compared to arrays which store only data.
3. No random access: Linked lists do not support direct access by index; elements must be accessed

23 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
sequentially.
4. Reverse traversal difficulty: Singly linked lists do not support backward traversal; doubly linked
lists do but at the cost of additional memory for storing back pointers.

Types of Linked Lists:

Basically we can put linked lists into the following four items:

1. Single Linked List.

2. Single Circular Linked List

3. Double Linked List.

4. Double Circular Linked List.

1. Single Linked List.

In any single linked list, the individual element is called as "Node". Every "Node" contains two
fields, data field, and the next field. The data field is used to store actual value of the node and next field is
used to store the address of next node in the sequence.

Example

From the above image :

1. The list has 4 elements.
2. In the data section it holds the value 10, 25, 18, 55.
3. In the link field, it holds the address of the next node.
4. The variable “head” holds the address of the first node.
5. The “link field” of the last element has “NULL”, to suggest that it is the end of the list.

2. Single Circular Linked List:-

In a single circular linked list, every node consists of two parts: information and address parts.
Address part holds the address of the next node. It allows one way and circular traversal in the list.
There is no end-node in a list, because the last node is linked to the first node.

24 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++

3. Double Linked List:

In a double linked list, every node consists of three parts: one is information part and two address
parts. First address part holds the address of the previous node and the other holds the address of the
next node.

From the above image we can infer following below points:

1. First node prev_link will always be null
2. Last node next_link will always be null
3. Data section holds the data
4. Head pointer always point to the first node

4.Double Circular Linked List.

In a double circular linked list, ever node consists of three parts: information and two address
parts. First address part holds the address of the previous node and the other holds the address of
the next node. The last node next address part holds the first node and the first node previous
node holds the address of last node.

Linked List Abstract Data type:-

The Linked List Abstract Data Type (ADT) is a theoretical concept that defines a sequence of elements
and the operations that can be performed on this sequence, without specifying how the data structure is

25 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
implemented.
An ADT specifies:
What data it stores (a collection or sequence of elements)
What operations are allowed on that data
The behavior of these operations (their effects), but
Not how the data or operations are implemented internally.
Linked List as an ADT:
The linked list ADT models a collection of elements arranged in a linear order, where each element points
to the next, enabling dynamic and flexible storage.
Core Operations of the Linked List ADT:
Insertion: Add elements at the beginning, end, or specific positions.
Deletion: Remove elements from beginning, end, or specific positions.
Traversal: Visit each element sequentially to access or modify data.
Search: Find an element by its value or position.
Size: Determine the number of elements in the list.
Check empty: Determine if the list has zero elements.

Operations on Single Linked List

The following operations are performed on a Single Linked List

1. Insertion
2. Deletion
3. Display

Before we implement actual operations, first we need to set up an empty list. First, perform the following
steps before implementing actual operations.

 Step 1 - Include all the header files which are used in the program.
 Step 2 - Declare all the user defined functions.
 Step 3 - Define a Node structure with two members data and next
 Step 4 - Define a Node pointer 'head' and set it to NULL.
 Step 5 - Implement the main method by displaying operations menu and make suitable function
calls in the main method to perform user selected operation.

1. Insertion
In a single linked list, the insertion operation can be performed in three ways. They are as follows...

1. Inserting At Beginning of the list

2. Inserting At End of the list
3. Inserting At Specific location in the list

26 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Inserting At Beginning of the list
We can use the following steps to insert a new node at beginning of the single linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
 Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...

 Step 1 - Create a newNode with given value and newNode → next as NULL.
 Step 2 - Check whether list is Empty (head == NULL).
 Step 3 - If it is Empty then, set head = newNode.
 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next is equal to NULL).
 Step 6 - Set temp → next = newNode.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.
 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
 Step 5 - Keep moving the temp to its next node until it reaches to the node after which we want to
insert the newNode (until temp1 → data is equal to location, here location is the node value after
which we want to insert the newNode).

27 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
 Step 6 - Every time check whether temp is reached to last node or not. If it is reached to last node
then display 'Given node is not found in the list!!! Insertion not possible!!!' and terminate the
function. Otherwise move the temp to next node.
 Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

2. Deletion
In a single linked list, the deletion operation can be performed in three ways. They are as follows...

1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the
function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Check whether list is having only one node (temp → next == NULL)
 Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list conditions)
 Step 6 - If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the
function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
 Step 4 - Check whether list has only one Node (temp1 → next == NULL)
 Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the function.
(Setting Empty list condition)
 Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node. Repeat the
same until it reaches to the last node in the list. (until temp1 → next == NULL)
 Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list...

28 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
 Step 1 - Check whether list is Empty (head == NULL)
 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate the
function.
 Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and initialize
'temp1' with head.
 Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to the last
node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.
 Step 5 - If it is reached to the last node then display 'Given node not found in the list! Deletion
not possible!!!'. And terminate the function.
 Step 6 - If it is reached to the exact node which we want to delete, then check whether list is
having only one node or not
 Step 7 - If list has only one node and that is the node to be deleted, then set head = NULL and
delete temp1 (free(temp1)).
 Step 8 - If list contains multiple nodes, then check whether temp1 is the first node in the list
(temp1 == head).
 Step 9 - If temp1 is the first node then move the head to the next node (head = head → next) and
delete temp1.
 Step 10 - If temp1 is not first node then check whether it is last node in the list (temp1 → next
== NULL).
 Step 11 - If temp1 is last node then set temp2 → next = NULL and delete temp1 (free(temp1)).
 Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 → next and
delete temp1 (free(temp1)).

Displaying a Single Linked List

We can use the following steps to display the elements of a single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
 Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last node
 Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data ---> NULL).

Below is the code for SLL where the element is insert, delete and display from the list.
#include <iostream>
using namespace std;

class LinkedList {
private:
struct Node {
int data;
Node* next;
};
Node* head;

29 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
public:
LinkedList() : head(nullptr) {}

void insertAtBeginning(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = head;
head = newNode;
cout << "\nOne node inserted!!!\n";
}

void insertAtEnd(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
}
cout << "\nOne node inserted!!!\n";
}

void insertBetween(int value, int loc1, int loc2) {

Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
newNode->next = nullptr;
head = newNode;
} else {
Node* temp = head;
30 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
while (temp != nullptr && temp->data != loc1 && temp->data != loc2)
temp = temp->next;
if (temp != nullptr) {
newNode->next = temp->next;
temp->next = newNode;
} else {
cout << "\nPositions not found. Node not inserted!\n";
delete newNode;
return;
}
}
cout << "\nOne node inserted!!!\n";
}

void removeBeginning() {
if (head == nullptr) {
cout << "\nList is Empty!!!\n";
} else {
Node* temp = head;
head = head->next;
delete temp;
cout << "\nOne node deleted!!!\n\n";
}
}

void removeEnd() {
if (head == nullptr) {
cout << "\nList is Empty!!!\n";
} else if (head->next == nullptr) {
delete head;
head = nullptr;
cout << "\nOne node deleted!!!\n\n";
} else {
Node* temp1 = head;
31 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Node* temp2 = nullptr;
while (temp1->next != nullptr) {
temp2 = temp1;
temp1 = temp1->next;
}
temp2->next = nullptr;
delete temp1;
cout << "\nOne node deleted!!!\n\n";
}
}

void removeSpecific(int delValue) {

if (head == nullptr) {
cout << "\nList is Empty!!!\n";
return;
}
if (head->data == delValue) {
Node* temp = head;
head = head->next;
delete temp;
cout << "\nOne node deleted!!!\n\n";
return;
}
Node* temp1 = head->next;
Node* temp2 = head;
while (temp1 != nullptr && temp1->data != delValue) {
temp2 = temp1;
temp1 = temp1->next;
}
if (temp1 == nullptr) {
cout << "\nGiven node not found in the list!!!\n";
return;
}
temp2->next = temp1->next;
32 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
delete temp1;
cout << "\nOne node deleted!!!\n\n";
}

void display() {
if (head == nullptr) {
cout << "\nList is Empty\n";
} else {
Node* temp = head;
cout << "\n\nList elements are - \n";
while (temp != nullptr) {
cout << temp->data << " ---> ";
temp = temp->next;
}
cout << "NULL\n";
}
}

~LinkedList() {
Node* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
};

int main() {
LinkedList list;
int choice, value, choice1, loc1, loc2;
while (true) {
mainMenu:
cout << "\n\n****** MENU ******\n1. Insert\n2. Display\n3. Delete\n4. Exit\nEnter your choice: ";
33 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the value to be inserted: ";
cin >> value;
while (true) {
cout << "Where you want to insert: \n1. At Beginning\n2. At End\n3. Between\nEnter your
choice: ";
cin >> choice1;
switch (choice1) {
case 1:
list.insertAtBeginning(value);
break;
case 2:
list.insertAtEnd(value);
break;
case 3:
cout << "Enter the two values between which you want to insert: ";
cin >> loc1 >> loc2;
list.insertBetween(value, loc1, loc2);
break;
default:
cout << "\nWrong Input!! Try again!!!\n\n";
goto mainMenu;
}
break;
}
break;
case 2:
list.display();
break;
case 3:
cout << "How do you want to delete: \n1. From Beginning\n2. From End\n3. Specific\nEnter
your choice: ";
34 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
cin >> choice1;
switch (choice1) {
case 1:
list.removeBeginning();
break;
case 2:
list.removeEnd();
break;
case 3:
cout << "Enter the value which you want to delete: ";
cin >> loc2;
list.removeSpecific(loc2);
break;
default:
cout << "\nWrong Input!! Try again!!!\n\n";
goto mainMenu;
}
break;
case 4:
exit(0);
default:
cout << "\nWrong input!!! Try again!!\n\n";
}
}
return 0;
}
Double Linked List:
In a doubly linked list (DLL), each node has two link fields to store information about the one to
the next and also about the one ahead of the node. Hence, each node has knowledge of its
successor and also its predecessor. In DLL, from every node, the list can be traversed in both the
directions.

35 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Creation of doubly Linked List:
Creation of DLL has the same procedure as that of SLL.The only difference is that each node must
be linked to both its predecessor (previous) and successor (next).

class DLLNode
{
public:
int Data;
DLLNode *Prev, *Next;
DLLNode( )
{
Prev = Next = Null;
}
};

class DList
{
private:
DLLNode *Head, *Tail;
public:
DList()
{
Head = Tail = Null;
}
};
Deletion of a node from a doubly Linked List:
Deleting from a DLL needs the deleted node’s predecessor, if any, to be pointed to the deleted
node’s successor. In addition, the successor, if any, should be set to point to the predecessor node.

The core steps involved in this process are the following:

(NewNode is curr) (curr->Prev)->Next = curr->Next;
(curr->Next)->Prev = curr->Prev; delete curr;

Insertion of a node in a doubly Linked List:

Now, let us discuss inserting a node in DLL. To insert a node, say Current, we have to modify four
links as each node points to its predecessor as well as successor. Let us assume that the node
Current is to be inserted in between the two nodes say node1 and node2. We have to modify the
following links:
node1->Next, node2->Prev, Current->Prev, and Current->Next
When the Current node is inserted in between node1 and node2, node1’s successor node changes.
Hence, we need to modify node1->Next. For the node node2, its predecessor changes. Therefore,
36 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
we need to modify node2->Prev

Current is a new node to be inserted. We need to set both its predecessor and successor by setting
the links as Current->Prev and Current->Next
After the insertion of Current, the resultant modified links should be shown as in below figure

Hence, to modify the links, the statements would be

To modify node1->Next we use the operation

node1->Next = Current;
To modify node2->Prev we use the operation

node2->Prev = Current;
To set curr->Next, we use the operation

Current->Next = node2;
To set curr->Prev, we use the operation

Current->Prev = node1;
Let us consider the insertion of a node given one node before or after which the node is to be
inserted, say before node2. Then, the four statements could be
(node2->Prev)->Next = Current;
Current->Prev = node2->Prev;
Current->Next = node2;
node2->Prev = Current;

Displaying of doubly Linked List:

Given a head pointer to the DLL; traversal is the same as that of an SLL. The advantage of DLL over
SLL is, given a pointer P pointing to any of the nodes of list, the list can be traversed only in one
(forward) direction in SLL, whereas the list can be traversed in both (forward and backward)
directions in DLL.
37 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Below is the code for DLL where the element is insert, delete and display from the list.
#include <iostream>
using namespace std;

class DoublyLinkedList {
private:
struct Node {
int data;
Node* next;
Node* prev;
};
Node* head;

public:
DoublyLinkedList() : head(nullptr) {}

void insertAtBeginning(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->prev = nullptr;
newNode->next = head;
if (head != nullptr)
head->prev = newNode;
head = newNode;
cout << "\nOne node inserted!!!\n";
}

void insertAtEnd(int value)

{
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (head == nullptr) {
newNode->prev = nullptr;

38 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
cout << "\nOne node inserted!!!\n";
}

void insertBetween(int value, int loc1, int loc2)

{
Node* newNode = new Node();
newNode->data = value;
if (head == nullptr) {
newNode->next = nullptr;
newNode->prev = nullptr;
head = newNode;
} else {
Node* temp = head;
while (temp != nullptr && temp->data != loc1 && temp->data != loc2)
temp = temp->next;
if (temp != nullptr) {
newNode->next = temp->next;
newNode->prev = temp;
if (temp->next != nullptr)
temp->next->prev = newNode;
temp->next = newNode;
}
else
{
cout << "\nPositions not found. Node not inserted!\n";
delete newNode;
39 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
return;
}
}
cout << "\nOne node inserted!!!\n";
}

void removeBeginning()
{
if (head == nullptr)
{
cout << "\nList is Empty!!!\n";
}
else
{
Node* temp = head;
head = head->next;
if (head != nullptr)
head->prev = nullptr;
delete temp;
cout << "\nOne node deleted!!!\n\n";
}
}

void removeEnd()
{
if (head == nullptr)
{
cout << "\nList is Empty!!!\n";
}
else if (head->next == nullptr)
{
delete head;
head = nullptr;
cout << "\nOne node deleted!!!\n\n";
40 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
}
Else
{
Node* temp = head;
while (temp->next != nullptr)
temp = temp->next;
temp->prev->next = nullptr;
delete temp;
cout << "\nOne node deleted!!!\n\n";
}
}

void removeSpecific(int delValue)

{
if (head == nullptr)
{
cout << "\nList is Empty!!!\n";
return;
}
Node* temp = head;
while (temp != nullptr && temp->data != delValue)
temp = temp->next;
if (temp == nullptr) {
cout << "\nGiven node not found in the list!!!\n";
return;
}
if (temp->prev != nullptr)
temp->prev->next = temp->next;
else
head = temp->next;

if (temp->next != nullptr)
temp->next->prev = temp->prev;

41 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
delete temp;
cout << "\nOne node deleted!!!\n\n";
}

void display()
{
if (head == nullptr)
{
cout << "\nList is Empty\n";
}
else
{
Node* temp = head;
cout << "\n\nList elements are - \n";
while (temp != nullptr) {
cout << temp->data << " <--> ";
temp = temp->next;
}
cout << "NULL\n";
}
}

~DoublyLinkedList()
{
Node* temp;
while (head != nullptr)
{
temp = head;
head = head->next;
delete temp;
}
}
};

42 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
int main()
{
DoublyLinkedList list;
int choice, value, choice1, loc1, loc2;
while (true) {
mainMenu:
cout << "\n\n****** MENU ******\n1. Insert\n2. Display\n3. Delete\n4. Exit\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter the value to be inserted: ";
cin >> value;
while (true) {
cout << "Where you want to insert: \n1. At Beginning\n2. At End\n3. Between\nEnter your
choice: ";
cin >> choice1;
switch (choice1) {
case 1:
list.insertAtBeginning(value);
break;
case 2:
list.insertAtEnd(value);
break;
case 3:
cout << "Enter the two values between which you want to insert: ";
cin >> loc1 >> loc2;
list.insertBetween(value, loc1, loc2);
break;
default:
cout << "\nWrong Input!! Try again!!!\n\n";
goto mainMenu;
}
break;
}
43 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
break;
case 2:
list.display();
break;
case 3:
cout << "How do you want to delete: \n1. From Beginning\n2. From End\n3. Specific\nEnter
your choice: ";
cin >> choice1;
switch (choice1) {
case 1:
list.removeBeginning();
break;
case 2:
list.removeEnd();
break;
case 3:
cout << "Enter the value which you want to delete: ";
cin >> loc2;
list.removeSpecific(loc2);
break;
default:
cout << "\nWrong Input!! Try again!!!\n\n";
goto mainMenu;
}
break;
case 4:
exit(0);
default:
cout << "\nWrong input!!! Try again!!\n\n";
}
}
return 0;
}

44 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Comparison of sequential and Linked Organizations:
Sequential organization:
1. Successive elements of a list are stored a fixed distance apart.
2. It provides static allocation, which means, the space allocation done by a compiler once cannot
be changed during execution, and the size has to be known in advance.
3. As individual objects are stored a fixed distance apart.
4. Insertion and deletion of objects in between the list require a lot of data movement.
5. It is space inefficient for large objects with frequent insertions and deletions.
6. An element need not know/store and keep the address of its successive element.

Linked organization:
1. Elements can be placed anywhere in the memory.
2. Dynamic allocation (size need not be known in advance), that is, space allocation as per need
can be done during execution.
3. As objects are not placed in consecutive locations at a fixed distance apart, random access to
elements is not possible.
4. Insertion and deletion of objects do not require any data shifting.
5. It is space efficient for large objects with frequent insertions and deletions.
Each element in general is a collection of data and a link. At least one link field is a must.

Representation of Stack using Linked list:

A stack data structure can be implemented by using a linked list data structure. The stack
implemented using linked list can work for an unlimited number of values. That means, stack
implemented using linked list works for the variable size of data. So, there is no need to fix the size
at the beginning of the implementation. The Stack implemented using linked list can organize as
many data values as we want.
In linked list implementation of a stack, every new element is inserted as 'top' element. That
means every newly inserted element is pointed by 'top'. Whenever we want to remove an element
from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its previous
node in the list. The next field of the first element must be always NULL.Stack Operations.

45 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Example

In the above example, the last inserted node is 99 and the first inserted node is 25. The order of elements
inserted is 25, 32,50 and 99.
 push(): Insert a new element into the stack (i.e just insert a new element at the beginning of the
linked list.)
 pop(): Return the top element of the Stack (i.e simply delete the first element from the linked
list.)
 peek(): Return the top element.
 display(): Print all elements in Stack.

Below is the code for Stack implementation using linked list

#include <iostream>
using namespace std;

class Stack {
private:
struct Node {
int data;
Node* next;
};
Node* top;

public:
Stack() : top(nullptr) {}

void push(int value) {

Node* newNode = new Node();
46 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
newNode->data = value;
newNode->next = top;
top = newNode;
cout << "\nInsertion is Success!!!\n";
}

void pop() {
if (top == nullptr) {
cout << "\nStack is Empty!!!\n";
} else {
Node* temp = top;
cout << "\nDeleted element: " << temp->data << endl;
top = temp->next;
delete temp;
}
}

void display() {
if (top == nullptr) {
cout << "\nStack is Empty!!!\n";
} else {
Node* temp = top;
while (temp != nullptr) {
cout << temp->data;
if (temp->next != nullptr) cout << "--->";
temp = temp->next;
}
cout << "--->NULL\n";
}
}

~Stack() {
Node* temp;
while (top != nullptr) {
47 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
temp = top;
top = top->next;
delete temp;
}
}
};

int main() {
Stack stack;
int choice, value;

cout << "\n:: Stack using Linked List ::\n";

while (true) {
cout << "\n****** MENU ******\n";
cout << "1. Push\n2. Pop\n3. Display\n4. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter the value to be inserted: ";
cin >> value;
stack.push(value);
break;
case 2:
stack.pop();
break;
case 3:
stack.display();
break;
case 4:
exit(0);
default:
cout << "\nWrong selection!!! Please try again!!!\n";
48 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
}
}
return 0;
}

Representation of Queue using Linked list:

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). The Queue implemented using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by 'rear' and the first
node is always pointed by 'front'.

Example

In above 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.

Below is the code for Queue implementation using linked list

#include <iostream>
using namespace std;

class Queue {
private:
struct Node {
int data;
Node* next;
};
Node* front;
Node* rear;

49 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++

public:
Queue() : front(nullptr), rear(nullptr) {}

void insert(int value) {

Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (front == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
cout << "\nInsertion is Success!!!\n";
}

void remove() {
if (front == nullptr) {
cout << "\nQueue is Empty!!!\n";
} else {
Node* temp = front;
front = front->next;
cout << "\nDeleted element: " << temp->data << "\n";
delete temp;
if (front == nullptr)
rear = nullptr;
}
}
void display() {
if (front == nullptr) {
cout << "\nQueue is Empty!!!\n";
} else {
Node* temp = front;
50 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
while (temp != nullptr) {
cout << temp->data;
if (temp->next != nullptr) cout << "--->";
temp = temp->next;
}
cout << "--->NULL\n";
}
}

~Queue() {
Node* temp;
while (front != nullptr) {
temp = front;
front = front->next;
delete temp;
}
rear = nullptr;
}
};
int main() {
Queue queue;
int choice, value;

cout << "\n:: Queue Implementation using Linked List ::\n";

while (true) {
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 inserted: ";
cin >> value;
51 | Page Rajeshuni Prashanth
M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
queue.insert(value);
break;
case 2:
queue.remove();
break;
case 3:
queue.display();
break;
case 4:
exit(0);
default:
cout << "\nWrong selection!!! Please try again!!!\n";
}
}
return 0;
}

Representation of Sparse Matrix:-

Sparse matrix is a matrix which contains very few non-zero elements
In computer programming, a matrix can be defined with a 2-dimensional array. Any array with 'm'
columns and 'n' rows represent a m X n matrix. There may be a situation in which a matrix contains more
number of ZERO values than NON-ZERO values. Such matrix is known as sparse matrix.
When a sparse matrix is represented with a 2-dimensional array, we waste a lot of space to
represent that matrix. For example, consider a matrix of size 100 X 100 containing only 10 non-zero
elements. In this matrix, only 10 spaces are filled with non-zero values and remaining spaces of the
matrix are filled with zero. That means, totally we allocate 100 X 100 X 2 = 20000 bytes of space to store
this integer matrix. And to access these 10 non-zero elements we have to make scanning for 10000 times.
To make it simple we use the following sparse matrix representation.

Sparse Matrix Representations

A sparse matrix can be represented by using TWO representations, those are as follows...
1. Triplet Representation (Array Representation)
2. Linked Representation

52 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Triplet Representation (Array Representation)
In this representation, we consider only non-zero values along with their row and column index values.
In this representation, the 0th row stores the total number of rows, total number of columns and the total
number of non-zero values in the sparse matrix.

For example, consider a matrix of size 5 X 6 containing 6 number of non-zero values. This matrix can be
represented as shown in the image...

In above example matrix, there are only 6 non-zero elements ( those are 9, 8, 4, 2, 5 & 2) and matrix size
is 5 X 6. We represent this matrix as shown in the above image. Here the first row in the right side table is
filled with values 5, 6 & 6 which indicates that it is a sparse matrix with 5 rows, 6 columns & 6 non-zero
values. The second row is filled with 0, 4, & 9 which indicates the non-zero value 9 is at the 0th-row 4th
column in the Sparse matrix. In the same way, the remaining non-zero values also follow a similar
pattern.

Linked Representation
In linked representation, we use a linked list data structure to represent a sparse matrix. In this linked
list, we use two different nodes namely header node and element node. Header node consists of three
fields and element node consists of five fields as shown in the image...

53 | Page Rajeshuni Prashanth

M.C.A TSSET
BSC MPCS III SEM DATA STRUCTURES USING C++
Consider the above same sparse matrix used in the Triplet representation. This sparse matrix can be
represented using linked representation as shown in the below image...

In the above representation, H0, H1,..., H5 indicates the header nodes which are used to represent
indexes. Remaining nodes are used to represent non-zero elements in the matrix, except the very first
node which is used to represent abstract information of the sparse matrix (i.e., It is a matrix of 5 X 6 with
6 non-zero elements).

In this representation, in each row and column, the last node right field points to its respective header
node.

54 | Page Rajeshuni Prashanth

M.C.A TSSET