LINKED LIST - DETECT AND REMOVE LOOP

We all know how the food chain in an environment works. The carnivores feed on the herbivores and the omnivores eat the carnivores and eventually the omnivores die becoming food for the herbivores to survive. On the contrary, these kind of loops are not as necessary in the computer world. This article explains how loops are detected in a linked list and how they are removed. The following diagram shows how a loop looks like in a linked list.

The main concept to detect and remove a loop in a linked list is to use a fast and a slow pointer. While a fast pointer will jump two nodes at a time, the slow pointer will move one node at a time in one iteration of a while loop construct that will be used. A loop is detected if these two pointers ever meet. Once the loop is detected, the start of the loop can help us remove the detected loop in the linked list. This is called the Floyd’s Cycle-Finding Algorithm.

Detecting the start of a loop in a linked list has the following steps that are followed:

Step A: Two pointers must be initialized with the slow pointer abbreviated to ‘S’ and fast pointer abbreviated to ‘F’. Each of these pointers will initially be set to the start or head reference of the linked list.

Step B: ‘S’ moves at one node per iteration while ‘F’ moves two nodes per iteration of the while or looping construct.

Step C: If at some ith iteration, the two pointers ‘F’ and ‘S’ point to the same node, then the loop is detected.

Once the loop is detected using the above method, the next step is to detect the starting of the loop and it is done as follows:

Step D: Initialize the pointer ‘S’ to the start of the linked list or the head reference of the linked list and ‘F’ remains wherever it was pointing to in Step C.

Step E: Pointers ‘S’ and ‘F’ will move forward one node per iteration until they point to the same node in the list.

Step F: The node at which the two pointers meet will be the start of the loop.

For example, consider the linked list with the loop as seen in the figure shown above. The starting point of the loop is at node that has the data=20. This is to be detected and removed to make the linked list to have the element as shown in the figure below.

The concept of detecting the loop is seen in the below pictorial representation from Step 1 to Step 5. While the removing of the detected loop is seen in Step A through Step C.

The function definition “detectAndRemoveLoop” returns an integer to the calling function and accepts the head reference pointer of the linked list as its input parameters.

Note: The linked list is made of data structures called “node” with the data stored in the node denoted by “data” and the link to the next node stored in “next”.

DETECTING THE START OF A LOOP IN A LINKED LIST

int detectAndRemoveLoop(struct node *head)

{

struct node *S=head;

struct node *F=head;

while( S && F && F->next)

{

                            S = S -> next;

                            F = F ->next ->next;

                            if( S == F )

                            {

                                          removeLoop(F,head);

                                          return 1;

                            }

             }

             return 0;

}

Here, as explained earlier, the S and F node pointers are initialized to the head pointer. A while loop runs until the condition is satisfied. The condition being that the slow pointer, the fast pointer and the next node to the fast pointer is not NULL. If this condition is true, the control of the program enters the while loop else returns a 0 back to the function call shifting the control back to the calling function. When the control enters the while loop, the S pointer moves one node and the F pointer moves two nodes in one iteration. If these two pointers point to the same node, then the removeLoop function is called that takes the pointer to the meeting point of the slow and the fast pointers along with the head reference node pointer as its parameters to remove the loop that is detected. This function has no return types.

REMOVE A LOOP FROM THE LINKED LIST

void removeLoop(struct node *loopNode, struct node *head)

{

             struct node* S;

struct node* F;

             S = head;

            while (S != F->next)

            {

                           S = S ->next;

                           F = F->next;

            }

            F->next = NULL;

}

In this function, two pointers are declared with S and F(as seen in the Figure above used to represent Step A to C). The S pointer will go back to the head of the linked list which is done by initializing S to head. A while construct checks for the condition that the S pointer does not go past the F pointer. If the condition is true, the S and the F pointers move forward one node at every iteration. If the condition becomes false, then the end of loop is reached and the “next” pointer to that node is made NULL representing the end of a linked list without loop.