Program on queue using array

#include <stdio.h>

#define MAX_SIZE 5 // Define the maximum size of the queue

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

// Function prototypes
void enqueue(int);
int dequeue();
void display();
int isEmpty();
int isFull();

int main() {
int choice, data;

while (1) {
printf("\n-------- Queue Program Menu --------\n");
printf("1. Enqueue (Insert)\n");
printf("2. Dequeue (Delete)\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter data to insert: ");
scanf("%d", &data);
enqueue(data);
break;
case 2:
if (!isEmpty()) {
data = dequeue();
printf("Dequeued element: %d\n", data);
} else {
printf("Queue is Empty\n");
}
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}

// Check if the queue is empty

int isEmpty() {
if (front == -1 || front > rear)
return 1; // True, the queue is empty
else
return 0; // False, the queue is not empty
}

// Check if the queue is full

int isFull() {
if (rear == MAX_SIZE - 1)
return 1; // True, the queue is full
else
return 0; // False, the queue is not full
}

// Add an element to the queue (Enqueue)

void enqueue(int element) {
if (isFull()) {
printf("Queue Overflow\n");
} else {
if (front == -1)
front = 0; // Set front to 0 for the first element
rear++;
queue[rear] = element;
printf("Inserted %d\n", element);
}
}

// Remove an element from the queue (Dequeue)

int dequeue() {
int element;
if (isEmpty()) {
// This case is handled in the main function
return -1;
} else {
element = queue[front];
front++;
if (front > rear) { // If all elements are dequeued, reset queue
front = -1;
rear = -1;
}
return element;
}
}

// Display all elements in the queue

void display() {
int i;
if (isEmpty()) {
printf("Queue is Empty\n");
} else {
printf("Queue elements are: ");
for (i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}
 LinkedList
Whenwe want to work with unknown number of data values,we use a linked list data structure to
organize that data. Linked list is a linear data structure that contains sequence of elements
suchthat each element links to its next element in the sequence. Each element in a linked list is
calledas "Node".
Eachnode of the linked list has at least the following two elements: [Link] member(s) being
stored in the list.
[Link] or link to the next element in the list.

Thelast node in the list contains a null pointer to indicate that it is the end or tail of the list.
Aheader node (head) is a special node that is attached at the beginning of the linked list

Comparison of Sequential and Linked Organizations

Sequential organization The features of this organization are the following:
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, we can access any element
randomly.
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 The features of this organization include the following:

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.
6. Each element in general is a collection of data and a link. At least one link field is a must.
7. Every element keeps the address of its successor element in a link field.
8. Linked organization needs the use of pointers and dynamic memory allocation.

19

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Types of Linked List
There are three common types of Linked List.

1. Single Linked List

2. Double Linked List
3. Circular Linked List

Single Linked List

Simply a list is a sequence of data, and linked list is a sequence of data linked with each other.
The formal definition of a single linked list is as follows...

Single linked list is a sequence of elements in which every element has link to its next
element in the sequence.

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

The graphical representation of a node in a single linked list is as follows...

Example

Operations
Inasinglelinked list we perform the following operations...
1. Insertion
2. Deletion
3. Display

20

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

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

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. newNode → data=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 newNode → data=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
(temp=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. newNode → data=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

21

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 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).
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'.
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.
22

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Step4:Check whether list has only one Node (temp1 → next == NULL)
Step5:Ifit is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
Step6:Ifit 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)
Step7:Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

Wecanuse the following steps to delete a specific node from the single linked list...
Step1:Check whether list is Empty (head == NULL)
Step2:Ifit is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step3:Ifit is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step4: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.
Step5:Ifit is reached to the last node then display 'Given node not found in the list!
Deletion not possible!!!'. And terminate the function.
Step6:Ifit is reached to the exact node which we want to delete, then check
whether list is having only one node or not
Step7:Iflist has only one node and that is the node to be deleted, then
set head = NULL and delete temp1 and temp2.
Step8:Iflist contains multiple nodes, then check whether temp1->data is equal to
value or position then stop traversing value (temp1->data==value) &
(temp1=temp1->next)
Step9:temp2 is holding the previous node address of the node which has to be
deleted and temp1 is holding the address of deleting the node.
Step10:Change the address of the node which pointed by temp2 with the node
which is pointed by temp1 (temp2 → next = temp1 → next) .

23

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

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.
(temp=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).

Program on single Linked List:

24

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 Stack using Linked List
The major problemwith the stack implemented using array is,it works only for fixed
number of data values. That means the amount of data must be specified at the
beginning of the implementation itself. Stack implemented using array is not suitable,
when we don't know the size of data which we are going to use.A stack data structure
can be implemented by using linked list data structure.

The stack implemented using linked list can work for unlimited number of values. That
means, stack implemented using linked list works for 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 next node in the list. The next field of the first element must be
always NULL.
Example

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

Operations
1. push(value) - Inserting an element into the Stack
2. pop() - Deleting an Element from a Stack
3. display() - Displaying stack of elements

30

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

push(value) - Inserting an element into the Stack
We can use the following steps to insert a new node into the stack...

Step 1: Create a newNode with given value.

Step 2: Check whether stack is Empty (top == NULL)
Step 3: If it is Empty, then set newNode → next = NULL.
Step 4: If it is Not Empty, then set newNode → next = top.
Step 5: Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

Step 1: Check whether stack is Empty (top == NULL).

Step 2: If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!"
and terminate the function
Step 3: If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
Step 4: Then set 'top = top → next'.
Step 7: Finally, delete 'temp' (free(temp)).

display() - Displaying stack of elements

Wecanuse the following steps to display the elements (nodes) of a stack...

Step1:Check whether stack is Empty (top == NULL).

Step2:Ifit is Empty, then display 'Stack is Empty!!!' and terminate the function.
Step3:Ifit is Not Empty, then define a Node pointer 'temp' and initialize with top.
Step4:Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack (temp → next != NULL).
Step4:Finally! Display 'temp → data ---> NULL'.

31

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 Queue using Linked List
The major problemwith thequeue implementedusing array is, It will work for only fixed
number of data. That means, the amount of data must be specified in the beginning itself.

Queue using 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 linked list data structure
The queue which is implemented using linked list can work for unlimited number of values
That means, queue using linked list can work for variable size of data (No need to fix the
size at 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.
Operations

1. Insert / enQueue(value) - Inserting an element into the Queue

2. Delete / deQueue() - Deleting an Element from Queue
3. display() - Displaying the elements of Queue

Insert / 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.

35

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Delete / 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)).

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 4: Finally! Display 'temp → data ---> NULL'.

Program on Queue using linked list

36

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 Double Linked List
In a single linked list, everynodehas link to its next nodein the sequence. So, we can traverse from
one node to other node only in one direction and we cannot traverse back. We can solve this kind
of problem by using double linked list. Double linked list can be defined as follows...

Double linked list is a sequence of elements in which every element has links to its previous
element and next element in the sequence.

In double linked list, every node has link to its previous node and next node. So, we can traverse
forward by using next field and can traverse backward by using previous field. Every node in a
double linked list contains three fields and they are shown in the following figure...

Here, 'link1' field is used to store the address of the previous node in the sequence, 'link2' field is
used to store the address of the next node in the sequence and 'data' field is used to store the
actual value of that node.

Example

Operations

In a double linked list we perform the following operations...

1. Insertion
2. Deletion
3. Display

Insertion

39

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

In a double 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

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the double linked list...
Step 1: Create a newNode with given value and newNode → previous as NULL .
Step 2: Check whether list is Empty (head == NULL)
Step 3: If it is Empty then initialise with head ( head= newNode),
assign NULL to newNode → next (newNode → next=NULL)
Step 4: If it is not Empty then, assign head to
newNode → next (newNode → next = head) and newNode to head
(head= newNode).

Inserting At End of the list

We can use the following steps to insert a new node at end of the double 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 assign NULL to newNode → previous
( newNode ->previous =NULL) and ( head= newNode).
Step 4: If it is not Empty, then, define a node pointer temp and initialize
with head.(temp=head)
Step 5: Keep moving the temp to its next node until it reaches to the last node in the
list (until temp → next == NULL).
Step 6: Assign (temp → next = newNode )and ( newNode → previous=temp )
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 double 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, assign newNode → previous=NULL &

newNode → next=NULL and head=newNode..

40

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Step 4: If it is not Empty then, define two node pointers temp1 & temp2 and
initialize temp1 with head. ( temp1 = head)
Step 5: Keep moving the temp1 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).
Step 6: Every time check whether temp1 is reached to the last node. If it is reached to the
last node then display 'Given node is not found in the list!!! Insertion not
possible!!!' and terminate the function. Otherwise move the temp1 to next node.
Step 7: Assign temp1 → next = temp2 , temp1 → next =newNode ,
newNode → previous=temp1, newNode → next =temp2
and temp2 → previous= newNode.

Deletion
In a double linked list, the deletion operation can be performed in three ways 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 double 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 set head=head->next (i.e. second node address will
become the first node) and update head->previous=NULL.

Deleting from End of the list

We can use the following steps to delete a node from end of the double 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 has only one Node (temp → previous and temp → next both
are NULL)
41

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Step 5: If it is TRUE, then assign NULL to head and delete temp. And terminate from the
function. (Setting Empty list condition)
Step 6: If it is FALSE, then keep moving temp until it reaches to the last node in the list.
(until temp → next is equal to NULL)
Step 7: Assign NULL to temp → previous → next and delete temp.
Deleting a Specific Node from the list
We can use the following steps to delete a specific node from the double 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: Keep moving the temp until it reaches to the exact node to be deleted or to the
last 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 fuction.
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 which is to be deleted then
set head to NULL and delete temp (free(temp)).
Step 8: If list contains multiple nodes, then check whether temp is the first node in the
list (temp == head).
Step 9: If temp is the first node, then move the head to the next node (head = head →
next), set head of previous to NULL (head → previous = NULL) and delete temp.
Step 10: If temp is not the first node, then check whether it is the last node in the list
(temp → next == NULL).
Step 11: If temp is the last node then set temp of previous of next to NULL
(temp → previous → next = NULL) and delete temp (free(temp)).
Step 12: If temp is not the first node and not the last node,
then
set temp of previous of next to temp of next (temp → previous → next = temp →
next), temp of next of previous to temp of previous (temp → next → previous = temp →
previous) and delete temp (free(temp)).

42

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Displaying a Double Linked List
We can use the following steps to display the elements of a double linked list...
Step1:Check whether list is Empty (head == NULL)
Step2:Ifit is Empty, then display 'List is Empty!!!' and terminate the function.
Step3:Ifit is not Empty, then define a Node pointer 'temp' and initialize with head.
Step4:Display 'NULL <--- '.
Step5:Keep displaying temp → data with an arrow (<===>) until temp reaches to the
last node
Step6:Finally, display temp → data with arrow pointing to NULL
(temp → data ---> NULL).

Program on Double linked list

43

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 Circular Linked List
In single linked list, every node points to its next node in the sequence and the last node points
NULL. But in circular linked list, every node points to its next node in the sequence but the last
node points to the first node in the list.

Circular linked list is a sequence of elements in which every element has link to its next
element in the sequence and the last element has a link to the first element in the sequence.

That means circular linked list is similar to the single linked list except that the last node points
to the first node in the list
Example

Operations
In a double linked list we perform the following operations...
1. Insertion
2. Deletion
3. Display

Insertion
In a double 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
48

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 3. Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the circular 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 head = newNode and newNode→next = head .
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

(until 'temp → next == head').

Step 6: Set 'newNode → next =head', 'head = newNode' and 'temp → next = head'.

Inserting At End of the list

We can use the following steps to insert a new node at end of the circular 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 head = newNode and newNode → next = head.
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 == head).
Step 6: Set temp → next = newNode and newNode → next = head.

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 circular 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 head = newNode and newNode → next = head.
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).
Step 6: Every time check whether temp is reached to the 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: If temp is reached to the exact node after which we want to insert the newNode

49

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

 then check whether it is last node (temp → next == head).
Step 8: If temp is last node then set temp → next = newNode and
newNode → next = head.
Step 8: If temp is not last node then set newNode → next = temp → next and
temp → next = newNode.

Deletion
In a circular linked list, deletion operation can be performed in three ways those 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 circular 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 both
'temp1' and 'temp2' with head.
Step 4: Check whether list is having only one node (temp1 → next == head)
Step 5: If it is TRUE then set head = NULL and delete temp1 (Setting Empty list
conditions)
Step 6: If it is FALSE move the temp1 until it reaches to the last node.
(until temp1 → next == head )
Step 7: Then set head = temp2 → next, temp1 → next = head and delete temp2.
Deleting from End of the list

We can use the following steps to delete a node from end of the circular 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 == head)
50

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Step 5: If it is TRUE. Then, set head = NULL and delete temp1. And terminate from 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 temp1 reaches to the last node in the list.
(until temp1 → next == head)
Step 7: Set temp2 → next = head and delete temp1.
Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the circular 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: 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 (temp1 → next == head)
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 set temp2 = head and keep moving temp2 to
its next node until temp2 reaches to the last node.
Then set head = head → next, temp2 → next = head and delete temp1.
Step 10: If temp1 is not first node then check whether it is last node in the list
(temp1 → next == head).
Step 11: If temp1 is last node then set temp2 → next = head 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)).
51

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Displaying a circular Linked List
Wecanuse the following steps to display the elements of a circular linked list...
Step1:Check whether list is Empty (head == NULL)
Step2:Ifit is Empty, then display 'List is Empty!!!' and terminate the function.
Step3:Ifit is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step4:Keep displaying temp → data with an arrow (--->) until temp reaches to the last

node
Step5:Finally display temp → data with arrow pointing to head → data

Dynamic memory allocation The process of allocating memory at run-time is known as

dynamic memory allocation.
new operator The new operator creates a new dynamic object of a specified type and
returns a pointer that points to this new object.
delete operator To destroy a dynamically allocated variable/object and free the space for
the object, the operator delete is used.

52

Downloaded by saraswati laxminarayan (saraswatil73@[Link])

Program on Circular Queue using c
#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Define the maximum size of the queue

int cqueue_arr[MAX];
int front = -1;
int rear = -1;

void insert(int item);

void deletion();
void display();

int main() {
int choice, item;
while (1) {
printf("\[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("\nEnter your choice : ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("\nInput the element for insertion : ");
scanf("%d", &item);
insert(item);
break;
case 2:
deletion();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("\nWrong choice\n");
}
}
return 0;
}

void insert(int item) {

if ((front == 0 && rear == MAX - 1) || (front == rear + 1)) {
printf("Queue Overflow\n"); // Check if the queue is full
 return;
}
if (front == -1) { // Check if the queue is empty on the first insert
front = 0;
rear = 0;
} else {
rear = (rear + 1) % MAX; // Use modulo arithmetic to wrap around
}
cqueue_arr[rear] = item;
}

void deletion() {
if (front == -1) { // Check for an empty queue (underflow)
printf("Queue Underflow\n");
return;
}
printf("Element deleted from queue is : %d\n", cqueue_arr[front]);

if (front == rear) { // Check if it was the last element

front = -1;
rear = -1;
} else {
front = (front + 1) % MAX; // Use modulo arithmetic to advance front
}
}

void display() {
int i;
if (front == -1) {
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
i = front;
if (front <= rear) { // Normal display when front is before or at rear
while (i <= rear) {
printf("%d ", cqueue_arr[i++]);
}
} else { // Display when the queue wraps around the array
while (i < MAX) {
printf("%d ", cqueue_arr[i++]);
}
i = 0;
while (i <= rear) {
printf("%d ", cqueue_arr[i++]);
}
}
printf("\n");
}

program on linked list using c

#include <stdio.h>
#include <stdlib.h>

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

struct node* head = NULL;

void insertAtBeginning(int data) {

struct node* newNode = (struct node*)malloc(sizeof(struct node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
newNode->data = data;
newNode->next = head;
head = newNode;
}

void displayList() {
struct node* temp = head;
if (head == NULL) {
printf("The list is empty\n");
return;
}
printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
insertAtBeginning(10);
insertAtBeginning(20);
displayList();
return 0;
}
program on stack using linked list using c
#include <stdio.h>
#include <stdlib.h> // Required for dynamic memory allocation (malloc, free)

// Define the structure for a node in the linked list

struct Node {
int data; // Data field to store the value
struct Node* next; // Pointer to the next node in the stack
};

// Global pointer to the top of the stack

struct Node* top = NULL;

// Function to check if the stack is empty

int isEmpty() {
return top == NULL; // Returns 1 if empty, 0 otherwise
}

// Function to add an element to the top of the stack (push operation)

void push(int value) {
// Allocate memory for a new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory overflow\n"); // Check for allocation failure
return;
}

newNode->data = value; // Assign data

newNode->next = top; // Link the new node to the current top node
top = newNode; // Update the top pointer to the new node
printf("Pushed %d to stack\n", value);
}

// Function to remove and return the top element from the stack (pop operation)
int pop() {
if (isEmpty()) {
printf("Stack Underflow: Cannot pop from an empty stack\n");
return -1; // Return an error value
}

struct Node* temp = top; // Temporary pointer to the current top node
int poppedValue = temp->data; // Store the data to be returned
top = top->next; // Move the top pointer to the next node
free(temp); // Free the memory of the removed node

return poppedValue;
}

// Function to return the top element without removing it (peek operation)

int peek() {
 if (isEmpty()) {
printf("Stack is empty\n");
return -1; // Return an error value
}
return top->data; // Return the data of the top node
}

// Function to display all elements in the stack

void display() {
struct Node* ptr = top;
if (isEmpty()) {
printf("Stack is empty\n");
return;
}

printf("Stack elements are:\n");

while (ptr != NULL) {
printf("%d -> ", ptr->data);
ptr = ptr->next;
}
printf("NULL\n");
}

// Main function to demonstrate stack operations

int main() {
push(10);
push(20);
push(30);
display();

printf("Popped element: %d\n", pop());

display();

printf("Top element is: %d\n", peek());

pop();
pop();
pop(); // Attempt to pop from an empty stack (triggers underflow message)

return 0;
}

program on queue using linked list using c

#include <stdio.h>
#include <stdlib.h>

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

struct Node* front = NULL;

struct Node* rear = NULL;

int isEmpty() {
return front == NULL;
}

void enqueue(int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Queue Overflow (Memory not allocated)\n");
return;
}
newNode->data = value;
newNode->next = NULL;

if (isEmpty()) {
front = rear = newNode;
return;
}

rear->next = newNode;
rear = newNode;
}

void dequeue() {
if (isEmpty()) {
printf("Queue is empty (Underflow)\n");
return;
}

struct Node* temp = front;

front = front->next;

if (front == NULL) {
rear = NULL;
}

printf("Dequeued element: %d\n", temp->data);

free(temp);
}

int peek() {
if (isEmpty()) {
 printf("Queue is empty\n");
return -1;
}
return front->data;
}

void display() {
struct Node* temp = front;
if (isEmpty()) {
printf("Queue is empty\n");
return;
}

printf("Queue: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();

printf("Front element is: %d\n", peek());

dequeue();
display();

dequeue();
dequeue();
dequeue();

return 0;
}

program on double linked list using c

#include <stdio.h>
#include <stdlib.h>

// Structure for a doubly linked list node

typedef struct Node {
int data;
struct Node* next;
 struct Node* prev;
} Node;

// Global head pointer, initialized to NULL for an empty list

Node* head = NULL;

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

// Function to insert a new node at the end of the list

void insertAtEnd(int data) {
Node* newNode = createNode(data);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}

// Function to display the list in forward direction

void displayForward() {
Node* temp = head;
if (head == NULL) {
printf("List is empty\n");
return;
}
printf("Doubly Linked List (Forward): ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to display the list in reverse direction
void displayBackward() {
Node* temp = head;
if (head == NULL) {
printf("List is empty\n");
return;
}
// Traverse to the last node
while (temp->next != NULL) {
temp = temp->next;
}
printf("Doubly Linked List (Backward): NULL <-> ");
// Traverse backwards using the prev pointer
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->prev;
}
printf("Head\n");
}

// Main function to run the program

int main() {
// Insert some elements
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
insertAtEnd(40);

// Display the list

displayForward();
displayBackward();

return 0;
}

program on circular linked list using c

#include <stdio.h>
#include <stdlib.h>

// Structure for a linked list node

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

// Global pointer to the last node (tail) for easy access

// The first node (head) is always last->next
struct Node* last = NULL;

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to insert a node at the end of the list

void insertAtEnd(int data) {
struct Node* newNode = createNode(data);

if (last == NULL) {
// If the list is empty, the new node points to itself
newNode->next = newNode;
last = newNode;
} else {
// New node points to the current head (last->next)
newNode->next = last->next;
// The current last node points to the new node
last->next = newNode;
// Update the last pointer to the new node
last = newNode;
}
printf("Inserted %d at the end.\n", data);
}

// Function to delete the first node of the list

void deleteFirst() {
if (last == NULL) {
printf("List is empty. Cannot delete.\n");
return;
}

struct Node* head = last->next;

// If there is only one node in the list

if (head == last) {
free(head);
last = NULL;
} else {
 // The last node's next pointer bypasses the old head
last->next = head->next;
free(head);
}
printf("Deleted the first node.\n");
}

// Function to display the circular linked list

void displayList() {
if (last == NULL) {
printf("List is empty.\n");
return;
}

struct Node* temp = last->next; // Start from the head

printf("Circular Linked List: ");
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != last->next); // Loop until we return to the head
printf("(head)\n");
}

// Driver Code
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
displayList(); // Output: 10 -> 20 -> 30 -> (head)

deleteFirst();
displayList(); // Output: 20 -> 30 -> (head)

insertAtEnd(40);
displayList(); // Output: 20 -> 30 -> 40 -> (head)

return 0;
}

Equivalence Class
An equivalence class is a subset of a set formed by grouping all elements
that are equivalent to each other under a given equivalence relation.
An equivalence relation is a relation that satisfies three
properties: reflexivity, symmetry, and transitivity.
Formally, if R is an equivalence relation on a set A, the equivalence class of
an element a∈A is the set of all elements in A that are related to a by R. This
is denoted as [a] and defined as:
[a] OR {x ϵ S| x is related to a}

An equivalence class is the name that we give to the subset of S that

includes all elements that are equivalent to each other. “Equivalent” is
dependent on a specified relationship, called an equivalence relation. If
there's an equivalence relation between any two elements, they're called
equivalent.
Equivalence Relation
Any relation R is said to be an Equivalence Relation if and only if it satisfies
the following three conditions:
Reflexivity
The relation ∼ is reflexive if, for every element aaa in the set S, relation ∼ a
holds. This means that each element is related to itself.
For all a ∈ S, show that a ∼ a. This can sometimes be straightforward (e.g.,
in the case of equality) or require specific reasoning depending on the
relation.
Symmetry
The relation ∼is symmetric if, for all elements a and b in S, whenever a ∼ b,
it also follows that b ∼ a.
Assume a ∼ b for arbitrary elements a, b ∈ S.
Show that this implies b ∼ a. This may involve using the definition of the
relation.
Transitivity
The relation ∼ is transitive if, for all elements a, b, and c in S, whenever a ∼
b and b ∼ c, it follows that a ∼ c.
Assume a∼ba \sim ba∼b and b∼cb \sim cb∼c for arbitrary elements a, b,
and c ∈ S.
Show that a ∼ c follows from these assumptions.
How to Find an Equivalence Class
To find the equivalence class of an element under a given equivalence
relation, follow these steps:
Identify the Set and the Equivalence Relation
Start with the set Aand the equivalence relation ∼ defined on it
Check if the Relation is an Equivalence Relation
Ensure the relation is reflexive, symmetric, and transitive. This confirms it is
an equivalence relation
Find the Equivalence Class of a Given Element
The equivalence class of an element a∈A, denoted [a], is the set of all
elements in A that are equivalent to a under the relation ∼:
[a] OR {x ϵ S| x ∼ a}
Equivalence Classes
Sets of elements that are considered equivalent under a relation
If A is an equivalence class, it is often denoted as [a] or [a]R, where a is a representative
element and R is the equivalence relation
Equivalence classes may have different cardinalities
Consider the set of integers and the equivalence relation "having the same remainder when
divided by 5."
Equivalence classes are {…,−5,0,5,…}, {…,−5,0,5,…}, {…,−4,1,6,…}, and {…,−4,1,6,…},
etc.
Equivalence classes are either disjoint or identical.

Solved Question on Equivalence Class

Question 1: Prove that the relation R is an equivalence type in the set P = { 3,
4, 5,6 } given by the relation R = { (p, q):|p-q| is even}.
Solution:
Given: R = { (p, q):|p-q| is even }. Where p, q belongs to P.
Reflexive Property
From the provided relation |p – p| = | 0 |=0.
And 0 is always even.
Therefore, |p – p| is even.
Hence, (p, p) relates to R
So R is Reflexive.
Symmetric Property
From the given relation |p – q| = |q – p|.
We know that |p – q| = |-(q – p)|= |q – p|
Hence |p – q| is even.
Next |q – p| is also even.
Accordingly, if (p, q) ∈ R, then (q, p) also belongs to R.
Therefore R is symmetric.
Transitive Property
If |p – q| is even, then (p-q) is even.
Similarly, if |q-r| is even, then (q-r) is also even.
The summation of even numbers is too even.
So, we can address it as p – q+ q-r is even.
Next, p – r is further even.
Accordingly,
|p – q| and |q-r| is even, then |p – r| is even.
Consequently, if (p, q) ∈ R and (q, r) ∈ R, then (p, r) also refers to R.
Therefore R is transitive.
Question 2: Consider A = {2, 3, 4, 5} and R = {(5, 5), (5, 3), (2, 2), (2, 4), (3, 5), (3,
3), (4, 2), (4, 4)}.
Solution:
Given: A = {2, 3, 4, 5} and
Relation R = {(5, 5), (5, 3), (2, 2), (2, 4), (3, 5), (3, 3), (4, 2), (4, 4)}.
For R to be Equivalence Relation, R needs to satisfy three properteis i.e.,
Reflexive, Symmetric, and Transitive.
Reflexive: Relation R is reflexive because (5, 5), (2, 2), (3, 3) and (4, 4) ∈ R.
Symmetric: Relation R is symmetric as whenever (a, b) ∈ R, (b, a) also
relates to R i.e.,
(3, 5) ∈ R ⟹ (5, 3) ∈ R
(2, 4) ∈ R ⟹ (4, 2) ∈ R
Transitive: Relation R is transitive as whenever (a, b) and (b, c) relate to R,
(a, c) also relates to R i.e.,
(2, 4) ∈ R and (4, 2) ∈ R ⇒ then (2, 2) ∈ R
(3, 5) ∈ R and (5, 3) ∈ R ⟹ (3, 3) ∈ R
(4, 2) and (2, 4) ⇒ (4, 4) ∈ R
(4, 2) and (2, 2) ⇒ (4, 2) ∈ R
(2, 4) and (4, 4) ⇒ (2, 4) ∈ R
Accordingly, R is reflexive, symmetric and transitive.
So, R is an Equivalence Relation
 Lecture-08
Polynomial List
A polynomial p(x) is the expression in variable x which is in the form (ax n + bxn-1 + …. +
jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non negative
integer, which is called the degree of polynomial.
An important characteristics of polynomial is that each term in the polynomial
expression consists of two parts:
 one is the coefficient
 other is the exponent
Example:
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 are its exponential value.
Points to keep in Mind while working with Polynomials:
 The sign of each coefficient and exponent is stored within the coefficient and the
exponent itself
 Additional terms having equal exponent is possible one
 The storage allocation for each term in the polynomial must be done in
ascending and descending order of their exponent

Representation of Polynomial
Polynomial can be represented in the various ways. These are:
 By the use of arrays
 By the use of Linked List
Representation of Polynomials using Arrays
There may arise some situation where you need to evaluate many polynomial
expressions and perform basic arithmetic operations like: addition and subtraction with
those numbers. For this you will have to get a way to represent those polynomials. The
simple way is to represent a polynomial with degree 'n' and store the coefficient of n+1
terms of the polynomial in array. So every array element will consists of two values:
 Coefficient and
 Exponent
Representation of Polynomial Using Linked Lists
A polynomial can be thought of as an ordered list of non zero terms. Each non zero
term is a two tuple which holds two pieces of information:
  The exponent part
 The coefficient part
Adding two polynomials using Linked List
Given two polynomial numbers represented by a linked list. Write a function that add
these lists means add the coefficients who have same variable powers.
Example:

Input:
1st number = 5x^2 + 4x^1 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^2 + 9x^1 + 7x^0
Input:
1st number = 5x^3 + 4x^2 + 2x^0
2nd number = 5x^1 + 5x^0
Output:
5x^3 + 4x^2 + 5x^1 + 7x^0
struct Node

int coeff;

int pow;

struct Node *next;

};

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;

void polyadd(struct Node *poly1, struct Node *poly2, struct Node *poly)

while(poly1->next && poly2->next)

if(poly1->pow > poly2->pow)

poly->pow = poly1->pow;

poly->coeff = poly1->coeff;

poly1 = poly1->next;

else if(poly1->pow < poly2->pow)

poly->pow = poly2->pow;

poly->coeff = poly2->coeff;

poly2 = poly2->next;

else

poly->pow = poly1->pow;

poly->coeff = poly1->coeff+poly2->coeff;
 poly1 = poly1->next;

poly2 = poly2->next;

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;

}
}

void show(struct Node *node)

while(node->next != NULL)

printf("%dx^%d", node->coeff, node->pow);

node = node->next;

if(node->next != NULL)

printf(" + ");

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("\n2nd Number: ");

show(poly2);
 poly = (struct Node *)malloc(sizeof(struct Node));

// Function add two polynomial numbers

polyadd(poly1, poly2, poly);

// Display resultant List

printf("\nAdded polynomial: ");

show(poly);

return 0;

Output:

1st Number: 5x^2 + 4x^1 + 2x^0

2nd Number: 5x^1 + 5x^0
Added polynomial: 5x^2 + 9x^1 + 7x^0
Static hashing
uses a hash table with a fixed number of buckets that does not change at runtime. Data is
mapped to these fixed locations using a consistent hash function, making it predictable and
simple to implement, though less flexible for dynamic datasets.

Key Components

 Hash Table: An array-based data structure used to store data in key-value pairs. Each
position in the array is called a "bucket" or "slot".
 Hash Function: An algorithm that takes a key as input and produces a fixed-size integer
value (hash code), which is then converted into an array index (bucket address).
 Collision: Occurs when two different keys are mapped to the same index by the hash
function. Collisions are inevitable and require specific techniques to manage.

How it Works
The process in static hashing is consistent for basic operations:

1. Insertion: A hash function is applied to the key of the new data to determine the bucket
index. The data is placed in that location. If the location is already occupied, a collision
resolution technique is used.
2. Searching: The same hash function is applied to the key being searched. The resulting
index points directly to the location where the data should be stored. The system checks
this specific bucket for the record.
3. Deletion/Updating: The hash function is used to quickly locate the item's bucket, after
which the item can be removed or modified.
 Advantages Disadvantages
Simple to implement and understand. Inefficient for large or dynamic datasets.
Performance degrades significantly with a high
Predictable memory usage due to the fixed size.
load factor (many collisions).
Restructuring the entire table is time-
Excellent performance (average O(1) time
consuming if it overflows.
complexity) for small, stable datasets.
 Hash Table

Hash Technique