Circular Linked List: Advantages and Disadvantages

What is a Circular Linked List?

A circular linked list is a sequence of nodes arranged so that each node can be retraced to itself. Each “node” is a self-referential element with pointers to one or two nodes in its immediate vicinity.

Below is a depiction of a circular linked list with 3 nodes.

Here, you can see that each node is retraceable to itself. The example shown above is a circular singly linked list.

Note: The simplest circular linked list is a single node whose next pointer traces back to itself, as shown below.

Basic Operations in Circular Linked Lists

The three basic operations on a circular linked list are:

1. Insertion
2. Deletion and
3. Traversal

• Insertion is the process of placing a node at a specified position in the circular linked list.
• Deletion is the process of removing an existing node from the linked list. The node can be identified by the occurrence of its value or by its position.
• Traversal of a circular linked list is the process of displaying the entire linked list’s contents and retracing back to the source node.

The next section explains how insertion works and the two types of insertion possible in a circular singly linked list.

Insertion Operation

You first create one node whose next pointer points back to itself, as shown below. Without this seed node, the first insertion becomes the first node in the list.

Next, there are two possibilities:

• Insertion at the current position of the circular linked list. This corresponds to inserting at either the beginning or the end of a regular singly linked list — in a circular linked list, the beginning and the end are the same point.
• Insertion after an indexed node. The node should be identified by an index number corresponding to its element value.

To insert at the beginning or end of the circular linked list — that is, at the position where the first-ever node was added — follow the steps below:

• You will have to break the existing self-link to the existing node
• The new node’s next pointer will link to the existing node.
• The last node’s next pointer will point to the inserted node.

NOTE: The pointer that marks the beginning or end of the circle can be reassigned to any node. A traversal will still return to the same node, as discussed later in this article.

Steps in (a) i-iii are shown below:

(Existing node)

Step 1) Break the existing link

Step 2) Create a forward link (from new node to an existing node)

Step 3) Create a loop link to the first node

Next, you will try insertion after a node.

For example, insert “VALUE2” after the node holding “VALUE0”, assuming the starting point is the node with “VALUE0”.

• Break the link between the first and second nodes, and place the node with “VALUE2” in between.
• The first node’s next pointer links to the new node, and the new node’s next pointer links to what was previously the second node.
• The rest of the arrangement remains unchanged. All nodes are retraceable to themselves.

NOTE: Because the arrangement is cyclic, the procedure for inserting a node is identical no matter which position you choose. The pointer that closes the cycle behaves like any other pointer in the list.

This is shown below:

(Let us say there are only two nodes. This is a trivial case)

Step 1) Remove the inner link between the connected nodes

Step 2) Connect the left-hand side node to the new node

Step 3) Connect the new node to the right hand side node.

Deletion Operation

Assume a 3-node circular linked list. The two deletion cases are:

• Deleting the current element
• Deletion after an element.

Deletion at the beginning/end:

1. Traverse to the first node from the last node.
2. Deleting from the end requires only one traversal step, from the last node to the first node.
3. Delete the link between the last node and the first node.
4. Link the last node to the next element of the first node.
5. Free the first node.

(Existing setup)

Step 1) Remove the circular link

Step 2) Remove the link between the first and next, link the last node, to the node following the first

Step 3) Free / deallocate the first node

Deletion after a node:

1. Traverse until the next node is the node to be deleted.
2. Traverse to the next node, placing a pointer on the previous node.
3. Connect the previous node to the node after the present node, using its next pointer.
4. Free the current (delinked) node.

Step 1) Let us say that we need to delete a node with “VALUE1.”

Step 2) Remove the link between the previous node and the current node, then link the previous node directly to the node pointed to by the current node’s next pointer (the node after VALUE1).

Step 3) Free or deallocate the current node.

Traversal of a Circular Linked List

To traverse a circular linked list from a last pointer, first check whether the last pointer is NULL. If it is not NULL, check whether the list has only one element. Otherwise, walk the list with a temporary pointer until you reach the last pointer again, as shown in the animation below.

Advantages of Circular Linked List

Some of the advantages of circular linked lists are:

1. No requirement for a NULL assignment in the code. The circular list never points to a NULL pointer unless fully deallocated.
2. Circular linked lists are advantageous for end-of-list operations because the beginning and end coincide. Algorithms such as round-robin scheduling can move through queued processes cleanly, without encountering dangling or NULL pointers.
3. A circular linked list still supports all the regular operations of a singly linked list. A circular doubly linked list can even eliminate the need for a full-length traversal to locate an element — in the worst case, the target sits opposite the start pointer, so at most half the list needs to be walked.

Disadvantages of Circular Linked List

The disadvantages in using a circular linked list are below:

1. Circular lists are more complex than singly linked lists.
2. Reversing a circular list is more complex than reversing a singly or doubly linked list.
3. If loop termination is not handled carefully, the traversal code can enter an infinite loop.
4. It is harder to find the end of the list and to write correct loop-control conditions.
5. Inserting at the start requires traversing the entire list to reach the last node (from an implementation perspective).

Singly Linked List as a Circular Linked List

You are encouraged to read and implement the C code below. It illustrates the pointer arithmetic associated with a circular singly linked list.

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

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

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

Explanation of code:

1. The first two lines of code are the necessary included header files.
2. The next section defines the structure of each self-referential node. It contains a value and a pointer of the same type as the structure.
3. Each structure instance links to other structure objects of the same type.
4. There are different function prototypes for:
   1. Adding an element to an empty linked list
   2. Inserting at the currently pointed position of a circular linked list.
   3. Inserting after a particular indexed value in the linked list.
   4. Removing/Deleting after a particular indexed value in the linked list.
   5. Removing at the currently pointed position of a circular linked list
5. The last function prints each element through a circular traversal at any state of the linked list.

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
  
struct node *insertCurrent(struct node *last, int data)

Explanation of code:

1. For the addToEmpty code, allocate an empty node using the malloc() function.
2. Place the incoming data into the temp node.
3. Assign the temp node to last and set its next pointer to itself so the single node points back to itself.
4. Return the last pointer back to the main() / application context.

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

Explanation of code

1. If the list is empty, hand off to addToEmpty() and return control.
2. Create a temporary node to place after the current node.
3. Link the pointers as shown in the diagram above.
4. Return the last pointer, matching the pattern used in the previous function.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

Explanation of code:

1. If the list is empty, ignore the search key, add the current item as the only node in the list, and return control.
2. In every iteration of the do-while loop, a previous pointer holds the last-traversed result.
3. Only then does the next traversal step occur.
4. The do-while terminates when the target data is found or when temp reaches the last pointer again. The following code block decides what to do with the located item.

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

Explanation of code:

1. If the entire list has been traversed but the item is not found, display an “Element not found” message and return control to the caller.
2. If the target node is found, allocate a new node for the value to insert.
3. Link the previous node to the new node, and link the new node’s next pointer to temp (the traversal variable).
4. This places the new element immediately after the target node in the circular linked list. Control then returns to the caller.

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

Explanation of code

1. To remove the last (current) node, first check whether the list is empty. If it is, no element can be removed.
2. The temp variable advances one link forward.
3. Link the last pointer to the node after the first node.
4. Free the temp pointer to deallocate the unlinked node.

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

Explanation of code

1. As with the previous removal function, first check whether the list is empty. If it is, no element can be removed.
2. Two pointers are assigned specific positions to locate the element to be deleted.
3. The pointers are advanced one behind the other (prev trails temp).
4. The traversal continues until the target element is found or the next pointer reaches the last node again.

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;

Explanation of program

1. If the entire linked list is traversed without finding the target, an “Element not found” message is displayed.
2. Otherwise, the element is unlinked and freed in steps 3 and 4.
3. The previous pointer is linked to the node pointed to by temp’s next pointer (the node after the one being deleted).
4. The temp pointer is then freed.

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;  
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

Explanation of code

1. The peek traversal is not possible if there are zero nodes — the user must first allocate or insert a node.
2. If there is only one node, no traversal is required — the node’s content is printed directly and the while loop does not execute.
3. If there is more than one node, temp prints every item up to the last element.
4. The moment the last element is reached, the loop terminates and the function returns control to main().

Applications of the Circular Linked List

• Implementing round-robin scheduling in system processes and circular scheduling in high-speed graphics.
• Token-ring scheduling in computer networks.
• Used in display units such as digital shop boards that require continuous traversal of data.

FAQs