Perl has built in fully dynamic data structures - arrays and hashes. These are in most cases sufficient for resident data needs. Can you explain why you need a linked list - is this a practical application or an academic exercise?

Here's something cobbled together - a class that will give you linked list:

package Data::LinkedList;

sub new {
    my $pkg = shift;
    my %proto = @_;

    bless \%proto, $pkg;
}

sub data {
    my $self = shift;

    @_ ? ($self->{data} = shift) : $self->{data};
}

sub next {
    my $self = shift;

    @_ ? ($self->{next} = shift) : $self->{next};
}

1;

__END__

my $ele1 = Data::LinkedList->new( data => 'abel' );
my $ele2 = Data::LinkedList->new( data => 'baker', next => $ele1);
[download]

And making it a doubly linked list is only slightly harder. However making a doubly linked list which does not leak memory is far, far harder.

Here is an example off of my scratchpad that does this. After examining it (and trying it if you want to see abysmal performance) I think that the point will be adequately made that linked lists are possible in Perl, but you really want to use arrays instead.

Read more... (3 kB)

Hi

    Felt good to see your prompt reply. Actually i was exploring Perl and thought of implementing the Linked list concept which might be Useful in for me in Future purposes........ So thought of trying it out

Work Hard Party Harderrr!!
Sushil Kumar

As others have said, linked lists are never really necessary in Perl.

See How do I handle linked lists? for an explanation (as well as a way to implement them).

map{$a=1-$_/10;map{$d=$a;$e=$b=$_/20-2;map{($d,$e)=(2*$d*$e+$a,$e**2
-$d**2+$b);$c=$d**2+$e**2>4?$d=8:_}1..50;print$c}0..59;print$/}0..20
[download]

Tom Melly, pm@tomandlu.co.uk

For further reference, chapter 3 of Mastering Algorithms with Perl explains how to implement linked lists in Perl. The following code is an example out of the book:

#!/usr/bin/perl

$list = $tail = undef;

foreach (1..5) {
    my $node = [ undef, $_ * $_ ];
    $list = undef;
    $tail = \$list;
    foreach (1..5) {
    my $node = [ undef, $_ * $_ ];
    $$tail = $node;
    $tail = \$node->[NEXT];
    }
}
[download]

Super Search is your friend.

It comes up with e.g. linked lists as arrays searching for "linked list".

--shmem

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

Most of the things linked lists are used for, you can just use a Perl array. If you ever really do need a linked list, you can create one just as easily as in any other language. (If you're familiar with the usual C implementation, just use anonymous hashes instead of structs and Bob is your uncle. Or if you prefer you could use anonymous arrays instead of structs.) But I suspect you could spend thirty years programming in Perl and never *need* a linked list, because Perl's built-in data structures are so much better than the ones in the kind of low-level language (like C) where things like linked lists are a big deal.

It's kinda like asking, "How do I implement an insertion sort in Perl?" or, to use a non-Perl example, "How do I tack in a speedboat?" Everyone's going to look at you funny and ask, "Why?"

A common technique is to use a hashref, pointing to an anonymous hash (the top node). That hash will have two or more key/value pairs. One of the keys will be "next", and its value will refer to the next anonymous hash in the linked list. In the end, you get a datastructure that looks like this:

$href = {
    value => "some data",
    next  => {
        value => "more data",
        next => {
            value => "still more",
            next => undef
        },
    },
};
[download]

Essentially you have little anonymous hashes that each have one key pointing to the next anonymous hash in the linked list. But you don't have to use a hash. You could also use anonymous arrays like this:

$aref = [
    "some data",
    [
        "more data",
        [
            "still more",
            undef
        ],
    ],
];
[download]

Here, $aref->[0] contains data, and $aref->[1] contains the pointer to the next anonymous array. To me it's a little more confusing because my mind prefers the labels like "next". I find $href->{next}{next}{value} easier to follow than $aref->[1][1][0], but there is a very slight performance improvement using the array instead of the hash. Probably not enough difference to worry about though unless you're really in a tight loop or something.

The best resource I've found for understanding the implementation of linked lists in Perl is Mastering Algorithms with Perl, published by O'Reilly & Associates. Of course you'll also find perlref, perllol, and perldsc helpful.

Perl already has linked lists in effect, they are (as others have suggested) called arrays. The key to unlocking Perl arrays as linked lists is to know about splice. Perl arrays are not constant time node insertion and deletion, but are likely to be fast enough for most purposes and splice is easier to read than a bunch of code fooling around with the 'pointers' a linked list requires.

$c = ['c', undef];
$b = ['b', undef];
$a = ['a', undef];

$a->[1] = $b;
$b->[1] = $c;
[download]

my $current = $a;

while (defined $current) {
    my $value = $current->[0];
    ...
    $current = $current->{1];
}
[download]

The main point is that a linked list is made up of elements that contain data and a pointer to the next element. In the case of a double linked list 2 pointers -- one to the previous element and one to the next element.

Hi Monks,


        Firstly i would like to thank you for ur replies and it was really a good thing to get the ideas and views of well experienced people.

        Most said Perl has built in fully dynamic data structures - arrays and hashes. These are in most cases sufficient for resident data needs. We have the extended featured functions for th ease in order to exploit the programming abilities....


FUNCTIONS: pop , push , splice , shift , unshift and many more and dont want to use etc.....

As jonadab said ...........

It's kinda like asking, "How do I implement an insertion sort in Perl?" or, to use a non-Perl example, "How do I tack in a speedboat?" Everyone's going to look at you funny and ask, "Why?"

But any wayz i felt it some thing like of learning a lot from all of you.

Work Hard Party Harderrr!!
Sushil Kumar

package P2Pr;
sub new {
    shift();
    my $ref = bless {};
    $ref -> link( @_ ) if ( @_ ); # support one-stop calls
    return $ref;
}
sub link {
    my ( $obj, $relation, $other ) = @_;
    $obj -> { $relation } = $other;
}

# ... 
1;

# common or garden example ...

use P2Pr;
my $carriage1 = P2Pr -> new();
my $train = P2Pr -> new( 'afore', $carriage1 );
$carriage1 -> link ( 'abaft', $train );
my $carriage2 = new( 'abaft', $carriage1 );
$carriage1 -> link( 'afore', $carriage2 );
[download]

No, I think the OP knows what he's asking: Linked list


holli, /regexed monk/