develooper Front page | perl.perl5.porters | Postings from July 2001

A Link List Question

Thread Next
Medi Montaseri
July 26, 2001 13:01
A Link List Question
Message ID:

I've got a linked list questiion for your amusement....

Give a Singly Linked List consisting of N nodes, where a node is
defined as

%Node = ( Element-1 => 'some value',
                  Element-2 => 'other value',
                 etc, etc
                 Next => undef );

And given $Head and $Tail

Propose an algorithm (in English is good enough) that deletes a node
from the end.

The following solutions have been visisted, so don't bother....

1- Traverse the list to the end, keeping $Previous or $OneBeforeTheLast
and do the surgery there.

2- Instead of $Tail, keep $OneBeforeTheLast, making it easier for
removal from
the end, but costly for appending to the end.

And here is what I'm after (or thinking of) now...

We know that $Tail points to the last Node. We also know that the
OneBeofreLast node
has a scalar pointing to the last node. We also know that Perl keeps
reference counts.
So if I ask the interpreter how many references do you have for the last
node, Perl
would say two.

Now, can we use this information, ie given an object with two reference
counts, can I ask
the interpreter to report who are pointing to this object. Obviously one
is $Tail.


Medi Montaseri,, 408-450-7114
Prepass Inc, IT/Operations, Software Eng.

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About