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

Re: A Link List Question

Thread Previous
Nick Ing-Simmons
July 27, 2001 01:16
Re: A Link List Question
Message ID:
John Peacock <> writes:
>Medi Montaseri wrote:
>> Hi,
>> 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.

p5p isn't really the place to discuss basic programming algorithms.
But ...

There is a variant on the one-before-last scheme - keep a reference
to the place you got this value from:

my $link = \$head;
while (my $node = $$link)
  $link = \($node->{Next});
$$link = undef;

The other scheme I use is to keep a circular list, and keep the value of $tail
as "the" global variable that "points" to the representation.

That way head is $tail->{Next} (just one hop away) so you can get 
at both ends of the list quickly.

>I don't know of any way to get Perl to give you that information.

Quite - perl knows how _many_ places point to a node but not where they 
are - it has reference counts not reference lists.

Nick Ing-Simmons

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