linked list

Discussion in 'Perl Misc' started by alexxx.magni@gmail.com, Apr 29, 2009.

  1. Guest

    please forgive me if this is a dumb question, but I'm unable to code a
    linked list in perl - to be precise I'm able to create it but I'm
    unable to delete nodes...

    the linked list contains 2 coordinates 'x','y' for each node:

    my $pixies=undef;

    for(1..10)
    { $pixies= [ $pixies, {'x'=>int(3*rand()), 'y'=>int(10*rand())} ] }

    my $head=$pixies;

    for $i(1..10)
    {
    print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    $pixies=$pixies->[0];
    }

    # trying to delete the 8th node:
    for $i(1..7)
    { $pixies=$pixies->[0] }

    # now!
    $pixies->[0]=$pixies->[0][0];

    print"\n\n\tdeleted 8...\n\n\n";

    # check:
    $pixies=$head;

    for $i(1..10)
    {
    print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    $pixies=$pixies->[0];
    }

    and I got the same nodes again!!! What am I doing wrong?

    Thanks a lot for any help on this...

    P.S.: I read often that linked lists implemented this way are not the
    way to go in perl, that you can do the same things with arrays (arrays
    of hashes, in my case).
    Do you agree? And in that case, how would you delete a node in the
    middle of the array without too much copying around of large
    structures?

    thanks again

    alessandro
     
    , Apr 29, 2009
    #1
    1. Advertising

  2. On 2009-04-29 06:45, <> wrote:
    > please forgive me if this is a dumb question, but I'm unable to code a
    > linked list in perl - to be precise I'm able to create it but I'm
    > unable to delete nodes...
    >
    > the linked list contains 2 coordinates 'x','y' for each node:
    >
    > my $pixies=undef;
    >
    > for(1..10)
    > { $pixies= [ $pixies, {'x'=>int(3*rand()), 'y'=>int(10*rand())} ] }
    >
    > my $head=$pixies;
    >
    > for $i(1..10)
    > {
    > print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    > $pixies=$pixies->[0];
    > }


    Here you just walked beyond the tenth (= last) node of your list.
    So, $pixies is undef here.

    >
    > # trying to delete the 8th node:
    > for $i(1..7)
    > { $pixies=$pixies->[0] }


    And here you try to walk 7 more steps.
    $pixies stays undef (sometimes autovivification is a bitch - there
    should be a way to get a warning in this case).

    >
    > # now!
    > $pixies->[0]=$pixies->[0][0];


    So here you don't delete the 8th node, you just create a new array,
    assign undef to it's element 0, and ...
    >
    > print"\n\n\tdeleted 8...\n\n\n";


    >
    > # check:
    > $pixies=$head;


    immediately overwrite it.

    >
    > for $i(1..10)
    > {
    > print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    > $pixies=$pixies->[0];
    > }
    >
    > and I got the same nodes again!!! What am I doing wrong?


    You forgot

    $pixies=$head;

    before

    # trying to delete the 8th node:

    (You also forgot "use warnings; use strict;", but in that case it
    wouldn't have helped).


    > Thanks a lot for any help on this...
    >
    > P.S.: I read often that linked lists implemented this way are not the
    > way to go in perl, that you can do the same things with arrays (arrays
    > of hashes, in my case).
    > Do you agree?


    Yes.

    > And in that case, how would you delete a node in the
    > middle of the array without too much copying around of large
    > structures?


    Perl arrays really contain only pointers to the elements. So if you
    delete 1 element from the middle of a 1-million-element array, you only
    have to move 500000 pointers (about 2 MB on a 32 bit system), not
    500000 perl scalars. That's pretty fast, especially if you compare it
    to the time needed to walk through 500000 nodes.

    There may be some situations where a simple singly-linked list is better
    than a perl array, but I am sure they are rare. More complicated data
    structures (especially various kinds of trees) are useful more often.

    hp
     
    Peter J. Holzer, Apr 29, 2009
    #2
    1. Advertising

  3. Guest

    On 29 Apr, 11:57, "Peter J. Holzer" <> wrote:
    > On 2009-04-29 06:45, <> wrote:
    >
    >
    >
    > > please forgive me if this is a dumb question, but I'm unable to code a
    > > linked list in perl - to be precise I'm able to create it but I'm
    > > unable to delete nodes...

    >
    > > the linked list contains 2 coordinates 'x','y' for each node:

    >
    > > my $pixies=undef;

    >
    > > for(1..10)
    > > { $pixies= [ $pixies, {'x'=>int(3*rand()), 'y'=>int(10*rand())} ]}

    >
    > > my $head=$pixies;

    >
    > > for $i(1..10)
    > > {
    > >     print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    > >     $pixies=$pixies->[0];
    > > }

    >
    > Here you just walked beyond the tenth (= last) node of your list.
    > So, $pixies is undef here.
    >
    >
    >
    > > # trying to delete the 8th node:
    > > for $i(1..7)
    > > {   $pixies=$pixies->[0] }

    >
    > And here you try to walk 7 more steps.
    > $pixies stays undef (sometimes autovivification is a bitch - there
    > should be a way to get a warning in this case).
    >
    >
    >
    > > # now!
    > >    $pixies->[0]=$pixies->[0][0];

    >
    > So here you don't delete the 8th node, you just create a new array,
    > assign undef to it's element 0, and ...
    >
    >
    >
    > > print"\n\n\tdeleted 8...\n\n\n";

    >
    > > # check:
    > > $pixies=$head;

    >
    > immediately overwrite it.
    >
    >
    >
    > > for $i(1..10)
    > > {
    > >     print("$i\t",$pixies->[1]{'x'},"\t",$pixies->[1]{'y'},"\n");
    > >     $pixies=$pixies->[0];
    > > }

    >
    > > and I got the same nodes again!!! What am I doing wrong?

    >
    > You forgot
    >
    >     $pixies=$head;
    >
    > before
    >
    >     # trying to delete the 8th node:
    >
    > (You also forgot "use warnings; use strict;", but in that case it
    > wouldn't have helped).
    >
    > > Thanks a lot for any help on this...

    >
    > > P.S.: I read often that linked lists implemented this way are  not the
    > > way to go in perl, that you can do the same things with arrays (arrays
    > > of hashes, in my case).
    > > Do you agree?

    >
    > Yes.
    >
    > > And in that case, how would you delete a node in the
    > > middle of the array without too much copying around of large
    > > structures?

    >
    > Perl arrays really contain only pointers to the elements. So if you
    > delete 1 element from the middle of a 1-million-element array, you only
    > have to move 500000 pointers (about 2 MB on a 32 bit system), not
    > 500000 perl scalars. That's pretty fast, especially if you compare it
    > to the time needed to walk through 500000 nodes.
    >
    > There may be some situations where a simple singly-linked list is better
    > than a perl array, but I am sure they are rare. More complicated data
    > structures (especially various kinds of trees) are useful more often.
    >
    >         hp


    many many thanks

    alessandro
     
    , Apr 29, 2009
    #3
  4. "" <> wrote:
    >P.S.: I read often that linked lists implemented this way are not the
    >way to go in perl, that you can do the same things with arrays (arrays
    >of hashes, in my case).


    That's correct. In Perl you typically use references only to create
    complex data structures. Simple lists are not complex.

    >Do you agree? And in that case, how would you delete a node in the
    >middle of the array without too much copying around of large
    >structures?


    perldoc -f splice

    splice(@myarray, 7, 1);

    jue
     
    Jürgen Exner, Apr 29, 2009
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris Ritchey
    Replies:
    7
    Views:
    484
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    472
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    513
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    674
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    762
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page