I was perusing perlfaq4 during my lunch break today and came across the topic "How do I handle linked lists?" The first sentence of the answer reads in part as follows: "In general, you usually don't need a linked list in Perl..." I did a double take and a silent "Hoo-aahh!"

I have rather nasty memories of trying to follow material on linked lists in certain algorithm texts years ago, so realizing that a programming language (i.e. Perl) can be widely accepted without linked lists as a feature was gratifying and enlightening.

Another quote from the faq: "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...but again, Perl's built-in are virtually always good enough." To me, this is another feature that pushes Perl to the top of my list when considering languages to use for coding projects.

Have any monks implemented linked-list structures in their Perl code, and if so did your performance improvements outweigh the additional complexity of the code?

Update: The node Shift, Pop, Unshift and Push with Impunity! showed up in the Selected Best Nodes and based on my reading of it makes me comfortable that Perl is very efficient at taking care of the kind of work that linked-list code might otherwise be needed to do such as demerphq describes in his reply in this thread.

Replies are listed 'Best First'.
Re: Linked Lists and Perl
by Fletch (Bishop) on Sep 28, 2006 at 13:57 UTC
[reply]
Re: Linked Lists and Perl
by jdporter (Paladin) on Sep 28, 2006 at 14:14 UTC

    One candidate from CPAN is Tree::DAG_Node. It supports 0..n child nodes, but you could easily restrict your usage of it to 0..1 child nodes.

    We're building the house of the future together.
[reply]
Re: Linked Lists and Perl
by Velaki (Chaplain) on Sep 28, 2006 at 14:09 UTC

    I wondered about it too, and then I realized that one could implement Scheme in Perl, which means one could even implement Prolog in Perl.

    Sometimes list processing concepts (LISP and its kin) are the way to go, especially when needing to model complex graphs. And in any case, using an AoA or AoH, or any of the other variants tends to exploit a kind of linked list already.

    If you want to go one step further, you can implement a true CONS cell using Perl.

    Just my thoughts,
    -v

    "Perl. There is no substitute."
[reply]
      Good point! In fact, it's been done. ;-)
[reply]

      Prolog in perl? Sure! AI::Prolog.

      ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

[reply]
Re: Linked Lists and Perl
by demerphq (Chancellor) on Sep 29, 2006 at 07:31 UTC

    Linked lists are often used where you want to add and remove elements from a structure on a regular basis and do not want to deal various performance and management issues that would come from using a structure like a C level array. Perls array implementation handles all that crap itself so theres generally not a lot of point.

    Having said that if you want a fast ring buffer with constant time insertion into a specific point then linked lists are hard to beat.

    ---
    $world=~s/war/peace/g

[reply]
Re: Linked Lists and Perl
by blackhat.blade (Initiate) on Oct 05, 2006 at 15:30 UTC
    everytime i implemented some kind of linked list (single, double or circular), i ended up with code that is actually slower than using Arrays or hashes (yeah even hashes were faster). IMHO the bottleneck is that such customly build data structures like linked lists require too much OPs to be more effcient than perls own data structures. the only real reason to use linked lists, is that they fit best structure of your data.
[reply]

Back to Meditations