Circular Linked List

A circular linked list is a type of linked list in which the last node is also connected to the first node to form a circle. Thus a circular linked list has no end.

There are two types of linked lists:

• Circular Singly Linked List.
• Circular Doubly Linked List.

Representation of Circular Linked List

Each of the nodes in the linked list consists of two parts:

• A data item.
• An address that points to another node.

A single node can be represented using structure as

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

Each struct node contains a data item as well as a pointer to another struct node. The following example creates a Circular Linked List with three items and display its elements.

Example: Creating a Circular Linked List

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

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

int main()
{
    // Create and initialize nodes
    struct node *head;
    struct node *one = NULL;
    struct node *two = NULL;
    struct node *three = NULL;
    struct node *current = NULL;
 
    // Allocate memory for the nodes
    one = (struct node*) malloc(sizeof(struct node));
    two = (struct node*) malloc(sizeof(struct node));
    three = (struct node*) malloc(sizeof(struct node));
 
    // Assign data to nodes
    one->data = 1;
    two->data = 2;
    three->data = 3;
 
    // Connect first node
    // with the second node
    one->next = two;
     
    // Connect second node
    // with the third node
    two->next = three;
 
    // Connect second node
    // with the third node
    three->next = one;
 
    // Save address of first node in head
    head = one;
    current = head;
 
    // print the linked list values
    while(current != NULL)
    {
        printf("%d ", current->data);
        current = current->next;
    }
    return 0;
}

Now we’ve made a circular linked list with three nodes.

Output

1 2 3

Inserting a New Node to a Circular Linked List

A new node can be inserted anywhere in a circular linked list. Here, we are discussing the following cases.

• Inserting a new Node at the beginning of a Circular Linked List.
• Inserting a new Node at the end of a Circular Linked List.

The remaining cases are the same as those described for a singly linked list.

Insert at the beginning of a list

Suppose we want to add a new node with data 24 as the first node in the following linked list. The following changes will be done in the linked list.

• Allocate memory for new node and initialize its DATA part to 24.
• Add the new node as the first node of the list by pointing the NEXT part of the new node to HEAD.
• Make HEAD to point to the first node of the list.
• Make HEAD point to the new node.

Algorithm: InsertAtBeginning

Step 1: IF AVAIL = NULL
            Write OVERFLOW
            Go to Step 11
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = HEAD
Step 6: Repeat Step 7 while PTR -> NEXT != HEAD
Step 7:     PTR = PTR -> NEXT
        [END OF LOOP]
Step 8: SET NEW_NODE -> NEXT = HEAD
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: SET HEAD = NEW_NODE
Step 11: EXIT

Note that the first step of the algorithm checks if there is enough memory available to create a new node. The second, and third steps allocate memory for the new node.

Insert at the end of the list

Suppose we want to add a new node with data 24 as the last node of the following circular linked list. The following changes have to be made in the linked list.

• Allocate memory for the new node and initialize data.
• Traverse to the end of the list.
• Point the NEXT part of the last node to the newly created node.
• Make the value of next part of last node to HEAD.

Algorithm: InsertAtLast

Step 1: IF AVAIL = NULL
            Write OVERFLOW
            Go to Step 1
        [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = HEAD
Step 6: SET PTR = HEAD
Step 7: Repeat Step 8 while PTR -> NEXT != HEAD
Step 8:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 1 : EXIT

Deleting a Node from a Circular Linked List

Let’s look at how a node is removed from a circular linked list in the following scenarios.

• The first node is deleted.
• The last node is deleted.

The remaining cases are the same as those described for a singly linked list.

Deleting first node from a list

The following changes have to be made to the linked list if we want to remove the first node having data 24.

• Check if the linked list is empty or not. Exit if the list is empty.
• Make HEAD points to the second node.
• Traverse to the end of the list and point the next part of last node to second node.
• Free the first node from memory.

Algorithm: DeleteFirst

Step 1: IF HEAD = NULL
            Write UNDERFLOW
            Go to Step 8
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: Repeat Step 4 while PTR -> NEXT != HEAD
Step 4:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 5: SET PTR -> NEXT = HEAD -> NEXT
Step 6: FREE HEAD
Step 7: SET HEAD = PTR -> NEXT
Step 8: EXIT

Deleting last node from the list

Suppose we want to delete the last node from the circular linked list. The following changes will be done in the list.

• Traverse to the end of the list.
• Change value of next pointer of second last node to HEAD.
• Free last node from memory.

Algorithm: DeleteFirst

Step 1: IF HEAD = NULL
            Write UNDERFLOW
            Go to Step 8
        [END OF IF]
Step 2: SET PTR = HEAD
Step 3: Repeat Steps 4 and 5 while PTR NEXT != HEAD
Step 4:     SET PREPTR = PTR
Step 5:     SET PTR = PTR -> NEXT
        [END OF LOOP]
Step 6: SET PREPTR -> NEXT = HEAD
Step 7: FREE PTR
Step 8: EXIT