EXPERIMENT NO 5 Roll Number:
Practice the Concept of Circular Linked List
Objective:
To be able to understand and implement Circular linked list in C++.
To understand the core principles of circular linked lists, their implementation,
and manipulation.
Theory:
A Circular Linked List is a variation of the standard linked list in which the last node
points back to the first node. This results in a closed-loop, making the list circular, allowing for
unique advantages and use-cases over traditional linear linked lists.
There are generally two types of circular linked lists:
Circular singly linked list: In a circular Singly linked list, the last node of the list contains a
pointer to the first node of the list. We traverse the circular singly linked list until we reach the
same node where we started. The circular singly linked list has no beginning or end. No null
value is present in the next part of any of the nodes.
Circular Doubly linked list: Circular Doubly Linked List has properties of both doubly linked
list and circular linked list in which two consecutive elements are linked or connected by the
previous and next pointer and the last node points to the first node by the next pointer and also
the first node points to the last node by the previous pointer.
Applications of circular linked lists:
1. Multiplayer games use this to give each player a chance to play.
2. A circular linked list can be used to organize multiple running applications on
an operating system. These applications are iterated over by the OS.
3. Circular linked lists can be used in resource allocation problems.
4. Circular linked lists are commonly used to implement circular buffers,
Example:
Perform this example and show the result.
// C++ program to delete a given key from free(*head);
// linked list. *head =
#include <bits/stdc++.h> NULL;
using namespace std; return;
}
// Structure for a node
class Node { Node *last = *head, *d;
public:
int data; // If head is to be deleted
Node* next; if ((*head)->data == key) {
};
// Find the last node of the
// Function to insert a node at the list while (last->next !=
// beginning of a Circular linked list *head)
void push(Node** head_ref, int data) last = last->next;
{
// Point last node to the next
// Create a new node and make head of
// as next of it. // head i.e. the second node
Node* ptr1 = new Node(); // of the list
ptr1->data = data; last->next = (*head)-
ptr1->next = *head_ref; >next; free(*head);
*head = last-
// If linked list is not NULL then >next; return;
// set the next of last node if }
(*head_ref != NULL) {
// Either the node to be deleted is
// Find the node before head // not found or the end of list
and // is not reached
// update next of it. Node* while (last->next != *head && last-
temp = *head_ref; while >next->data != key) {
(temp->next != last = last->next;
*head_ref }
// If node to be deleted was
found if (last->next->data ==
key) {
temp = temp->next; temp->next = ptr1; d = last->next;
} last->next = d-
else >next; free(d);
// For the first node }
ptr1->next = ptr1; else
cout << "Given node is
*head_ref = ptr1; not found in the list!!!\n";
} }
// Function to print nodes in a given
// circular linked list // Driver
void printList(Node* head) code int
{ main()
Node* temp = head; if {
(head != NULL) { do // Initialize lists as
{ empty Node* head =
cout << temp->data << NULL;
" ";
temp = temp->next; // Created linked list will be
} while (temp != head); // 2->5->7->8->10
} push(&head, 2);
push(&head, 5);
cout << endl; push(&head, 7);
} push(&head, 8);
push(&head, 10);
// Function to delete a given node
// from the list cout << "List Before Deletion:
void deleteNode(Node** head, int key) "; printList(head);
{
// If linked list is empty if deleteNode(&head, 7);
(*head == NULL)
return; cout << "List After
Deletion: "; printList(head);
// If the list contains only a
// single node return 0;
if ((*head)->data == key && (*head)- }
>next == *head) {
Lab Task:
T1. Convert Singly Linked List to Circular Linked List:
Take a singly linked list.
Traverse to the end of the singly linked list.
Make the last node's next pointer point to the head of the list.
T2. Circular Doubly Linked List:
Extend the above task to include a previous pointer in the Node class.
T3. Insertion in Circular Linked List:
Beginning: Link the new node to the current head, traverse to the last
node, update its next to the new node, and make the new node the new
head.
End: Traverse to the last node, link the new node to the head, and update the
last node's next to the new node.
Middle: Locate the required position and adjust the next pointers of the preceding
and subsequent nodes.
T4. Sorting in a Circular Linked List:
Implement a sorting algorithm, like bubble sort, that works specifically with the circular linked list
structure.
Questions
1. How does a circular linked list (CLL) differ from a standard singly linked list?
2. While traversing a circular linked list, what condition should you check for to ensure
you don't end up in an infinite loop?
3. In a circular linked list, what node does the next pointer of the tail node point to?