Check if a linked list is Circular Linked List

By | September 20, 2016

What is Linked List:

Each node points next node in a list.Here node means,it contains data and address of the next node in the list.

What is the node here ?

A node is simple data structure,it contains two elements

  1. Value,it contains.
  2. Address of next node stored in node.

How normal Linked list looks like ?

Every node points to next node.Last node points to nothing/null(dead end)

Sample Linked List Looks like

Sample Linked List Looks like

What is Circular Linked List ?

Every node points to next node and last node points to some node in the linked list.There is no end in the linked list.

Let’s come to question here.We need to find whether given linked list is circular linked list (or) whether it contains any loops.

Linked List Examples

Linked List Examples,Drawn on kid’s Notebook .bear with me 🙂

Remember it is only Singular Linked list problem,we will discuss about Doubly linked list in some other article.

Let’s Discuss the Logic to find the Loop.

I am going to explain full program here.you can simply compile and execute.

#include<stdio.h>
/*Node Data Structure Definition */
struct Node
{
 int data; //It is actual data stored in each node 
 struct Node* next; //It is address to the next node in linked list
};

/*Method which will tell True or false based on verification*/
bool CheckCicularLinkedList(struct Node *head)
{
//if head itself is empty,return true that
//means it is empty linked list.
//simply exit.
if (head == NULL)
return true;
//now let’s copy the next of head element into one temporary node.
//we will start from the second element,will keep on moving to next
//element until we find next element should be equal to head.
//if we matches with root element,we will exit by doing return.

struct Node *node = head->next;
while (node != NULL && node != head)
node = node->next;

if(node == head)
{
Return true;
//we got Loop Here
}
else
{
Return False;
}
}

//Method to create a new node,if we pass data to it.
//Returns address of the new node.
Node *createNewNode(int data)
{
struct Node *temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
//Program Starts Executing from here.All the best

int main()
{
Printf(“Program Started.\n”);
Printf(“Welcome to Verify ,whether given Linked list is circular.\n”);
Printf(“Creation of Circular Linked list is started.\n”);

struct Node* head = createNewNode(20);//first node created
head->next = createNewNode(40);//Second node created
head->next->next = createNewNode(50);//Third node created
head->next->next->next = createNewNode(55);//Fourth node created
struct Node* head = createNewNode(45);//fifth node created
head->next = createNewNode(80);//sixth node created
head->next->next = createNewNode(90);//seventh node created
head->next->next->next = createNewNode(100);//eighth node created

Printf(“Creation of Linked list with 8 Elements Completed\n”);
//Eighth node address is pointing to Head node
//If we comment below line and execute,we get “False”
//otherwise,we get True as it contains loop

Printf(“Making Last Element pointing it to First Element Started\n”);
head->next->next->next->next->next->next->next->next = head;
Printf(“Making Last Element pointing it to Last Element Completed.\n”);
Printf(“Calling CheckCicularLinkedList with root element.\n”);

if( CheckCicularLinkedList(head) )
{
Printf(“Great:You found the Loop in the Linked List.\n”);
}
else
{
Printf(“Excellent:You found the No, Loop in the Linked List.\n”);
}
Printf(“Program Completed Successfully\n”);
return 0;
}

Output:
 Program Started.
 Welcome to Verify ,whether given Linked list is circular.
 Creation of Circular Linked list is started.
 Creation of Linked list with 8 Elements Completed.
 Making Last Element pointing it to First Element Started.
 Making Last Element pointing it to Last Element Completed.
 Great:You found the Loop in the Linked List.

It Seems to be simple program,but it is advisable to write the program on our own.

If you like Simplylearntopics.com and would like to contribute, you can Send article to [email protected]”.It will start appearing on the SimplyLearnTopics.com main page and help other Learners.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

If you like the Article ,Wants to subscribe to our News Letter,Please provide the Email in the below form.we will send the most Interesting Articles to you.

Enter your email address to send you the most Interesting Articles

Delivered by FeedBurner

The following two tabs change content below.

SRINIVAS DARIPELLI

Myself SRINIVAS DARIPELLI. I have 15+ Years of Experience in Programming worked on multiple technologies.Apart from it,I am a blogger, writer, editor, artist and dad 🙂 .I believe in reality.I love to share the Helpful things around the Technology. Feel free to connect with me

One thought on “Check if a linked list is Circular Linked List

  1. daripelli

    Beautifully explained the logic around the linked list that is circular

    Reply

Leave a Reply