Circularly Linked List

Circularly linked list is a linked list where all nodes are connected to form a circle.There is no end or rear or null pointer.

Circularly Linked List

Circular linked list can be implemented in both singly linked list as well as doubly linked list.
The only difference between implementation of a circularly linked list and other linked list is that, Circularly linked list doesn't have a last element instead points to the head.Whereas other linked list points to null in place of the head.

To traverse through all the elements in the circularly linked list, we need to use two loops 

1. One which checks the condition that the head reference is not equal to null
2. Other loop which checks if the loop doesn't repeat. i.e temp variable doesn't equal to head.

Function to push an element into the Circularly linked list 

/* Function to insert a node at the begining of a Circular linked list */ void push(struct node **head_ref, int data) { struct node *ptr1 = (struct node *)malloc(sizeof(struct node)); struct node *temp = *head_ref; ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1; /*For the first node */ *head_ref = ptr1; }

1) Linked List is empty: a) since new_node is the only node in CLL, make a self loop. new_node->next = new_node; b) change the head pointer to point to new node. *head_ref = new_node; 2) New node is to be inserted just before the head node: (a) Find out the last node using a loop. while(current->next != *head_ref) current = current->next; (b) Change the next of last node. current->next = new_node; (c) Change next of new node to point to head. new_node->next = *head_ref; (d) change the head pointer to point to new node. *head_ref = new_node; 3) New node is to be inserted somewhere after the head: (a) Locate the node after which new node is to be inserted. while ( current->next!= *head_ref && current->next->data < new_node->data) { current = current->next; } (b) Make next of new_node as next of the located pointer new_node->next = current->next; (c) Change the next of the located pointer current->next = new_node;

Source: Geeksforgeeks
Also Refer to Tortoise-Hare Algorithm

Tortoise & Hare Algorithm

Tortoise & Hare algorithm is also known as Floyd's Cycle-Finding Algorithm.This is a technique for detecting infinite loops inside a linked list, symlinks, state machines etc.

To detect a loop inside a linked list
Source

• Make a pointer to start of the linked list and call it Hare 
• Make a pointer to the head of the linked list and call it Tortoise 
• advance the Hare by two and the tortoise by one for every interation.
• There's a loop if the Tortoise and Hare meet
• There's no loop if the Hare reaches the end.

Algorithm is intersting as it takes O(n) time and O(1) space.

Python code to understand Tortoise and Hare algorithms
Source

def floyd(f,x0): tortoise=f(x0) hare=f(f(x0)) while tortoise!=hare: tortoise=f(tortoise) hare=f(f(hare)) mu=0 tortoise=x0 while tortoise!=hare: tortoise=f(tortoise) hare=f(hare) mu+=1 lam=1 hare=f(tortoise) while(tortoise!=hare): hare=f(hare) lam+=1 return lam,mu


With this Algorithm we detect the loops and iterations in a circularly linked list as suggested by the name Floyd's Cycle-finding Algorithm.

More Reference: Coding Freak