Almost always in Perl you don't need to use linked lists. Perl's arrays combined with shift, unshift, push, pop and splice do pretty much anything you would need a linked list for in other languages.

If you really, really, really need a linked list tell us about the context because I suspect you really, really, really don't. ;)

You'll find lots of answers at How to implement Linked List.

The purpose of a linked list in say C is to overcome C's deficiency in dynamic handling of data storage (similar deficiency exists for e.g. Pascal - only the syntax is different). Although C has the capability of dynamically increasing and decreasing the length of an array of fixed-sized elements (be they structured or not), you can't delete or add to the middle of an array and in effect not at the beginning either. The solution in languages like C is to have a linked list of dynamically allocated storage units. There is however a (bit clunky) implementation of a hash in C++ (called a map) but which is far more limited in its implementation than in Perl - achieving similar functionality as for Perl would not be at all easy in C++ and certainly beyond the capability of the average programmer. The map attempts to simulate an associative array over a fixed storage area with the effect that it can't achieve more than the most trivial of hash implementations. Java uses the C++ model as the basis for its data storage and inherits the same limitations.

Perl, on the other hand, implements its structures more flexibly, allowing seamless dynamic storage and preventing the need for a linked list. In Perl hashes and arrays do not need their elements to be of a fixed length or type and thus instead of a linked list, an array of hash or array will suffice because elements can be added, deleted and amended anywhere in the array (and obviously anywhere in a hash) including changing the type as well as size used by a given element with complete flexibility.

There is one exception however: sometimes, but very rarely, a requirement might functionally suggest the implementation of a linked list. For example, a binary tree might be needed in some actual business functionality (as opposed to reacted technical functionality) such as simulating a particular database algorithm. In that case, you should implement the linked list dynamically as you would in C++ rather than use an array or hash container at all (else you are duplicating the overheads of Perl versus your own implementation!):

# example: building a binary tree from an unsorted file of strings
$_ = <>;
chop;
my $llref;
{ $llref = { data => $_ }; }
while ( <> ) {
    chop;
    Bin( $llref );
}

# on completion there is only $llref defined pointing at a dynamic lis
+t element being an anonymous hash with links to other similar list el
+ements.

sub Bin {
    my $llref = shift;
    if ( $_ < $llref -> { data } ) {
        if ( defined ( $llref -> { left } ) ) {
            Bin( $llref -> { left ));
        }
        else {
            $llref -> { left } = { data => $_ };
        }
    elsif( $_ > $llref -> { data } ) {
        if ( defined( $llref -> { right } ) ) {
            Bin( $llref -> { right ));
        }
        else {
            $llref -> { right } = { data => $_ };
        }
    }
}
[download]

Update: A terniary tree requirement would make the linked list an even stronger technical candidate in Perl, making it much harder to use hashes and arrays as outer structural containers but I can't think of a functional requirement needing a terniary tree.

sometimes, but very rarely, a requirement might functionally suggest...

It's not nearly as rare as you imagine.

Amended - i.e. I'll believe it - It could happen to me any time I suppose.
__________________________________________________________________________________

^M Free your mind!

In any case, as others have posted alreay, you generally don't use linked lists in perl. In any case you can implement them in perl in the same way you can implement them in C or Pascal: $element->{next} = $next_element

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]

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

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

...roboticus

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!

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