Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: How to implement Linked List

by davido (Archbishop)
on Dec 18, 2006 at 19:32 UTC ( #590530=note: print w/ replies, xml ) Need Help??


in reply to How to implement Linked List

A common technique is to use a hashref, pointing to an anonymous hash (the top node). That hash will have two or more key/value pairs. One of the keys will be "next", and its value will refer to the next anonymous hash in the linked list. In the end, you get a datastructure that looks like this:

$href = { value => "some data", next => { value => "more data", next => { value => "still more", next => undef }, }, };

Essentially you have little anonymous hashes that each have one key pointing to the next anonymous hash in the linked list. But you don't have to use a hash. You could also use anonymous arrays like this:

$aref = [ "some data", [ "more data", [ "still more", undef ], ], ];

Here, $aref->[0] contains data, and $aref->[1] contains the pointer to the next anonymous array. To me it's a little more confusing because my mind prefers the labels like "next". I find $href->{next}{next}{value} easier to follow than $aref->[1][1][0], but there is a very slight performance improvement using the array instead of the hash. Probably not enough difference to worry about though unless you're really in a tight loop or something.

The best resource I've found for understanding the implementation of linked lists in Perl is Mastering Algorithms with Perl, published by O'Reilly & Associates. Of course you'll also find perlref, perllol, and perldsc helpful.


Dave


Comment on Re: How to implement Linked List
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://590530]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (14)
As of 2015-07-02 18:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (44 votes), past polls