linked list

[alexxx.magni]

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

 

[Peter J. Holzer]

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

 

[alexxx.magni]

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

 

[Jürgen Exner]

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