Horje
C Program to Implement Circular Linked List

A linked list is a dynamic data structure where elements are not stored in contiguous memory locations but linked using pointers. In a circular linked list, the last node points back to the first node instead of pointing to NULL, forming a circle.

In this article, we will learn how to implement the circular linked list in C++ along with its basic operations.

What is a Circular Linked List?

A circular linked list is a type of linked list where the last node of the list points back to the first node instead of pointing to NULL. This circular linking makes traversal of the list from any point possible and eliminates the need to maintain a separate pointer for the head and tail of the list.

circular-linked-list-copy[1]

In the above diagram, last node pointer back to first node, creating the circular link. This organization allows for the seamless transitions from the end of list back to the beginning and it can be enabling the continuous iteration over the lists elements.

Representation of Circular Linked List in C

In C, a circular linked list is represented using a Node structure that contains data and a pointer to the next node:

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

Implementation of Circular Linked List in C

To implement a circular linked list in C, we can define functions for basic operations such as insertion, deletion, traversal, and searching. Here’s how we can create and manipulate a circular linked list:

Basic Operations on Circular Linked List

Following are the basic operations on the circular linked list in C++:

1. Insertion

Insertion in the circular linked list can be performed at the various positions: the beginning, the end or after the specific node. Each insertion operation has its own specific steps and considerations to the maintain the circular structure.

Operation

Definition

Time Complexity

Space Complexity

Insertion at the end

Adding the new node at the end of circular linked list.

O(n)

O(1)

Insertion at the Beginning

Adding the new node at the beginning of the circular linked list.

O(n)

O(1)

Deletion from the Specific Position

Adding the new node at the given position

O(n)

O(1)

Implementation of InsertAtBegin

To insert a node at the beginning of a circular linked list:

  • Create a new node with the given data.
  • If the list is empty, set the new node to itself and make it the head node.
  • If the list is not empty, traverse to the last node and update its next pointer to point to the new node. Then update the head pointer to the new node.’

Implementation of InsertAtEnd

To insert a node at the end of a circular linked list:

  • Create a new node with the given data.
  • If the list is empty, set the new node to itself and make it the head node.
  • If the list is not empty, traverse to the last node.
  • Set the last node’s next pointer to the new node.
  • Set the new node’s next pointer to the head to maintain circularity.

Implementation of InsertAtSpecificPosition

To insert a node at a specific position in a circular linked list:

  • Create a new node with the given data.
  • If the list is empty and position is 0, set the new node to itself and make it the head node.
  • Traverse to the node just before the desired position.
  • Insert the new node by adjusting pointers.

2. Deletion

Deletion can be performed at the various positions: from the beginning, the end or the specific node. Each deletion operation must ensure the structure can be maintained by the updating pointers appropriately.

Operation

Definition

Time Complexity

Space Complexity

Deletion from the Beginning

Removing the first node of circular linked list.

O(n)

O(1)

Deletion from the End

Removing the last node of circular linked list.

O(n)

O(1)

Deletion from the Specific Position

Remove the element from the given position

O(n)

O(1)

Implementation of DeleteFromBeginning

To delete a node from the beginning of a circular linked list:

  • If the list is empty, return.
  • If the list has only one node, delete it and set head to NULL.
  • Traverse to the last node and update its next pointer.
  • Free the memory allocated to the node to be deleted.

Implementation of DeleteFromEnd

To delete a node from the end of a circular linked list:

  • If the list is empty, return.
  • If the list has only one node, delete it and set head to NULL.
  • Traverse to the second last node and update its next pointer to NULL.
  • Free the memory allocated to the last node.

Implementation of DeleteFromSpecificPosition

To delete a node from a specific position in a circular linked list:

  • If the list is empty, return.
  • Traverse to the node just before the desired position.
  • Adjust pointers to skip the node to be deleted.
  • Free the memory allocated to the node to be deleted.

3. Traversal

Traversing the circular linked list means visiting the each node starting from any node and continuing until all the nodes have been visited at the least once. this operation can typically starts at the head and continuous until the head is encountered again.

Implementation of Traversal

  1. Check if list is empty then if it is return.
  2. Initialize the temporary pointer to the head.
  3. Loop through the list starting from head and print the each nodes data.
  4. Continue until the pointer reaches back to head.

4. Search

To search for a node with a given key in a circular linked list:

  • Start from the head node.
  • Traverse each node and compare its data with the given key until the key is found or you reach the head again.

Program to Implement Circular Linked List in C

C 
#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));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int data)
{
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
    }
    else {
        struct Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
        *head = newNode;
    }
}

// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data)
{
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = *head;
    }
    else {
        struct Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = *head;
    }
}

// Function to insert a node at a specific position
void insertAtPosition(struct Node** head, int data,
                      int position)
{
    struct Node* newNode = createNode(data);
    if (*head == NULL && position == 0) {
        *head = newNode;
        newNode->next = *head;
    }
    else if (position == 0) {
        insertAtBeginning(head, data);
    }
    else {
        struct Node* temp = *head;
        int i = 0;
        while (i < position - 1) {
            temp = temp->next;
            i++;
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

// Function to delete a node from the beginning
void deleteFromBeginning(struct Node** head)
{
    if (*head == NULL) {
        return;
    }
    else if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
    }
    else {
        struct Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        temp->next = (*head)->next;
        struct Node* toDelete = *head;
        *head = (*head)->next;
        free(toDelete);
    }
}

// Function to delete a node from the end
void deleteFromEnd(struct Node** head)
{
    if (*head == NULL) {
        return;
    }
    else if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
    }
    else {
        struct Node* secondLast = *head;
        while (secondLast->next->next != *head) {
            secondLast = secondLast->next;
        }
        struct Node* last = secondLast->next;
        secondLast->next = *head;
        free(last);
    }
}

// Function to delete a node from a specific position
void deleteAtPosition(struct Node** head, int position)
{
    if (*head == NULL) {
        return;
    }
    else if (position == 0) {
        deleteFromBeginning(head);
    }
    else {
        struct Node* temp = *head;
        int i = 0;
        while (i < position - 1) {
            temp = temp->next;
            i++;
        }
        struct Node* toDelete = temp->next;
        temp->next = temp->next->next;
        free(toDelete);
    }
}

// Function to traverse and print the circular linked list
void traverse(struct Node* head)
{
    if (head == NULL) {
        return;
    }
    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("HEAD\n");
}

// Function to search for a node with a given key
int search(struct Node* head, int key)
{
    if (head == NULL) {
        return 0;
    }
    struct Node* temp = head;
    do {
        if (temp->data == key) {
            return 1; // Key found
        }
        temp = temp->next;
    } while (temp != head);
    return 0; // Key not found
}

// Driver program
int main()
{
    struct Node* head = NULL;

    // Insertion
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtBeginning(&head, 5);
    insertAtPosition(&head, 15, 2);

    // Traversal
    printf("Circular Linked List: ");
    traverse(head);

    // Deletion
    deleteFromEnd(&head);
    deleteAtPosition(&head, 1);

    // Traversal after deletion
    printf("Circular Linked List after deletion: ");
    traverse(head);

    // Searching
    int key = 10;
    if (search(head, key)) {
        printf("Element %d is found in the linked list.\n",
               key);
    }
    else {
        printf(
            "Element %d is not found in the linked list.\n",
            key);
    }

    return 0;
}

Output
Circular Linked List: 5 -> 10 -> 15 -> 20 -> HEAD
Circular Linked List after deletion: 5 -> 15 -> HEAD
Element 10 is not found in the linked list.

Applications of Circular Linked List

  1. Round Robin Scheduling: It can be used in the operating system to schedule a process in the cyclic manner.
  2. FIFO Buffers: It can be used in networking for the buffer management.
  3. Music Player Playlists: It can be used to cycle through the songs in a playlist.

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

C Language

Related
Queue using Linked List in C Queue using Linked List in C
Tarjan’s Algorithm in C Language Tarjan’s Algorithm in C Language
N Queen Problem Using Branch and Bound in C N Queen Problem Using Branch and Bound in C
Partition Equal Subset Sum in C Partition Equal Subset Sum in C
Shortest Path Algorithm in C Shortest Path Algorithm in C

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 21



 

Horje