Circular Linked List


A circular linked list is a variation of a linked list where the last node points back to the first node, creating a loop. We traverse a circular singly linked list until we reach the same node where we started. The circular singly liked list has no beginning and no ending. There is no null value present in the next part of any of the nodes.

The following image shows a circular singly linked list.

Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of circular linked lists and can be accessed again on clicking the previous button.

Here are the details and algorithms for various operations on a circular linked list:

Node Structure

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

Algorithm: initializeCircularLinkedList() 
Input: None 
Output: head (initialized as NULL) 
1. Set head to NULL. 
2. Return head.

Algorithm: insertAtBeginning(head, data)
Input: head (current head of the circular linked list), data (value to be inserted)
Output: newHead (updated head after insertion)

1. Create a new node newNode and allocate memory for it.
2. Set newNode's data to the given data.
3. If the list is empty (head is NULL):
    a. Set newNode's next pointer to itself.
    b. Return newNode as the new head.
4. Set newNode's next pointer to the current head.
5. Traverse the list to find the last node (last) whose next is the current head.
6. Set last's next pointer to newNode.
7. Return newNode as the new head.


// Function to insert a node at the beginning of the circular linked list
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        newNode->next = newNode; // Point to itself for the only node in the list
    } else {
        newNode->next = head;
        head->next = newNode;
    }

    return newNode;
}

Algorithm: insertAtEnd(head, data)
Input: head (current head of the circular linked list), data (value to be inserted)
Output: head (updated head after insertion)

1. Create a new node newNode and allocate memory for it.
2. Set newNode's data to the given data.
3. If the list is empty (head is NULL):
    a. Set newNode's next pointer to itself.
    b. Return newNode as the head.
4. Traverse the list to find the last node (last) whose next is the current head.
5. Set last's next pointer to newNode.
6. Set newNode's next pointer to the current head.
7. Return the original head.

// Function to insert a node at the end of the circular linked list
struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        newNode->next = newNode; // Point to itself for the only node in the list
        return newNode;
    }
    struct Node *current=head;
    do
    {
        current=current->next;
    }
    while(current->next!=head);
    current->next=newNode;
    newNode->next = head;
    
    return head;
}

Algorithm: deleteAtBeginning(head)
Input: head (current head of the circular linked list)
Output: newHead (updated head after deletion)

1. If the list is empty (head is NULL), print "List is empty" and return NULL.
2. Create a temporary node temp and set it to head.
3. Traverse the list to find the last node (last) whose next is the current head.
4. If there is only one node in the list (head's next is head):
    a. Free the memory of head.
    b. Return NULL as the new head.
5. Set the new head to head's next.
6. Set last's next pointer to the new head.
7. Free the memory of temp.
8. Return the new head.

// Function to delete a node from the front of the circular linked list
struct Node* deleteFromFront(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    struct Node* current=head;

    if (head->next == head) {
        free(head);
        return NULL;
    }
     do
     {
       current=current->next;  
     }
     while(current->next!=head);
    current->next = head->next;
    struct Node *temp=head;
    head=head->next;
    free(temp);
    return head;
}

Algorithm: deleteAtEnd(head)
Input: head (current head of the circular linked list)
Output: head (updated head after deletion)

1. If the list is empty (head is NULL), print "List is empty" and return NULL.
2. Traverse the list to find the last node (last) and the second-to-last node (secondLast).
3. If there is only one node in the list (head's next is head):
    a. Free the memory of head.
    b. Return NULL as the new head.
4. Set secondLast's next pointer to head.
5. Free the memory of the last node.
6. Return the original head.
// Function to delete a node from the end of the circular linked list
struct Node* deleteFromEnd(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    struct Node* current = head;
    struct Node* previous = NULL;

    if (current->next == head) {
        // Only one node in the list
        free(head);
        return NULL;
    }

    while (current->next != head) {
        previous = current;
        current = current->next;
    }

    previous->next = current->next;
    free(current);

    return head;
}

Algorithm: traverseCircularLinkedList(head)
Input: head (current head of the circular linked list)
Output: None (prints the elements in the list)

1. If the list is empty (head is NULL), print "List is empty."
2. Create a temporary node temp and set it to head.
3. Do the following until temp reaches the head again:
    a. Print the data of temp.
    b. Move temp to the next node.
4. Print a newline.

// Function to traverse and print the circular linked list
void traverseCircularLinkedList(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* current = head; // Start from the first node
    do
    {
        printf("%d ", current->data);
        current = current->next;
    }  // Stop when we reach the first node again
   while(current!=head);
    printf("\n");
}

Time Complexity:

Insertion/Deletion at the Beginning:
Time complexity: O(1)
Inserting or deleting a node at the beginning of a circular linked list involves updating pointers, and the time complexity is constant.

Insertion/Deletion at the End:
Time complexity: O(n)
Inserting or deleting a node at the end of a circular linked list requires traversing the entire list to find the last node. This results in a linear time complexity.

Traversing the List:
Time complexity: O(n)
To traverse the entire circular linked list, you need to visit each node once. The time complexity is linear.

C program Implementation-Circular Linked List
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>

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

// 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(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the beginning of the circular linked list
struct Node* insertAtBeginning(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        newNode->next = newNode; // Point to itself for the only node in the list
    } else {
        newNode->next = head;
        head->next = newNode;
    }

    return newNode;
}

// Function to insert a node at the end of the circular linked list
struct Node* insertAtEnd(struct Node* head, int data) {
    struct Node* newNode = createNode(data);

    if (head == NULL) {
        newNode->next = newNode; // Point to itself for the only node in the list
        return newNode;
    }
    struct Node *current=head;
    do
    {
        current=current->next;
    }
    while(current->next!=head);
    current->next=newNode;
    newNode->next = head;
    

    return head;
}

// Function to delete a node from the front of the circular linked list
struct Node* deleteFromFront(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    struct Node* current=head;

    if (head->next == head) {
        free(head);
        return NULL;
    }
     do
     {
       current=current->next;  
     }
     while(current->next!=head);
    current->next = head->next;
    struct Node *temp=head;
    head=head->next;
    free(temp);
    return head;
}

// Function to delete a node from the end of the circular linked list
struct Node* deleteFromEnd(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }

    struct Node* current = head;
    struct Node* previous = NULL;

    if (current->next == head) {
        // Only one node in the list
        free(head);
        return NULL;
    }

    while (current->next != head) {
        previous = current;
        current = current->next;
    }

    previous->next = current->next;
    free(current);

    return head;
}

// Function to traverse and print the circular linked list
void traverseCircularLinkedList(struct Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    struct Node* current = head; // Start from the first node
    do
    {
        printf("%d ", current->data);
        current = current->next;
    }  // Stop when we reach the first node again
   while(current!=head);
    printf("\n");
}


// Main function for testing
int main() {
    struct Node* head = NULL;

    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 20);
    traverseCircularLinkedList(head);
    head = insertAtEnd(head, 30);
    head = insertAtEnd(head, 40);
    traverseCircularLinkedList(head);
    printf("Circular Linked List: ");
    traverseCircularLinkedList(head);

   head = deleteFromEnd(head);
   printf("After deletion from end: ");
    
    traverseCircularLinkedList(head);

    head = deleteFromFront(head);

    printf("After deletion from front: ");
    traverseCircularLinkedList(head);
  
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more