in reply to implementing linklist structure in perl

kan:

As Polonius, GrandFather and Joost mentioned, you normally don't need a linked list in Perl. Using an array, you can do all the same operations. The simple ones:

Add/remove list head: unshift/shift

Add/remove list tail: push/pop

As well as the slightly trickier ones. For a traditional linked list, you'll have a pointer to a node and for the array you'll just have an index into the list. So you can still remove the item you're pointing to:

@list = (@list[0..($ptr-1)], @list[($ptr+1)..$#list]);

[download]
or insert after the pointer:

@list = (@list[0..$ptr], $item_to_insert, @list[($ptr+1)..$#list]);

[download]
Notes:

  • I've not done array splicing for a while, so I might have the syntax a bit off....
  • Range-checking of the pointer before your operations would be a good idea in realcode.

    • So you don't usually need a linked list in Perl (except, of course, for homework assignments).

    ...roboticus

    Replies are listed 'Best First'.
    Re^2: implementing linklist structure in perl
    by jasonk (Parson) on May 09, 2007 at 15:46 UTC

      They aren't so tricky if you read perlfunc...

      
# remove the item you are pointing to
splice( @list, $i, 1 );

# insert after the pointer
splice( @list, $i+1, 0, $item_to_insert );

      [download]

      I suspect this is also going to be a lot faster than rebuilding the whole array.

      We're not surrounded, we're in a target-rich environment!
    		[reply]
    [d/l]
        jasonk:

        ++ Thanks for the tip...that's another function I'll have to add to my arsenal. I refer to perlfunc frequently, but I just can't bring myself to read it from beginning to end to see what's in it. (The plot just isn't very interesting!)

        ...roboticus

    		[reply]

    In Section Seekers of Perl Wisdom