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

Introduction to Circular Linked Lists

Circular linked list Advantages

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.

Circular linked list

Advantages

  • 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.

Disadvantages

  • 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;
}; 
circular linked list 1

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 list
struct Node {
int data;
struct Node* next;
// Pointer pointing towards next node
};

//function to print the 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);
}
}

// main function
int 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;
}