Prev: FAQ 9.4 How do I remove HTML from a string?
Next: LibXML (XPATH) and escape
From: PerlFAQ Server on 24 Jan 2010 06:00
This is an excerpt from the latest version perlfaq4.pod, which
comes with the standard Perl distribution. These postings aim to
reduce the number of repeated questions as well as allow the community
to review and update the answers. The latest version of the complete
perlfaq is at http://faq.perl.org .

--------------------------------------------------------------------

4.46: How do I handle linked lists?

In general, you usually don't need a linked list in Perl, since with
regular arrays, you can push and pop or shift and unshift at either end,
or you can use splice to add and/or remove arbitrary number of elements
at arbitrary points. Both pop and shift are O(1) operations on Perl's
dynamic arrays. In the absence of shifts and pops, push in general needs
to reallocate on the order every log(N) times, and unshift will need to
copy pointers each time.

If you really, really wanted, you could use structures as described in
perldsc or perltoot and do just what the algorithm book tells you to do.
For example, imagine a list node like this:

$node = {
VALUE => 42,
LINK => undef,
};

You could walk the list this way:

print "List: ";
for ($node = $head; $node; $node = $node->{LINK}) {
print $node->{VALUE}, " ";
}
print "\n";

You could add to the list this way:

my ($head, $tail);
$tail = append($head, 1); # grow a new head
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; # replace caller's version
}
return $node;
}

But again, Perl's built-in are virtually always good enough.



--------------------------------------------------------------------

The perlfaq-workers, a group of volunteers, maintain the perlfaq. They
are not necessarily experts in every domain where Perl might show up,
so please include as much information as possible and relevant in any
corrections. The perlfaq-workers also don't have access to every
operating system or platform, so please include relevant details for
corrections to examples that do not work on particular platforms.
Working code is greatly appreciated.

If you'd like to help maintain the perlfaq, see the details in
perlfaq.pod.
From: Richard McBeef on 25 Jan 2010 11:25
PerlFAQ Server wrote:
> This is an excerpt from the latest version perlfaq4.pod, which
> comes with the standard Perl distribution. These postings aim to
> reduce the number of repeated questions as well as allow the community
> to review and update the answers. The latest version of the complete
> perlfaq is at http://faq.perl.org .
>
> --------------------------------------------------------------------
>
> 4.46: How do I handle linked lists?
> [snip]
At YAPC 2009 there was a good talk about some
occasions where a LL is nice to have in Perl.
Here is a link to the slides.
http://github.com/lembark/Talks/blob/21437a3e24f1ea809685a3e0bb162119bd05b84b/perly-linked-lists.pdf
Really good stuff. Probably the best talk at an
otherwise unusually dull YAPC.
From: brian d foy on 25 Jan 2010 13:53
In article <hjkglp$trt$1(a)speranza.aioe.org>, Richard McBeef
<cho.seung-hui(a)vt.edu> wrote:


> At YAPC 2009 there was a good talk about some
> occasions where a LL is nice to have in Perl.
> Here is a link to the slides.
>
> http://github.com/lembark/Talks/blob/21437a3e24f1ea809685a3e0bb162119bd05b84b/
> perly-linked-lists.pdf


I missed that YAPC. I'll look at those slides and see what I can use to
improve the answer.

Thanks,
 | 
Pages: 1
Prev: FAQ 9.4 How do I remove HTML from a string?
Next: LibXML (XPATH) and escape