http://www.perlmonks.org?node_id=996187

Shaveta_Chawla has asked for the wisdom of the Perl Monks concerning the following question:

A linked list can be created in perl like this::
my ($head, $tail); $tail = append($head, 1); for $value ( 2 .. 10 ) { $tail = append($tail, $value); } sub append { my($list, $value) = @_; my $node = { VALUE => $value }; if ($list) { $node->{LINK} = $list->{LINK}; $list->{LINK} = $node; } else { $_[0] = $node; } return $node; }
but if i want to insert a new node say 11 after a specific position say after 6, how can i do that??? Or is there any better way to create a Linked List in perl??

Replies are listed 'Best First'.
Re: Linked list in Perl
by Arunbear (Prior) on Sep 28, 2012 at 12:25 UTC
    Just use an array, and splice to add the new element e.g. to add something after position 5:
    +% perl -de0 Loading DB routines from perl5db.pl version 1.32 Editor support available. Enter h or `h h' for help, or `man perldebug' for more help. main::(-e:1): 0 DB<1> @ar = 'a' .. 'h' DB<2> x \@ar 0 ARRAY(0x288c320) 0 'a' 1 'b' 2 'c' 3 'd' 4 'e' 5 'f' 6 'g' 7 'h' DB<3> @slice = @ar[6 .. -1] DB<4> splice @ar, 6, @slice, 11, @slice DB<5> x \@ar 0 ARRAY(0x288c320) 0 'a' 1 'b' 2 'c' 3 'd' 4 'e' 5 'f' 6 11 7 'g' 8 'h' DB<6>

    Also see How do I handle linked lists?

      To insert , use length zero

      perl -deep oading DB routines from perl5db.pl version 1.33 ditor support available. nter h or `h h' for help, or `perldoc perldebug' for more help. ain::(-e:1): ep DB<1> @f=a..f; DB<2> x\@f ARRAY(0xe2b154) 0 'a' 1 'b' 2 'c' 3 'd' 4 'e' 5 'f' DB<3> splice @f, 3,0, P; DB<4> x\@f ARRAY(0xe2b154) 0 'a' 1 'b' 2 'c' 3 'P' 4 'd' 5 'e' 6 'f' DB<5> q
Re: Linked list in Perl
by grizzley (Chaplain) on Sep 28, 2012 at 12:21 UTC
    Linked list is best if you need to add at the end and pick from beginning. If you want to insert/remove elements in the middle you have to travel from the beginning and if you are at desired element C (after which you want to insert new element N) just copy link to next element from C to N, set link to next element in C to N and you are done. So you want to change

    C -> nextElem

    to

    C -> N -> nextElem

Re: Linked list in Perl
by Anonymous Monk on Sep 28, 2012 at 12:05 UTC
Re: Linked list in Perl
by Anonymous Monk on Sep 28, 2012 at 12:19 UTC
Re: Linked list in Perl
by GrandFather (Saint) on Sep 30, 2012 at 21:45 UTC

    In Perl I create linked lists like:

    my @list;

    I can then append at the front with unshift or the back with push. I can remove from the front with shift and from the back with pop. I can insert at any index position with splice using splice @list, $iPoint, 0, $item and remove an item anywhere from the list with my ($delItem) = <c>splice @list, $dPoint, 1. Actually I can add multiple items in a single operation using any of push, unshift or splice by using a list instead of a single item and I can use splice to remove multiple contiguous items anywhere from the list.

    Was there something you want to do with a linked list that isn't included in the box with Perl?

    True laziness is hard work
Re: Linked list in Perl
by sundialsvc4 (Abbot) on Sep 28, 2012 at 17:12 UTC

    A linked-list is a specific implementation of “a list,” but Perl already has well-defined List and Array data-types.   You don’t need to bother to create your own ... unless you are dealing with a very unusual edge-case, for which there will undoubtedly be an application-specific module to be found at http://search.cpan.org.

    If you find yourself “dumpster diving” to details at that level, it almost invariably means that you are on the wrong track.   (Heck, that’s also true with C++, which has plenty of “extensible container” classes available off-the-shelf.)   It means that you are getting lost in one path of “how can I do this” and losing sight of “what am I trying to achieve?”   (A very easy thing to do!)

      What kind of 'well-defined' list data types are you referring to? Can you give an example of how to use them?

      On cpan, what modules would you suggest using to solve the given problem?

      I find the lacking of concrete information in your post disturbing ...
Re: Linked list in Perl
by LanX (Saint) on Sep 29, 2012 at 23:26 UTC
    > Or is there any better way to create a Linked List in perl??

    Arrays of length 2 consume far less memory. See for instance "Higher Order Perl" or many examples here in the archives.

    like here Re: How to implement Linked List

    If you're desperate, you could even try increase compactness by using dualvars assigning references to the number slot and values to the string slot. see Scalar::Util (don't know if it's practical =)

    Cheers Rolf