Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

How to implement Linked List

by msk_0984 (Friar)
on Dec 18, 2006 at 11:53 UTC ( #590415=perlquestion: print w/ replies, xml ) Need Help??
msk_0984 has asked for the wisdom of the Perl Monks concerning the following question:

Hi Respected Monks,

          I am really happy that i have learnt a lot from the day one i have joined into this great family of Perl Monks. And i was able to resolve my doubts and issues with the help of most effective and effienct well experienced Monks.


          As of now i would like to know a technique to implement Linked Lists in Perl. Actually i have got the Idea of Hashes but i felt that there could also be a better approach for this one .... i thought some thing like

%words = ("abel", "baker", "baker", "charlie", "charlie", "delta", "delta", "");
And also any other techniques would be helpful .........
Work Hard Party Harderrr!!
Sushil Kumar

Comment on How to implement Linked List
Download Code
Re: How to implement Linked List
by rinceWind (Monsignor) on Dec 18, 2006 at 12:07 UTC

    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);

    --

    Oh Lord, won’t you burn me a Knoppix CD ?
    My friends all rate Windows, I must disagree.
    Your powers of persuasion will set them all free,
    So oh Lord, won’t you burn me a Knoppix CD ?
    (Missquoting Janis Joplin)

      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
        Tom Melly, pm@tomandlu.co.uk
      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.

Re: How to implement Linked List
by SFLEX (Chaplain) on Dec 18, 2006 at 12:08 UTC
    If you mean HTML links you could take a look at these posts Turning a hash into a line of links

    if that is not what you meant please show me more so i can get a better idea of the problem.

    Good Luck!

    Updated: I was very off on this topic. You can disregard this post and yes Im a web page programmer. :p
      No, I think the OP knows what he's asking: Linked list


      holli, /regexed monk/
Re: How to implement Linked List
by Hofmator (Curate) on Dec 18, 2006 at 12:42 UTC
    I must agree with rinceWind, I don't see the need for linked lists in your example.

    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]; } }

    -- Hofmator

    Code written by Hofmator and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.

Re: How to implement Linked List
by shmem (Canon) on Dec 18, 2006 at 13:00 UTC

    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}
Re: How to implement Linked List
by jonadab (Parson) on Dec 18, 2006 at 15:18 UTC

    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?"


    Sanity? Oh, yeah, I've got all kinds of sanity. In fact, I've developed whole new kinds of sanity. You can just call me "Mister Sanity". Why, I've got so much sanity it's driving me crazy.
Re: How to implement Linked List
by davido (Archbishop) on Dec 18, 2006 at 19:32 UTC

    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 }, }, };

    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 ], ], ];

    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.


    Dave

Re: How to implement Linked List
by GrandFather (Cardinal) on Dec 18, 2006 at 19:50 UTC

    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.


    DWIM is Perl's answer to Gödel
Re: How to implement Linked List
by gam3 (Curate) on Dec 19, 2006 at 04:07 UTC
    A simple linked list would be [ 'a' [ 'b' [ 'c', undef]]]. This is more clear if you look at it like this:
    $c = ['c', undef]; $b = ['b', undef]; $a = ['a', undef]; $a->[1] = $b; $b->[1] = $c;
    This is the same as the hash version above, but using arrays. You would travers this list like this:
    my $current = $a; while (defined $current) { my $value = $current->[0]; ... $current = $current->{1]; }
    This is no different than the hash version above, but should be a bit more efficient.

    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.

    -- gam3
    A picture is worth a thousand words, but takes 200K.
      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
Re: How to implement Linked List
by Moron (Curate) on Dec 19, 2006 at 16:21 UTC
    The main raison d'etre of a linked list is that in compiled languages (but not in Perl) arrays are not supported by element deletion or insertion. But I said 'main' rather than 'only'. It is perfectly reasonable that a class might call for a peer to peer relationship and that just happens to be identical in implementation to a linked list. So without further ado, and covering my eyes to anything too complex that has been suggested (sorry no time before Christmas!) that becomes my recommendation, to whit, create a SIMPLE object solution something like:
    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 );
    Perl should automatically delete objects that have been unlinked from the list, although I am in the habit of making sure by applying a "delete" + object reference before bypassing a node into oblivion (in the example that could be done just by linking both neighbours of the victim node to each other).

    -M

    Free your mind

Re: How to implement Linked List
by Anonymous Monk on Dec 19, 2006 at 22:09 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://590415]
Approved by Corion
Front-paged by Old_Gray_Bear
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (9)
As of 2014-08-23 18:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (178 votes), past polls