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 both 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: