Detection of Looping in Linked Lists

A Linked List is basically data stored in a linear form, like a list or an array.
It can be considered as the following structure

 [illustration only]

The  address(this) is the memory location of the initialized [but not yet assigned] linked list object. When there are no values added yet in a linked list, then address(next) value will be null. This will always be null for the last object structure in the list ( hint:: That's how you know you have reached the last element :) )

Alrighty then, you can do the standard functions to traverse the list and get the values.

Now for the mind bender..
say there is some sort of data corruption or a wrong input, and the list has a loop in it !

It becomes an inadvertent loop. How do you find a loop in your linked system?

There are ways to find out, and then there are ways to find out ;)
For an explanation for all of the ways you can do it, please refer  http://ostermiller.org/find_loop_singly_linked_list.html

The best method to do it is the "Hare and Tortoise" Algorithm (Floyd's Cycle Finding Algorithm).

The method basically uses 2 incrementers, one of them incrementing by one and the other incrementing by two. Consider the Red Spot as the 1st incrementer and the Blue Spot as the 2nd.

At the 0th iteration,

When iterator step = 1

When iterator step = 2

When iterator step = 3

And Voila !!! If we check the object values of the objects pointed by the two iterators, and we determine them to be equal, we have the position where the loop occurs ! This happens because the second iterator goes twice as fast around the loop and catches up to the first one if there is indeed a loop.

And since it takes only one iteration of the main list to actually determine the loop presence, the algorithm is said to be of O(n) Time Complexity. Also it takes only a fixed number of variables (two iterators) to determine the loop presence.


Pseudo Code Snippet


Iterator i = list.Iterator(); 1-step
Iterator j = list.Iterator(); 2-step


while{
        // increment iterator by two (one step at a time)

        if(j has next element){
            j= j.next();
        }else{
          // reached end of list via iterator j .. return, no loop present
        }

        if(j has next element){
            j= j.next();
        }else{
            // reached end of list via iterator j .. return, no loop present
        }


        // actually the conditional check code is not required since 
        // whatever the iterator i is going through, j has already gone through
        // but its still left in for illustration purpose


        // increment iterator by one
        if(i has next element){
            i= i.next();
        }else{
           // reached end of list via iterator i .. return, no loop present
        }

        // Check the nodes are equal
        if(node(i) == node(j)){
                // Nodes are identical ..  loop found .. return loop position (i or j)
        }
}