Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > linked list question

Reply
Thread Tools

linked list question

 
 
junky_fellow@yahoo.co.in
Guest
Posts: n/a
 
      01-22-2008
On Jan 22, 4:08*pm, santosh <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:
> > On Jan 22, 3:19*pm, "Malcolm McLean" <(E-Mail Removed)> wrote:
> >> <(E-Mail Removed)> wrote in message
> >> > Is there any efficient way of finding the intesection point of two
> >> > singly linked lists ?
> >> > I mean to say that, there are two singly linked lists and they meet
> >> > at some point. I want to find out the addres of the node where the
> >> > two linked intersect.

>
> >> > thanks for any help...

>
> >> struct node
> >> {
> >> struct node *next;
> >> void *data;
> >> int flag;

>
> >> }

>
> >> Iterate from start one to then end setting all the flags.
> >> Iterate from start two. When you find a set flag, that's your merge
> >> point.

>
> > In fact, I also thought of similar kind of solution, but there need
> > not be a flag in the node structure. I also thought of using the
> > padding bytes inserted in between the members of a structure and put
> > some pattern in the padding/unused bytes each time a node is
> > traversed. But, there may not be any padding bytes at all.

>
> In addition, padding bytes need not retain their values after a write.
> In fact, I think an attempt to write to them at all invokes undefined
> behaviour


Santosh, Can you please tell me why the padding bytes need not retain
their values after a write ? Also, you wrote that writing to padding
bytes may invoke undefined behaviour. Why is it so ? I could not think
of any reason for that. Can you please tell me the reason behind it.
 
Reply With Quote
 
 
 
 
Ravishankar S
Guest
Posts: n/a
 
      01-22-2008

"Malcolm McLean" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
> <(E-Mail Removed)> wrote in message
> > Is there any efficient way of finding the intesection point of two
> > singly linked lists ?
> > I mean to say that, there are two singly linked lists and they meet at
> > some point. I want to find out the addres of the node where the two
> > linked intersect.
> >
> > thanks for any help...
> >

> struct node
> {
> struct node *next;
> void *data;
> int flag;
> }
>
> Iterate from start one to then end setting all the flags.
> Iterate from start two. When you find a set flag, that's your merge point.
>
> Horrid hack.
> For some reason we cannot carry a flag about. So reverse the bits of the
> next pointer. Almost always you will be able to detect a bit-reversed
> pointer. You keep the start of list one and go through for a second time,
> undoing your bit mangling. Needless to say, the horrid hack is dangerous.
>

I think there may also be a system specific solution depending on where in
the memory map
the dynamically allocated storage is.


 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      01-22-2008
<(E-Mail Removed)> wrote in message
On Jan 22, 4:08 pm, santosh <(E-Mail Removed)> wrote:
> (E-Mail Removed) wrote:


>> In addition, padding bytes need not retain their values after a write.
>> In fact, I think an attempt to write to them at all invokes undefined
>> behaviour

>
>Santosh, Can you please tell me why the padding bytes need not retain
>their values after a write ? Also, you wrote that writing to padding
>bytes may invoke undefined behaviour. Why is it so ? I could not think
>of any reason for that. Can you please tell me the reason behind it.
>

He' s wrong on the reading / writing

memset(x, 0, sizeof(x));

is correct whether x contains padding bytes or not.
as is

memcpy(&y, &x, sizeof(x));

However padding bytes are designed not to be used by the program. So the
compiler could notionally use them for a checksum or something. I doubt that
any compilers actually do this.


--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
Richard Harter
Guest
Posts: n/a
 
      01-22-2008
On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
"(E-Mail Removed)" <(E-Mail Removed)> wrote:

>Hi,
>
> Is there any efficient way of finding the intesection point of two
>singly linked lists ?
>I mean to say that, there are two singly linked lists and they meet at
>some point. I want to find out the addres of the node where the two
>linked intersect.
>
>thanks for any help...


Here is a simple approach. Let A and B be the two lists, and let
count(A) and count(B) be the number of nodes in each list.
Suppose that count(A) >= count(B). Skip count(A)-count(B)
elements of list A to get A'. Now A' and B have the same lengths
so you can compare them element by element until you find the
merge point. This is an O(length of lists) method.

There may be an O(length of distances to merge point) algorithm
but it doesn't occur to me off hand.

Why is this in comp.lang.c?



 
Reply With Quote
 
junky_fellow@yahoo.co.in
Guest
Posts: n/a
 
      01-22-2008
On Jan 22, 4:45*pm, (E-Mail Removed) (Richard Harter) wrote:
> On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>
> "(E-Mail Removed)" <(E-Mail Removed)> wrote:
> >Hi,

>
> > * Is there any efficient way of finding the intesection point of two
> >singly linked lists ?
> >I mean to say that, there are two singly linked lists and they meet at
> >some point. I want to find out the addres of the node where the two
> >linked intersect.

>
> >thanks for any help...

>
> Here is a simple approach. *Let A and B be the two lists, and let
> count(A) and count(B) be the number of nodes in each list.
> Suppose that count(A) >= count(B). *Skip count(A)-count(B)
> elements of list A to get A'. *Now A' and B have the same lengths
> so you can compare them element by element until you find the
> merge point. *This is an O(length of lists) method.
>
> There may be an O(length of distances to merge point) algorithm
> but it doesn't occur to me off hand.
>
> Why is this in comp.lang.c?


great. thanks for the solution.
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-22-2008
"Malcolm McLean" <(E-Mail Removed)> writes:

> <(E-Mail Removed)> wrote in message
>> Is there any efficient way of finding the intesection point of two
>> singly linked lists ?

<snip>
> struct node
> {
> struct node *next;
> void *data;
> int flag;
> }
>
> Iterate from start one to then end setting all the flags.
> Iterate from start two. When you find a set flag, that's your merge point.
>
> Horrid hack.
> For some reason we cannot carry a flag about. So reverse the bits of
> the next pointer. Almost always you will be able to detect a
> bit-reversed pointer.


The traditional way to find an extra flag bit was always just to use
one of the bits in the pointer. The most usual being the least
significant bit since this will often be 0 for link node pointers
(even on word-addressed machines). You can also easily traverse the
list even when the bit is "in use" be one mask operation.

--
Ben.
 
Reply With Quote
 
junky_fellow@yahoo.co.in
Guest
Posts: n/a
 
      01-22-2008
On Jan 22, 5:01*pm, Ben Bacarisse <(E-Mail Removed)> wrote:
> "Malcolm McLean" <(E-Mail Removed)> writes:
> > <(E-Mail Removed)> wrote in message
> >> * Is there any efficient way of finding the intesection point of two
> >> singly linked lists ?

> <snip>
> > struct node
> > {
> > * struct node *next;
> > * void *data;
> > * *int flag;
> > }

>
> > Iterate from start one to then end setting all the flags.
> > Iterate from start two. When you find a set flag, that's your merge point.

>
> > Horrid hack.
> > For some reason we cannot carry a flag about. So reverse the bits of
> > the next pointer. Almost always you will be able to detect a
> > bit-reversed pointer.

>
> The traditional way to find an extra flag bit was always just to use
> one of the bits in the pointer. *The most usual being the least
> significant bit since this will often be 0 for link node pointers
> (even on word-addressed machines). *You can also easily traverse the
> list even when the bit is "in use" be one mask operation.
>


Why do you say that the lsb of the structure pointer will often be 0 ?
For instance, consider a structure that has three char members.
struct test {
char c1;
char c2;
char c3;
};

Can't a compiler allocate an odd address for this structure. I am
using gcc over cygwin. I declared an array of 10 such structures and
printed the address of each of them. I found that some of the
addresses were odd.
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      01-22-2008

"Richard Harter" <(E-Mail Removed)> wrote in message
> Here is a simple approach. Let A and B be the two lists, and let
> count(A) and count(B) be the number of nodes in each list.
> Suppose that count(A) >= count(B). Skip count(A)-count(B)
> elements of list A to get A'. Now A' and B have the same lengths
> so you can compare them element by element until you find the
> merge point. This is an O(length of lists) method.
>

That's the answer.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

 
Reply With Quote
 
Richard Harter
Guest
Posts: n/a
 
      01-22-2008
On Tue, 22 Jan 2008 11:45:16 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter)
wrote:

>On Mon, 21 Jan 2008 23:19:46 -0800 (PST),
>"(E-Mail Removed)" <(E-Mail Removed)> wrote:
>
>>Hi,
>>
>> Is there any efficient way of finding the intesection point of two
>>singly linked lists ?
>>I mean to say that, there are two singly linked lists and they meet at
>>some point. I want to find out the addres of the node where the two
>>linked intersect.
>>
>>thanks for any help...

>
>Here is a simple approach. Let A and B be the two lists, and let
>count(A) and count(B) be the number of nodes in each list.
>Suppose that count(A) >= count(B). Skip count(A)-count(B)
>elements of list A to get A'. Now A' and B have the same lengths
>so you can compare them element by element until you find the
>merge point. This is an O(length of lists) method.
>
>There may be an O(length of distances to merge point) algorithm
>but it doesn't occur to me off hand.


And here is a method that doesn't depend on knowing the list
lengths. As before, let A and B be the list lengths. Traverse A
by one step. Traverse B by three steps, checking to see if it
there is a match with the last element read from A. Traverse A
by five more steps, checking for a match with the last element
read from B. Continue, alternating lists and increasing the
steps by two each time. When a match is found this way we know
the difference of distances to the merge point, m. This gives us
an O(m^2 +D) method where D is the common distance to the merge
point. This result can probably be improved.

The second method is a trifle more complicated but doesn't
require traversing the entire lists.

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-22-2008
"(E-Mail Removed)" <(E-Mail Removed)> writes:

> On Jan 22, 5:01*pm, Ben Bacarisse <(E-Mail Removed)> wrote:

<snip>
>> The traditional way to find an extra flag bit was always just to use
>> one of the bits in the pointer. *The most usual being the least
>> significant bit since this will often be 0 for link node pointers
>> (even on word-addressed machines). *You can also easily traverse the
>> list even when the bit is "in use" be one mask operation.

>
> Why do you say that the lsb of the structure pointer will often be 0 ?
> For instance, consider a structure that has three char members.
> struct test {
> char c1;
> char c2;
> char c3;
> };
>
> Can't a compiler allocate an odd address for this structure.


Yes, but I was talking about linked list node pointers. These will
have at least one pointer in them and, if that is not enough, will
usually be allocated with malloc.

Note "usually". We are in system-specific territory here. You can
probably break this by, for example, having a list node struct with an
odd size and making a packed array of these (using something like
__attribute__((packed)) in gcc). A linked list made from this array
will not all have a 0 LSB.

--
Ben.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments