A linked list with a loop

[snb021]

Theoretically, given a linked list, how can you tell if there is a "loop" in it (i.e. one node is being pointed to by more than one other node)??

Then, how can you tell where the "loop" starts??

 

[marsd]

You are talking about a linear list I hope?
Seems pretty straightforward..you would use a nested
loop and walk through the list comparing addresses.
I did it this way quickly, in response to your
question:

int checkforDupe(struct FOO *ppt) {
int y, j;
char afoo[30], bfoo[30];
struct FOO *tmp, *ttmp;

     for (tmp = ppt, y = 0 ; tmp != NULL ; tmp = tmp->nxt, y++) {
         sprintf(afoo,"%p",tmp);
         for (ttmp = tmp->nxt ; ttmp != NULL ; ttmp = ttmp->nxt) {
             sprintf(bfoo,"%p",ttmp);
             printf("Comparing addresses at %s :: %s\n", afoo, bfoo);
               if ( (j = strcmp(afoo,bfoo)) == 0) {
                    return y;
               }
          }
      }

return 0;
}

 

[marsd]

Oops.
There's a logic problem there.
You need to exempt the current pointer from itself
and search from the beginning of the list in the inner
loop.
My bad.

 

[marsd]

This seems to have it.

int checkforDupe(struct FOO *ppt) {
int y, j, x = 0;
char afoo[30], bfoo[30];
struct FOO *tmp, *ttmp;

     for (tmp = ppt, y = 0 ; tmp != NULL ; tmp = tmp->nxt, y++) {
         sprintf(afoo,"%p",tmp);
         for (ttmp = ppt->nxt, x = y < 1 ? 0 : 1 ; ttmp != NULL ; ttmp = ttmp->nxt , x++) {
              sprintf(bfoo,&quot;%p&quot;,ttmp);
              printf(&quot;Comparing addresses at OUT = %s :: IN =  %s\n&quot;, afoo, bfoo);
               printf(&quot;INNER: %d and  OUTER: %d\n&quot;,x,y); 
               if (x != y && (j = strcmp(afoo,bfoo)) == 0) {
                    return y;
               }
          }
      }

return 0;
}

Anybody:
Is there a more straightforward way?

 

[Zyrenthian]

int GetCount(node* begin, node* find)
{
if(!begin)
return 0;

if(begin == find)
return 1+GetCount(begin->next,find);

}

bool IsDupe(node* p)
{
return(GetCount(head,p) > 1)
}

A little recursion never hurt noone (yes it is a double negative )
Matt

 

[Zyrenthian]

Oh... btw... some mods will need to be done because if a loop exists the recursion wont stop (eek). I will repost when I have a solution

Matt

 

[Zyrenthian]

void GetCount(node* begin, node* find,int& count)
{
if(count>1)
return;

if(!begin)
return 0;

if(begin == find)
{
count++;
GetCount(begin->next,find,count);
}

}


bool IsDupe(node* p)
{
int count = 0;
GetCount(head,p,count);
return count>1;
}

 

[lionelhill]

Hey, nice interesting question!

As previous writers have pointed out, the real problem is that a one-directional linked list that bites into the middle of itself is a dangerous thing! Anyone processing a linked list like that to the end is going to come to grief because there IS no end.

I suppose you could do something like scan along the linked list building a second list, an Ordered!! list of the nodes you find. Because you are ordering, you will automatically be able to identify when you have a second point to a node you've already encountered. The loop that's searching for this will have two possible end-conditions.
(1) I've just found a second reference to the same node. This linked list has got a circular bit.
(2) I've just gone off the end of the list. This is a linear list.

Having said that circular lists are dangerous, they are also very useful. Consider a pacman figure who needs to keep opening and closing his mouth (for ever). Aranging the pictures in a circular linked list makes perfect sense, because each game-loop you just progress to the next node, getting the next picture in the animation. There is never an end, and the whole process costs next to nothing.

 

[Zyrenthian]

I still dont think my recursion works Oh well. What I would suggest instead is modify the insertion algorithm to check for the node before inserting it.

Matt

 

[snb021]

Thanks for your insight on the question guys!