# Introduction to Circular linked list

## Circular Linked Lists

Circular linked lists are just like singly linked lists but all of its nodes are connected to form a circle

The circular linked list is also two types.

• Singly linked list
• Doubly linked list

In a singly circular linked list, the address of the last node’s next pointer rather than being NULL is pointed towards the address of the head node.

Similarly, in a doubly linked list, in addition to the address of the last node’s next pointer being the address of head node. The previous pointer of the head node is provided to the address of the last node.

• Any node can be starting point and we can still traverse the whole list
• It can also deem to be useful for implementation as queues as rather than maintaining the Front and Rear, we can use a circular linked list and just maintain the pointer to the first inserted node and it can simply be the next node to the last node.
• Circular linked lists are commonly used in OS’es for the task that requires repeatedly to be executed by OS.

• Doubly Linked List is faster in getting previous node information due to previous pointer.
• Doubly Linked List can traverse in both forward and backward direction.
• Finding end of list and loop control is harder (no NULL  to mark beginning and end).
• The entire list can be traversed starting from any node (traverse means visit every node just once).

So, when we want to traverse the node in a circular linked list so we will traverse in a singly circular linked list so, it is just like the singly linked list where tail nodes hold the address of head node so traversal can be done circularly in only one direction.

And the Traversal in a doubly linked list can be done circularly in both directions.

## Creation of Circular Linked Lists

Creation of the list node is same as singly or doubly only implementation with the struct is different

### Defining struct for Circular Linked List (Singly)

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

### Defining struct for Circular Linked List (Doubly)

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

### Function to traverse in a Circular linked list

`void display(struct Node *head) {     struct Node *temp = head;     if (head != NULL)     {         do        {             printf("%d ", temp->data);             temp = temp->next;         }         while (temp != head);     } }`

### Code of Circular linked list

`//We are creating program for linked list creation#include <stdio.h>#include <stdlib.h>//stdlib used to provide a declaration of ‘malloc’// structure of Circular linked liststruct Node {     int data;     struct Node* next;     // Pointer pointing towards next node};//function to print the Circular linked listvoid display(struct Node *head) {     struct Node *temp = head;     if (head != NULL)     {         do        {             printf("%d ", temp->data);             temp = temp->next;         }         while (temp != head);     } }// main functionint main() {     //creating 4 pointers of type struct Node    //So these can point to address of struct type variable    struct Node* head = NULL;     struct Node* node2 = NULL;     struct Node* node3 = NULL;     struct Node* node4 = NULL;     // allocate 3 nodes in the heap     head =  (struct Node*)malloc(sizeof(struct Node));     node2 = (struct Node*)malloc(sizeof(struct Node));     node3 = (struct Node*)malloc(sizeof(struct Node));     node4 = (struct Node*)malloc(sizeof(struct Node));     /* Using malloc method we have created 4 memory blocks    Each memory block is of type struct and has int data and Pointer of type Node    So it can point towards a node type struct.       head           node2           node3             node4         |                |               |               |         |                |               |               |     +---+-----+     +----+----+     +----+----+     +----+----+     |data|next|     |data|next|     |data|next|     |data|next|     +---+-----+     +----+----+     +----+----+     +----+----+    # As of now data has garbage value and its pointer   points towards random addresses*/    head->data = 5; // data set for head node     head->next = node2; // next pointer assigned to address of node2     node2->data = 10;     node2->next = node3;     node3->data = 12;    node3->next = node4;     node4->data = 3;    node4->next = head;     //last node assigned to head node as linked list ends here    //this completes Circular linked list    /* Finally Circular linked list looks like       head           node2           node3             node4         |                |               |               |         |                |               |               |     +---+-----+     +----+----+     +----+----+     +----+----+     | 5 | next|---->| 10 | next|--->|12 | next|---->| 3 | next| ---> |    +---+-----+     +----+----+     +----+----+     +----+----+      |        ^                                                            |        |                                                            |        -------------------------------------------------------------    */    display(head);    return 0; } `