Circular Linked List in C

Circular linked list is like a regular linked list except its last node points to the first node. Generally the last node of linked list points to NULL. But the last node of circular linked list points back to the first node.

If you traverse a regular linked list, you can not come back to a previous node. You can not traverse back. And you can not go anywhere from the last node. But in circular linked list, you can come back to any previous node as the last node points back to the first node.

We keep a pointer to access the linked list. In regular linked, head points to the first node. But for circular linked list, its better to keep a pointer pointing to the last node.

If we keep a head pointer pointing to the first node, then to insert a new node at the end, we have to traverse the whole list. But for last pointer pointing to the last node, we can insert a new node at the front or at the end without traversing the list.

Circular Linked List Operations

Traverse the Circular Linked List

Normally we traverse a linked list from head to NULL. But in circular linked list, no node points to NULL. So at the beginning we have to save the node where we started traversal. We have to stop we when we came back to the starting node.

/*Print the linked list*/
void print_list(struct node *in_node) {
  struct node *start = in_node;

  do {
    printf("%d->", in_node->val);
    in_node = in_node->next;
  } while (start != in_node);
  
  printf("\n");
}

Insert at the Front

1. Create the new node (new_node) and set the value of the node (new_node->val = val)
2. If last is NULL, point last to the new node (last = new_node) and point the new node to itself (new_node->next = new_node).
3. Else, point the new node where the last node is pointing to (new_node->next = last->next). And point the last node to the new node (last->next = new_node).

The Program

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

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

/*Print the linked list*/
void print_list(struct node *in_node) {
  struct node *start = in_node;

  do {
    printf("%d->", in_node->val);
    in_node = in_node->next;
  } while (start != in_node);
  
  printf("\n");
}

/*Insert an element at the front of the list*/
void insert_front(struct node **last, int value) {
  /*Allocating memory for the new node*/
  struct node * new_node = (struct node *)malloc(sizeof(struct node));

  if (new_node == NULL) {
    printf("Failed to insert element. Out of memory");
  }

  new_node->val = value;
    
  if(*last == NULL) {
    /*List is empty*/
    *last = new_node;
    new_node->next = new_node;
    return;
  }

  /*Pointing the new node to where the last node is currently pointing to*/
  new_node->next = (*last)->next;

  /*Pointing last node to new node.*/
  (*last)->next = new_node;
}

void main()
{
  int count = 0, i, val;
  struct node * last = NULL;

  printf("Enter number of elements: ");
  scanf("%d", &count);

  for (i = 0; i < count; i++)
  {
    printf("Enter %dth element: ", i);
    scanf("%d", &val);
    insert_front(&last, val);
  }

  printf("Linked List: ");
  print_list(last->next);
}

This is the output of the program.

Insert at the End

Inserting at the end is exactly same as inserting at front. You have to make the newly inserted node the last node. Just point the last pointer to the new node.

/*Insert an element at the end of the list*/
void insert_end(struct node **last, int value) {
  /*Allocating memory for the new node*/
  struct node * new_node = (struct node *)malloc(sizeof(struct node));

  if (new_node == NULL) {
    printf("Failed to insert element. Out of memory");
  }

  new_node->val = value;
    
  if(*last == NULL) {
    /*List is empty*/
    *last = new_node;
    new_node->next = new_node;
    return;
  }

  /*Pointing the new node to where the last node is currently pointing to*/
  new_node->next = (*last)->next;

  /*Pointing last node to new node.*/
  (*last)->next = new_node;
  
  /*Make the new node last node*/
  *last = new_node;
}

Inserting in the middle of a circular linked list is same as inserting into a regular linked list.

If you also want to contribute, click here.