Creating a linked list structure in Perl

Question

In C you can create your own structure, and from there create a linked list where a record in the structure would point to the next record as well as the previous one.

Surely Perl must have a way to do this? Would love to know how.

Thanks

Answer 1

You can do this basically the same way you'd do it in C, but use references instead of pointers and hashes instead of structs.

But in Perl usually you don't have to because Perl's built in arrays are pretty smart and fast. They grow automatically and already do most of what a linked list can do like adding and removing arbitrary elements with splice, and adding and removing from the front and back of the array with pop, push, shift, and unshift. And, unlike a linked list, you get O(1) random access. See perlfunc for more.

You also don't do this because writing your own data structures in Perl tend to be pretty slow. Perl arrays are written in C, but your linked list will be written in much slower Perl and consume much more memory. While the algorithm might be more efficient, the implementation will be slow. In Computer Science terms, the constant will be very large. The end result is specialized data structures like linked lists and trees only make sense when you start to get into hundreds of thousands or millions of elements.

Your other option is to use a linked list library written in C. You can take advantage of C libraries using a thing called XS that acts as a bridge between C code and Perl code. But it's not the easiest thing to use.

Answer 2

You don't tend to see Perl programmers creating things like linked lists. You might want to read perllol and perldsc to find out about more typically "Perlish" data structures.

Having said that, you could look at the source of LinkedList::Single to see one way to write a singly-linked list in Perl.