Circular Linked List: Advantages with C Program Example

Details

What is a Circular Linked List?

A circular linked list is a sequence of nodes arranged such a way that each node can be retraced to itself. Here a "node" is a self-referential element with pointers to one or two nodes in iI'simmediate 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 most simple circular linked list, is a node which traces only to itself as shown

In this circular linked list tutorial, you will learn:

Basic Operations

The basic operations on a circular linked list are:

  1. Insertion
  2. Deletion and
  3. Traversal

In the next section, you will understand insertion of a node, and the types of insertion possible in a Circular Singly Linked List.

Insertion Operation

Initially, you need to create one node which points to itself as shown in this image. Without this node, insertion creates the first node.

Next, there are two possibilities:

For inserting at the beginning/end of the circular linked list, that is at the position where the first-ever node was added,

NOTE: The pointer that is the token master or the beginning/end of the circle can be changed. It will still return to the same node on a traversal, discussed ahead.

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, let us insert "VALUE2" after the node with "VALUE0". Let us assume that the starting point is the node with "VALUE0".

NOTE: Since there is a cyclic arrangement, inserting a node involves the same procedure for any node. The pointer that completes a cycle completes the cycle just like any other node.

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

Let us assume a 3-node circular linked list. The cases for deletion are given below:

Deletion at the beginning/end:

  1. Traverse to the first node from the last node.
  2. To delete from the end, there should be only one traversal step, from the last node to the first node.
  3. Delete the link between the last node and the next 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

STEPS 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 till 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. Link its previous node with the next node pointed by the current node (with VALUE1).

STEP 3) Free or deallocate the current node.

Traversal of a Circular Linked List

To traverse a circular linked list, starting from a last pointer, check if the last pointer itself is NULL. If this condition is false, check if there is only one element. Otherwise, traverse using a temporary pointer till the last pointer is reached again, or as many times as needed, as shown in the GIF 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 operations since beginning and end coincide. Algorithms such as the Round Robin scheduling can neatly eliminate processes which are queued in a circular fashion without encountering dangling or NULL-referential pointers.
  3. Circular linked list also performs all regular functions of a singly linked list. In fact, circular doubly linked lists discussed below can even eliminate the need for a full-length traversal to locate an element. That element would at most only be exactly opposite to the start, completing just half the linked list.

Singly Linked List as a Circular Linked List

You are encouraged to attempt to read and implement the code below. It presents the pointer arithmetic associated with circular linked lists. 

#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 describes the structure of each self-referential node. It contains a value and a pointer of the same type as the structure.
  3. Each structure repeatedly links to 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 addEmpty code, allocate an empty node using the malloc function.
  2. For this node, place the data to the temp variable.
  3. Assign and link the only variable to the temp variable
  4. Return the last element 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 there is no element to insert, then you should make sure to add to an empty list and return control.
  2. Create a temporary element to place after the current element.
  3. Link the pointers as shown.
  4. Return the last pointer as 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 there is no element in the list, ignore the data, add the current item as the last item in the list and return control
  2. For every iteration in the do-while loop ensure that there is a previous pointer that holds the last-traversed result.
  3. Only then can the next traversal occur.
  4. If the data is found, or temp reaches back to the last pointer, the do-while terminates. The next section of code decides what has to be done with the 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, yet the item is not found, display an "item not found" message and then return control to the caller.
  2. If there is a node found, and/or the node is not yet the last node, then create a new node.
  3. Link the previous node with the new node. Link the current node with temp (the traversal variable).
  4. This ensures that the element is placed after a particular node in the circular linked list. Return 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 only the last (current) node, check if this list is empty. If it is, then no element can be removed.
  2. The temp variable just traverses one link forward.
  3. Link the last pointer to the pointer after the first.
  4. Free the temp pointer. It deallocates the un-linked last pointer.
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, check if there is no element. If this is true, then no element can be removed.
  2. Pointers are assigned specific positions to locate the element to be deleted.
  3. The pointers are advanced, one behind the other. (prev behind temp)
  4. The process continues until an element is found, or the next element retraces to the last pointer.
    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 element found after traversing the entire linked list, an error message is displayed saying the item was not found.
  2. Otherwise, the element is delinked and freed in steps 3 and 4.
  3. The previous pointer is linked to the address pointed as "next" by the element to be deleted (temp).
  4. The temp pointer is therefore deallocated and 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 or traversal is not possible if there are zero needed. The user needs to allocate or insert a node.
  2. If there is only one node, there is no need to traverse, the node's content can be printed, and the while loop does not execute.
  3. If there is more than one node, then the temp prints all the item till the last element.
  4. Moment the last element is reached, the loop terminates, and the function returns call to the main function.

Applications of the Circular Linked List

 

YOU MIGHT LIKE: