Is it circular link list?

This is a discussion on Is it circular link list? within the C Programming forums, part of the General Programming Boards category; How do I know, a given link list is a circular link list? Thanks, Al...

  1. #1
    Registered User
    Join Date
    Aug 2001
    Posts
    8

    Lightbulb Is it circular link list?

    How do I know, a given link list is a circular link list?

    Thanks,
    Al

  2. #2
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    A linked list is a set of items where each item is part of a node that also contains a link to a node.
    We most often work with lists that correspond to a simple sequential arrangement of the items, adopting one of the following conventions for the link in the final node:
    • It is a null link that points to no node.
      It refers to a dummy node that contains no item.
      It refers back to the first node, making the list a circular list.
    Excerpts from Sedgewick.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    412
    Pick any node in the list. Keep traversing the list in one direction until you either hit NULL, or you return to the node you started from. If you hit NULL, it's not a circular list, if you got back to where you began, it is.

  4. #4
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230
    THis might work...untested and all...

    Code:
    current = first;
    
    while(current->next != first)
    {
    
         if(current->next == NULL)
         {
               printf("normal list!\n");
               break;
         }
    
         else
               current = current->next;
    }
         if(current->next != NULL);
              printf("circular, baby!\n");
    Last edited by -KEN-; 11-01-2001 at 06:33 PM.

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Your test fails in this example:

    node1 -> node2 -> node3 -> node4 ->node5 ->node3 ->

    See? If your list is circular, but not a first -> last circular, then your loop fails. This is how you test for a circular list, with _the least_ resources involved:
    Code:
    Node *n1, *n2;
    
    n1 = n2 = myListToTestForCircularity;
    do {
       if( n2->next && n2->next->next )
       {
          n2 = n2->next->next;
          n1 = n1->next;
       }
       if( n1 == n2 ) {
          printf("Is a loop.");
       }
       else
       {
          printf("Not a loop.");
          break;
       }
    } while( n1 != n2 && !loop );
    See, it works like this:

    Advance 1 pointer 1 time.
    Advance another pointer twice.
    If pointer 1 ever equals pointer 2, you have a loop.

    JC Lawrence taught me that one. Props to him.

    Quzah.

  6. #6
    Just one more wrong move. -KEN-'s Avatar
    Join Date
    Aug 2001
    Posts
    3,230
    always tryin to show me up

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how do i reverse a circular double linked list
    By kobra_swe in forum C Programming
    Replies: 13
    Last Post: 04-08-2008, 05:20 PM
  2. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 11:01 PM
  3. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 10:11 AM
  4. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21