I studied all the related posts on the site and I feel there needs to be a more informative answer to this, so here's my effort:

The purpose of a linked list in say C is to overcome C's deficiency in dynamic handling of data storage (similar deficiency exists for e.g. Pascal - only the syntax is different). Although C has the capability of dynamically increasing and decreasing the length of an array of fixed-sized elements (be they structured or not), you can't delete or add to the middle of an array and in effect not at the beginning either. The solution in languages like C is to have a linked list of dynamically allocated storage units. There is however a (bit clunky) implementation of a hash in C++ (called a map) but which is far more limited in its implementation than in Perl - achieving similar functionality as for Perl would not be at all easy in C++ and certainly beyond the capability of the average programmer. The map attempts to simulate an associative array over a fixed storage area with the effect that it can't achieve more than the most trivial of hash implementations. Java uses the C++ model as the basis for its data storage and inherits the same limitations.

Perl, on the other hand, implements its structures more flexibly, allowing seamless dynamic storage and preventing the need for a linked list. In Perl hashes and arrays do not need their elements to be of a fixed length or type and thus instead of a linked list, an array of hash or array will suffice because elements can be added, deleted and amended anywhere in the array (and obviously anywhere in a hash) including changing the type as well as size used by a given element with complete flexibility.

There is one exception however: sometimes, but very rarely, a requirement might functionally suggest the implementation of a linked list. For example, a binary tree might be needed in some actual business functionality (as opposed to reacted technical functionality) such as simulating a particular database algorithm. In that case, you should implement the linked list dynamically as you would in C++ rather than use an array or hash container at all (else you are duplicating the overheads of Perl versus your own implementation!):

# example: building a binary tree from an unsorted file of strings
$_ = <>;
chop;
my $llref;
{ $llref = { data => $_ }; }
while ( <> ) {
    chop;
    Bin( $llref );
}

# on completion there is only $llref defined pointing at a dynamic lis
+t element being an anonymous hash with links to other similar list el
+ements.

sub Bin {
    my $llref = shift;
    if ( $_ < $llref -> { data } ) {
        if ( defined ( $llref -> { left } ) ) {
            Bin( $llref -> { left ));
        }
        else {
            $llref -> { left } = { data => $_ };
        }
    elsif( $_ > $llref -> { data } ) {
        if ( defined( $llref -> { right } ) ) {
            Bin( $llref -> { right ));
        }
        else {
            $llref -> { right } = { data => $_ };
        }
    }
}
[download]

In summary: a linked list is needed in languages which depend in some way on fixed storage. Perl's fully dynamic storage model make "technically required" linked lists unnecessary. Functionally required linked lists should use dynamic hashes as elements of the list and link them by reference rather than make an aoh or hoh container.

Update: A terniary tree requirement would make the linked list an even stronger technical candidate in Perl, making it much harder to use hashes and arrays as outer structural containers but I can't think of a functional requirement needing a terniary tree.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.