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

Re: A Link List Question

Thread Previous | Thread Next
John Peacock
July 26, 2001 13:31
Re: A Link List Question
Message ID:
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

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.



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 Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About