DATA STRUCTURES
CSE 1301
LECTURE 5
CIRCULAR LINKED LIST OPERATIONS
University of Liberal Arts Bangladesh 1
Circular Linked List
• A linked list where the last node points back
to the first node, forming a loop.
• Each node contains data and a pointer to
the next node.
• Operations: Insertion, deletion, search, and
traversal.
Real-Life Application of Circular
Linked Lists
• Music and Media Players
• Task Scheduling
• Cache Management
Insert at the Start
1. Create a new node with the given data.
2. If the list is empty, set the next pointer of the new
node to itself.
3. Otherwise, find the last node in the list (the node
pointing to the head).
4. Set the next pointer of the new node to the head.
5. Update the next pointer of the last node to the new
node.
6. Set the head pointer to the new node.
Code
void insertAtStart(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
newNode->next = newNode;
} else {
struct Node* last = *head;
while (last->next != *head) {
last = last->next;
}
newNode->next = *head;
last->next = newNode;
}
*head = newNode;
}
Insert at a Position
1. Create a new node with the given data.
2. If the list is empty, set the next pointer of the new node to
itself and update the head pointer.
3. Otherwise, find the node at the desired position.
4. Set the next pointer of the new node to the next pointer of
the previous node.
5. Set the next pointer of the previous node to the new node.
Code
void insertAtPosition(struct Node** head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}
struct Node* current = *head;
for (int i = 1; i < position - 1; i++) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
Insert at the End
1. Create a new node with the given data.
2. If the list is empty, set the next pointer of the new
node to itself and update the head pointer.
3. Otherwise, find the last node in the list (the node
pointing to the head).
4. Set the next pointer of the new node to the head.
5. Set the next pointer of the last node to the new node.
Code
void insertAtEnd(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
newNode->next = newNode;
*head = newNode;
return;
}
struct Node* last = *head;
while (last->next != *head) {
last = last->next;
}
newNode->next = *head;
last->next = newNode;
}
Delete at the Start
1. If the list is empty, return.
2. Find the last node in the list (the node pointing to the
head).
3. Set the next pointer of the last node to the second
node in the list.
4. Free the memory of the first node.
5. Update the head pointer to the second node.
Code
void deleteAtStart(struct Node** head) {
if (*head == NULL) {
return;
}
struct Node* last = *head;
while (last->next != *head) {
last = last->next;
}
struct Node* temp = *head;
last->next = (*head)->next;
*head = (*head)->next;
free(temp);
}
Delete with a Value
1. If the list is empty, return.
2. Find the node with the given value.
3. If the node is not found, return.
4. If the node is the head node, call the deleteAtStart
function.
5. Otherwise, find the previous node of the node to be
deleted.
6. Set the next pointer of the previous node to the next
pointer of the node to be deleted.
7. Free the memory of the node to be deleted.
Code
void deleteWithValue(struct Node** head, int value) {
if (*head == NULL) {
return; }
struct Node* current = *head;
struct Node* prev = NULL;
while (current->data != value) {
if (current->next == *head) {
return; }
prev = current;
current = current->next;
if (current == *head) {
deleteAtStart(head);
return;
prev->next = current->next;
free(current);
}
Delete at the End
1. If the list is empty, return.
2. Find the node pointing to the last node in the list (the
node pointing to the head).
3. Find the last node in the list (the head node).
4. Set the next pointer of the node pointing to the last
node to the head.
5. Free the memory of the last node.
Code
void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
return;
}
struct Node* current = *head;
struct Node* prev = NULL;
while (current->next != *head) {
prev = current;
current = current->next;
}
prev->next = *head;
free(current);
}
Search
1. If the list is empty, return NULL (not found).
2. Start from the head node and traverse the
list until the last node is reached.
3. If the desired value is found, return the
node.
4. If the last node is reached and the value is
not found, return NULL (not found).
Code
bool search(Node* head, int value) {
if (head == NULL)
return false;
Node* curr = head;
do {
if (curr->data == value)
return true;
curr = curr->next;
} while (curr != head);
return false;
}
Traverse
1. If the list is empty, return.
2. Start from the head node and traverse the list until
the last node is reached.
3. Print the data of each node.
4. Stop traversing when the last node is reached.
Code
void traverse(struct Node* head) {
if (head == NULL) {
return;
}
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
Common Mistakes
Dereferencing a NULL pointer
head = NULL;
head->data = 5; /* ERROR */
Using a pointer before set
one = malloc(sizeof(struct node));
head=one
head->next->data = 7; /* ERROR */
21
