|
Posted by PerlFAQ Server on February 28, 2008, 9:03 pm
Please log in for more thread options
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->) {
print $node->, " ";
}
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-> = $list->;
$list-> = $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.
|
| Similar Threads | Posted | | FAQ 4.46: How do I handle linked lists? | October 28, 2004, 11:03 pm |
| FAQ 4.46 How do I handle linked lists? | February 8, 2005, 12:03 pm |
| FAQ 4.46 How do I handle linked lists? | May 9, 2005, 5:03 am |
| FAQ 4.46 How do I handle linked lists? | July 24, 2005, 10:03 pm |
| FAQ 4.46 How do I handle linked lists? | October 8, 2005, 10:03 pm |
| FAQ 4.46 How do I handle linked lists? | October 29, 2005, 10:03 am |
| FAQ 4.46 How do I handle linked lists? | July 7, 2006, 3:03 pm |
| FAQ 4.46 How do I handle linked lists? | August 17, 2006, 9:03 pm |
| FAQ 4.46 How do I handle linked lists? | October 18, 2006, 9:03 pm |
| FAQ 4.46 How do I handle linked lists? | December 30, 2006, 9:03 pm |
|
XML Sitemap