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

Re: A Link List Question

Thread Previous
From:
Nick Ing-Simmons
Date:
July 27, 2001 01:16
Subject:
Re: A Link List Question
Message ID:
20010727081636.723.2@bactrian.ni-s.u-net.com
John Peacock <jpeacock@rowman.com> 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
http://www.ni-s.u-net.com/


Thread Previous


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About