Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > linked list

Reply
Thread Tools

linked list

 
 
alexxx.magni@gmail.com
Guest
Posts: n/a
 
      04-29-2009
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
 
Reply With Quote
 
 
 
 
Peter J. Holzer
Guest
Posts: n/a
 
      04-29-2009
On 2009-04-29 06:45, http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
alexxx.magni@gmail.com
Guest
Posts: n/a
 
      04-29-2009
On 29 Apr, 11:57, "Peter J. Holzer" <(E-Mail Removed)> wrote:
> On 2009-04-29 06:45, (E-Mail Removed) <(E-Mail Removed)> 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
 
Reply With Quote
 
Jürgen Exner
Guest
Posts: n/a
 
      04-29-2009
"(E-Mail Removed)" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Airplane Program with Linked Lists. The linked list portion is veryconfusing to me. jawdoc C++ 9 03-10-2008 03:38 AM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Generating a char* from a linked list of linked lists Chris Ritchey C++ 7 07-10-2003 10:12 PM
Generating a char* from a linked list of linked lists Chris Ritchey C Programming 7 07-10-2003 10:12 PM



Advertisments