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

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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://590530]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2017-01-22 23:08 GMT
Find Nodes?
    Voting Booth?
    Do you watch meteor showers?

    Results (190 votes). Check out past polls.