Linked List in C – Detect/Find Loop

Linked List in C - Detect or Find Loop.png

Linked List in C – Detect/Find Loop

DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

Linked List in C – Detect/Find Loop :

           We use two pointers current and previous

Pseudo Code:
1. Current pointer initially points to first node(head) of the linked list
2. Previous node initially points to first node(head) of the linked list
3. We traverse current pointer from first node
4. For each node traversed in the linked list with current pointer, we again traverse the linked list from first node till where current pointer is pointing with previous pointer
5. Each time we check whether current node is pointing to previous node
6. If current node points to previous node Then
           Loop is present
Else
           Loop is not present

Source Code :

#include<stdio.h>

//We use two pointers current and previous
//
//Pseudo Code
//1. Current pointer initially points to first node(head) of the linked list
//2. Previous node initially points to first node(head) of the linked list
//3. We traverse current pointer from first node
//4. For each node traversed in the linked list with current pointer, we again traverse the linked list from first node till where current pointer is pointing with previous pointer
//5. Each time we check whether current node is pointing to previous node
//6. If current node points to previous node Then
//		Loop is present
//	Else
//		Loop is not present

struct node
{
    	//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
	    int data;
    	struct node *next;
};

struct node *head=NULL;
//Declared as global variable since it is accessed by multiple functions

struct node* findloop()
{
    	//Function to detect whether loop is present in the linked list

    	struct node *current=head;

    	while(current->next!=NULL)
    	{
        		struct node *previous=head;

        		while(previous!=NULL && previous!=current)
        		{
            			if(current->next ==previous)
            			{
                				printf("Loop Found");
                				return;
            			}
            			previous=previous->next;
        		}
        	current=current->next;
    	}
    	printf("\nLoop Not Found");
}

void print()
{
    	//This funtion is used to print the data in each of the node in the linked list
    	//Process of moving from one node to another node is called as traversing
    	struct node *temp=head;
    	printf("\nList:");
    	while(temp!=NULL)
    	{
        		printf("\n%d ",temp->data);
        		temp=temp->next;		
    	}
}

int main()
{
    	struct node *one = (struct node*)malloc(sizeof(struct node));
    	struct node *two = (struct node*)malloc(sizeof(struct node));
    	struct node *three = (struct node*)malloc(sizeof(struct node));
    	struct node *four = (struct node*)malloc(sizeof(struct node));
    	//Four nodes are created

    	head=one;
    	//head pointer points to node one of the linked list

    one->data=1;
    	one->next=two;

    	two->data=2;	
    	two->next=three;

    	three->data=3;
    	three->next=four;

    	four->data=4;
    	four->next=one;
    	//one->two->three->four->one->two->....
    	//There are only four nodes in the linked list
    	//But the fourth node points to first node "one" which forms the loop

    	//print();	
    	//Calling the print function will print the data in the nodes of the linked list infinitely	

    	findloop();
    	//Calling the function findloop() to detect the presence of loop in the linked list

    	return 0;
}

Output :

Loop Found

[ YOU MAY ALSO LIKE ]

Leave a Reply