c++ code to check whether a list is circular or not

hi all,

i need c++ code to check whether a list is circular or not...
please help

The exact code depends on the implementation of the list, but the algorithm's easy enough, here's pseudocode:

int is_circular(list l)
{
        a=l.head;
        b=a->next;

        while(b != END)
        {
                // List is circular if we end up where we started
                if(b == a)
                {
                       return(1);
                }

                b=b->next;
        }

        return(0); // list is not circular if it ends
}

This will not detect the case when it loops back to the middle of the list. You can have two pointers starting at the head, advance one by one step, two for the other. Check if they meet.

I think that what you mentioned is a list having a loop in it.

Out of curiosity , I decided to look at the standard definition of what exactly we mean by the term Circular list.

Below is what I found:

Some url for the reference:

Hence the above pseudo code, by Corona, prefectly hold true in context to this thread question.

---------- Post updated at 01:30 AM ---------- Previous update was at 12:59 AM ----------

Definitions apart, a practical approach.

The circular list is a specilized version of the linear linked list with a loop into it, hence a small edition to the above pseudo code (per binlib) :

typedef struct node list;
typedef NULL END;

bool is_circular(list l)
{
        a=l.head;
        b=(a->next)->next;

        while((b != END) && (a != b))
        {

                if((b == l) || (a == l)) {
                   /*
                   ** Perfect circular, as per the standard definition.
                   */
                   return 1;
                }

                if (END != b->next) {
                   b=(b->next)->next;
                }
                else {
                   /*
                   ** The list is a linear one.
                   */
                   return 0;
                }
                a=a->next;
        }

        if (END == b) {
           return 0;  //Linear case.
        }
        else { 
           /*
           ** Some kind of loop
           */
           return 1; 
        }

}

hi thanks for the reply. but i have a question that is this pseudo code is the optimal solution to detect the circular list?

The code above is more of a working code , which would be compiled with a little or almost no effort from yourside. Try it.

When compiled, it should be able to tell you (given a pointer to a linked list datastructure) that if the same is a Linear list, a Circular list or a Linked list having a loop into it.

Let me know , if you need further assistance, I'd be glad enough.

Thanks.

In what way would you speed it up? You cannot traverse a linked list any quicker than one node at a time, and cannot find a loop in any less steps than it takes to traverse it.

Am not sure why this is needed? The above algorithm is "hare and tortoise algorithm" where one pointer moves faster 2 nodes at a time and the other slower - 1 node at a time. After the loop, it will detect if there is a loop or will meet the NULL condition.

From within the while-loop , we examined for two cases:

1) A perfect circular condition.

2) A perfect linear condition.

Statement-A:
There is still a remaining case for the 'perfect linear condition' needs to be tested for (END != (b->next)->next); which we are doing with the while-loop condition itself, when the value of b becomes b = (b->next)->next) .

Now What could be the exact conditions when the while-loop ends?

Its the following:

Either
1) (b != END) == FALSE

Or,
2) (a != b) == FALSE

Both these conditions needs to be tested to establish what was the exact condition of the loop-termination to decide the two remaining cases of the list.

The test (b != END) == FALSE definitely needs to be tested to satisfy the statement-A above. Hence this is testing for the Linear case of the list.

The other one is the else-part of it in which the test for ((a != b) == FALSE) is being done and this refers to a case when there is a loop inside the linked list and also that the list is not a 'perfect circular list'. This kind of list assumes a sigma-shape.