Re: How to implement Linked List

[davido]

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.