Linked List

[Mark A. Gibbs]

Re: Linked List

Siemel Naran wrote:
[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>
>[color=green]
>>node* node = yourfirstnode;
>>node* node5 = node->next->next->next->next;[/color]
>
>
> What happens on a list of 0 to 4 elements?[/color]

As he noted:

"P-code, and without error checking (assumes list is at least 5 long):"

mark

[Mark A. Gibbs]

Re: Linked List

Siemel Naran wrote:
[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>
>[color=green]
>>node* node = yourfirstnode;
>>node* node5 = node->next->next->next->next;[/color]
>
>
> What happens on a list of 0 to 4 elements?[/color]

As he noted:

"P-code, and without error checking (assumes list is at least 5 long):"

mark

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yKZbc.1487 0
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;
>
> for(;;)
> {
> if(node5->next == 0)
> {
> return node->val;
> }
> node = node->next;
> node5 = node5->next;
> }[/color]

Is it really faster than the 2 pass method? In the 2 pass method, first
visit all N elements for a total of N calls to const_iterator: :operator++.
Then you perform N-5 more calls to operator++. But in the 1 pass method,
you perform N calls to const_iterator: :operator++ on node, and N-5 on node5.
So don't they both have the same running time?

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yKZbc.1487 0
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;
>
> for(;;)
> {
> if(node5->next == 0)
> {
> return node->val;
> }
> node = node->next;
> node5 = node5->next;
> }[/color]

Is it really faster than the 2 pass method? In the 2 pass method, first
visit all N elements for a total of N calls to const_iterator: :operator++.
Then you perform N-5 more calls to operator++. But in the 1 pass method,
you perform N calls to const_iterator: :operator++ on node, and N-5 on node5.
So don't they both have the same running time?

[Pete]

Re: Linked List

Siemel Naran wrote:[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>[color=green]
>> node* node = yourfirstnode;
>> node* node5 = node->next->next->next->next;
>>
>> for(;;)
>> {
>> if(node5->next == 0)
>> {
>> return node->val;
>> }
>> node = node->next;
>> node5 = node5->next;
>> }[/color]
>
> Is it really faster than the 2 pass method? In the 2 pass method,
> first visit all N elements for a total of N calls to
> const_iterator: :operator++. Then you perform N-5 more calls to
> operator++. But in the 1 pass method, you perform N calls to
> const_iterator: :operator++ on node, and N-5 on node5. So don't they
> both have the same running time?[/color]

No, it really wouldn't be faster much if at all, but it's much more
"elegant" IMHO.

- Pete

[Pete]

Re: Linked List

Siemel Naran wrote:[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>[color=green]
>> node* node = yourfirstnode;
>> node* node5 = node->next->next->next->next;
>>
>> for(;;)
>> {
>> if(node5->next == 0)
>> {
>> return node->val;
>> }
>> node = node->next;
>> node5 = node5->next;
>> }[/color]
>
> Is it really faster than the 2 pass method? In the 2 pass method,
> first visit all N elements for a total of N calls to
> const_iterator: :operator++. Then you perform N-5 more calls to
> operator++. But in the 1 pass method, you perform N calls to
> const_iterator: :operator++ on node, and N-5 on node5. So don't they
> both have the same running time?[/color]

No, it really wouldn't be faster much if at all, but it's much more
"elegant" IMHO.

- Pete

[David Harmon]

Re: Linked List

On Mon, 05 Apr 2004 00:42:42 GMT in comp.lang.c++, "Siemel Naran"
<SiemelNaran@RE MOVE.att.net> wrote,[color=blue]
>Is it really faster than the 2 pass method? In the 2 pass method, first
>visit all N elements for a total of N calls to const_iterator: :operator++.
>Then you perform N-5 more calls to operator++. But in the 1 pass method,
>you perform N calls to const_iterator: :operator++ on node, and N-5 on node5.
>So don't they both have the same running time?[/color]

Nobody said it was faster. The problem spec said "in one pass".
The question is, with both pointers running through the list like that
does it count as one pass, or two passes running not quite in parallel?

[David Harmon]

Re: Linked List

On Mon, 05 Apr 2004 00:42:42 GMT in comp.lang.c++, "Siemel Naran"
<SiemelNaran@RE MOVE.att.net> wrote,[color=blue]
>Is it really faster than the 2 pass method? In the 2 pass method, first
>visit all N elements for a total of N calls to const_iterator: :operator++.
>Then you perform N-5 more calls to operator++. But in the 1 pass method,
>you perform N calls to const_iterator: :operator++ on node, and N-5 on node5.
>So don't they both have the same running time?[/color]

Nobody said it was faster. The problem spec said "in one pass".
The question is, with both pointers running through the list like that
does it count as one pass, or two passes running not quite in parallel?

[Pete]

Re: Linked List

Siemel Naran wrote:[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>[color=green]
>> node* node = yourfirstnode;
>> node* node5 = node->next->next->next->next;
>>
>> for(;;)
>> {
>> if(node5->next == 0)
>> {
>> return node->val;
>> }
>> node = node->next;
>> node5 = node5->next;
>> }[/color]
>
> Is it really faster than the 2 pass method? In the 2 pass method,
> first visit all N elements for a total of N calls to
> const_iterator: :operator++. Then you perform N-5 more calls to
> operator++. But in the 1 pass method, you perform N calls to
> const_iterator: :operator++ on node, and N-5 on node5. So don't they
> both have the same running time?[/color]

BTW, this exercise is a good example of a good reason to use a doubly linked
list, because it's easy to go either forwards or back depending on the
situation. The extra memory used for the extra pointer per node really isn't
an issue, usually.

- Pete

[Pete]

Re: Linked List

Siemel Naran wrote:[color=blue]
> "Pete" <x@x.x> wrote in message news:yKZbc.1487 0
>[color=green]
>> node* node = yourfirstnode;
>> node* node5 = node->next->next->next->next;
>>
>> for(;;)
>> {
>> if(node5->next == 0)
>> {
>> return node->val;
>> }
>> node = node->next;
>> node5 = node5->next;
>> }[/color]
>
> Is it really faster than the 2 pass method? In the 2 pass method,
> first visit all N elements for a total of N calls to
> const_iterator: :operator++. Then you perform N-5 more calls to
> operator++. But in the 1 pass method, you perform N calls to
> const_iterator: :operator++ on node, and N-5 on node5. So don't they
> both have the same running time?[/color]

BTW, this exercise is a good example of a good reason to use a doubly linked
list, because it's easy to go either forwards or back depending on the
situation. The extra memory used for the extra pointer per node really isn't
an issue, usually.

- Pete

[Alf P. Steinbach]

Re: Linked List

* subscrib_77@hot mail.com (source) schriebt:[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.[/color]

What is your definition of "one pass", and does this need to be
non-destructive?

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Alf P. Steinbach]

Re: Linked List

* subscrib_77@hot mail.com (source) schriebt:[color=blue]
> function that would: return the 5th element from the end in a singly
> linked list of integers, in one pass, and then provide a set of test
> cases
> against that function.[/color]

What is your definition of "one pass", and does this need to be
non-destructive?

--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yF2cc.1528 4[color=blue]
> Siemel Naran wrote:[/color]
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;
>
> for(;;)
> {
> if(node5->next == 0)
> {
> return node->val;
> }
> node = node->next;
> node5 = node5->next;
> }[/color]
[color=blue][color=green]
> > Is it really faster than the 2 pass method? In the 2 pass method,
> > first visit all N elements for a total of N calls to
> > const_iterator: :operator++. Then you perform N-5 more calls to
> > operator++. But in the 1 pass method, you perform N calls to
> > const_iterator: :operator++ on node, and N-5 on node5. So don't they
> > both have the same running time?[/color][/color]

Seems the 2 pass method you maintain an index for looping from [0, N-5) but
in the 1 pass method you don't. So based on that the 1 pass method might be
faster, though the improvement is probably negligible.

[color=blue]
> BTW, this exercise is a good example of a good reason to use a doubly[/color]
linked[color=blue]
> list, because it's easy to go either forwards or back depending on the
> situation. The extra memory used for the extra pointer per node really[/color]
isn't[color=blue]
> an issue, usually.[/color]

If going back is not a common operation, the single list could be better.
Anyway, the point of these 'clever' interview questions is not always to
mimic reality, but to see how you think through problems, especially the
logic questions.

Anyway, I think if you just store the value of the pointer in one pass, you
could get better


node* node = yourfirstnode;
node* node5 = node->next->next->next->next;

T * last[5] = { &node->val, &node->next->val, ... };

for(int i=0; ; i = (i==5 ? 0 : 5))
{
if(node5->next == 0)
{
return last[i];
}
last[i] = &node5->val;
node5 = node5->next;
}

[Siemel Naran]

Re: Linked List

"Pete" <x@x.x> wrote in message news:yF2cc.1528 4[color=blue]
> Siemel Naran wrote:[/color]
[color=blue]
> node* node = yourfirstnode;
> node* node5 = node->next->next->next->next;
>
> for(;;)
> {
> if(node5->next == 0)
> {
> return node->val;
> }
> node = node->next;
> node5 = node5->next;
> }[/color]
[color=blue][color=green]
> > Is it really faster than the 2 pass method? In the 2 pass method,
> > first visit all N elements for a total of N calls to
> > const_iterator: :operator++. Then you perform N-5 more calls to
> > operator++. But in the 1 pass method, you perform N calls to
> > const_iterator: :operator++ on node, and N-5 on node5. So don't they
> > both have the same running time?[/color][/color]

Seems the 2 pass method you maintain an index for looping from [0, N-5) but
in the 1 pass method you don't. So based on that the 1 pass method might be
faster, though the improvement is probably negligible.

[color=blue]
> BTW, this exercise is a good example of a good reason to use a doubly[/color]
linked[color=blue]
> list, because it's easy to go either forwards or back depending on the
> situation. The extra memory used for the extra pointer per node really[/color]
isn't[color=blue]
> an issue, usually.[/color]

If going back is not a common operation, the single list could be better.
Anyway, the point of these 'clever' interview questions is not always to
mimic reality, but to see how you think through problems, especially the
logic questions.

Anyway, I think if you just store the value of the pointer in one pass, you
could get better


node* node = yourfirstnode;
node* node5 = node->next->next->next->next;

T * last[5] = { &node->val, &node->next->val, ... };

for(int i=0; ; i = (i==5 ? 0 : 5))
{
if(node5->next == 0)
{
return last[i];
}
last[i] = &node5->val;
node5 = node5->next;
}

[Niels Dybdahl]

Re: Linked List

> Is it really faster than the 2 pass method?

If the time for retrieval of one element is high, then a one pass approach
is faster than a two pass.
However the method of using two pointers are actually a two pass algorithm
in that case (each element is loaded/passed twice).
A one pass algorithm, that would save time, would cache the elements once
loaded and maintain a local 5 element list.

Niels Dybdahl