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

Re: A Link List Question

Thread Previous | Thread Next
From:
John Peacock
Date:
July 26, 2001 13:31
Subject:
Re: A Link List Question
Message ID:
3B607B49.BBB37EE7@rowman.com
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.
> 

I think you actually want a here is a doubly-linked list.

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

That way the $Tail node can point back to previous node and then the
$Tail itself can be deleted and the new $Tail assigned.  This makes
appending to the $Tail cheap (as well as inserts in the middle).  
Deleting any node from the $Head down is as cheap as a singly-linked
list.

I don't know of any way to get Perl to give you that information.
As far as I know, the only other way is to walk the entire list.

HTH

John

--
John Peacock
Director of Information Research and Technology
Rowman & Littlefield Publishing Group
4720 Boston Way
Lanham, MD 20706
301-459-3366 x.5010
fax 301-429-5747

Thread Previous | Thread Next


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