How to find a node in link list
Author Message
How to find a node in link list

Hello,

I'm using C compiler in unix. We have created a linked list and know
that one of the node does not point to next node but point to one of
the previous node. How can I find this node?

Marcus

Sun, 21 Oct 2001 03:00:00 GMT
How to find a node in link list
: Hello,

: I'm using C compiler in unix. We have created a linked list and know
: that one of the node does not point to next node but point to one of
: the previous node. How can I find this node?

Walk the list printing out the nodes contents?  I've missed something
somewhere, I think.

Will

Sun, 21 Oct 2001 03:00:00 GMT
How to find a node in link list

Quote:

> I'm using C compiler in unix. We have created a linked list and know
> that one of the node does not point to next node but point to one of
> the previous node. How can I find this node?

For example:

typedef struct node {
struct node *next;
/* whatever other data */

Quote:
} NODE, *PNODE;

PNODE   Head;   /* assuming this is filled before call to FindNode */

PNODE   FindNode(void)
{
PNODE   p, q;

for (p = Head, q = NULL; p; p = p->next) {
if (p->next == q)
return p;
q = p;
}
return NULL;

Quote:
}

AriL
--
Humans may send email (if absolutely necessary) to the

Sun, 21 Oct 2001 03:00:00 GMT
How to find a node in link list

Quote:

> I'm using C compiler in unix. We have created a linked list and know
> that one of the node does not point to next node but point to one of
> the previous node. How can I find this node?

Marcus...

"Walk" the list and stop at each node. Pick up the pointer to the next
node. Look back over the portion of the list you've traveled so far and
see if the pointer you're holding is to any of those nodes (or to the
current node). If not, go to the next node and repeat.

If you have difficulty making the code work, post it here with
description of problem.

Morris Dovey
West Des Moines, Iowa USA

Sun, 21 Oct 2001 03:00:00 GMT
How to find a node in link list

Quote:

> Hello,

> I'm using C compiler in unix. We have created a linked list and know
> that one of the node does not point to next node but point to one of
> the previous node. How can I find this node?

If the nodes can store a 'mark field', the solution is (almost) trivial:

break;
}

}

If there's no such thing as a 'mark field', things get a bit more
complicated,
but not all is lost -- the following function traverses a list (with a
loop
somewhere) using _two_ pointers p and q. Pointer p hops from an element
to the next element, while pointer q hops two elements at the time; when
the two pointers compare equal again, pointer p has traversed the loopy
part of the list once. While hopping the list every value of p's next
value
is checked agains a value r. Here it is:

node_t* hop_list(node_t* r) {

node_t* p= r;
node_t* q= r;

do {
if (p->next == r)
return p;

p= p->next;
q= q->next->next;
}
while (p != q);

return NULL;
}

The function above can be used to find the back-pointing element:

}

return NULL;
}

kind regards,

Mon, 22 Oct 2001 03:00:00 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages