Dynamically Linked List

[Carl the Rake]

As a programming exercise (cause I do this for "Fun"), I'm trying to create a simple address book style data-base in Perl. What I'd like to be able to do is to set-up a hash with the information fields as indicies in the hash-table, then a reference to the next hash, creating a string of hashes that all point to each other. Unfortunately, I'm having no luck finding information on dynamically allocating space within a program in Perl (looking for something like malloc() in C). Is there anybody that can point me to some documentation, or possibly an example of this kind of structure?

[chromatic]

Perl allocates space automatically, as needed. You can do something like this:

my $tail;
for (1 .. 10) {
    my %record = (
        title => (1950 + $_),
        artist => 'chromatic orchestra',
    );

    # handle first condition
    $tail ||= $record;
    
    $tail->{_prev} = \%record;
    $record{_next} = $tail;
    $tail = \%record;    
}

Untested, but that's generally one way to do it.

Update: Fastolfe pointed out that since I had changed my mind in the middle about the nature of %record, I should have changed the curly braces to parens. Fixed.

[bbfu]

dkubb's suggested reading sounds like the thing. But if you're looking for a quicker example:

use strict;

my $First_Hash = new_entry();
my $First_Hash->{'Next'} = new_entry();
# ... etc ...

# Creates a new, dynamically allocated hash and returns
# a pointer to it.
sub new_entry {
    return {
        Field1 => 'Data',
        Field2 => 'Data',
        Next => undef
    };
}

bbfu
Seasons don't fear The Reaper.
Nor do the wind, the sun, and the rain.
We can be like they are.

[tilly]

It sounds like you are trying to produce a linked list in Perl. For most purposes linked lists are not necessary because native arrays are efficient enough. However inserting in the middle is still O(n). So if you need more complex data structures then you might want to take a look at how Dominus implemented BTrees in Perl.

For production code I would just use a real database or else use DB_File to tie a hash to an efficient BTree implementation...

[dkubb]

If you're interested in learning about data structures in perl, by far the most comprehensive book on this subject is Mastering Algorithms with Perl. It covers hashes and arrays, then quickly moves into linked lists, doubly linked lists, binary trees, heaps, and more advanced related subjects.

O'Reilly has a sample chapter that you can read here.

[MeowChow]

Not only is memory allocation unnecessary in Perl, but pre-initializing references in your arrays/hashes is also unnecessary as well, due to a nice bit of magic called auto-vivification.

For more info on this, read perldsc and perlref. They have all the answers you are looking for.

[ColonelPanic]

perllol has information specifically on using references to create complex data structures.

When's the last time you used duct tape on a duct? --Larry Wall

[Elgon]

This sounds to me a bit like the BASIC programmer's classic question: Why is there no 'PEEK/POKE' command in Perl?

Perl tries to get away from hardware issues where at all possible by using automagical tricks like assigning memory for you and vivification. You worry about the problem let Perl deal with the hardware end.

Elgon