FAQ 4.46 How do I handle linked lists?

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

This is an excerpt from the latest version perlfaq4.pod, which
comes with the standard Perl distribution. These postings aim to
reduce the number of repeated questions as well as allow the community
to review and update the answers. The latest version of the complete
perlfaq is at http://faq.perl.org .


4.46: How do I handle linked lists?

    In general, you usually don't need a linked list in Perl, since with
    regular arrays, you can push and pop or shift and unshift at either end,
    or you can use splice to add and/or remove arbitrary number of elements
    at arbitrary points. Both pop and shift are O(1) operations on Perl's
    dynamic arrays. In the absence of shifts and pops, push in general needs
    to reallocate on the order every log(N) times, and unshift will need to
    copy pointers each time.

    If you really, really wanted, you could use structures as described in
    perldsc or perltoot and do just what the algorithm book tells you to do.
    For example, imagine a list node like this:

            $node = {
                    VALUE => 42,
                    LINK  => undef,

    You could walk the list this way:

            print "List: ";
            for ($node = $head;  $node; $node = $node->) {
                    print $node->, " ";
            print "\n";

    You could add to the list this way:

            my ($head, $tail);
            $tail = append($head, 1);       # grow a new head
            for $value ( 2 .. 10 ) {
                    $tail = append($tail, $value);

            sub append {
                    my($list, $value) = @_;
                    my $node = { VALUE => $value };
                    if ($list) {
                            $node-> = $list->;
                            $list-> = $node;
                    else {
                            $_[0] = $node;      # replace caller's version
                    return $node;

    But again, Perl's built-in are virtually always good enough.


The perlfaq-workers, a group of volunteers, maintain the perlfaq. They
are not necessarily experts in every domain where Perl might show up,
so please include as much information as possible and relevant in any
corrections. The perlfaq-workers also don't have access to every
operating system or platform, so please include relevant details for
corrections to examples that do not work on particular platforms.
Working code is greatly appreciated.

If you'd like to help maintain the perlfaq, see the details in

Site Timeline