Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Dynamically Linked List

by Carl the Rake (Initiate)
on Jan 30, 2001 at 10:10 UTC ( #55194=perlquestion: print w/replies, xml ) Need Help??
Carl the Rake has asked for the wisdom of the Perl Monks concerning the following question:

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?

Replies are listed 'Best First'.
Re: Dynamically Linked List
by chromatic (Archbishop) on Jan 30, 2001 at 10:49 UTC
    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.

Re: Dynamically Linked List
by bbfu (Curate) on Jan 30, 2001 at 10:56 UTC

    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 }; }

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

Re (tilly) 1: Dynamically Linked List
by tilly (Archbishop) on Jan 30, 2001 at 14:38 UTC
    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...

Re: Dynamically Linked List
by dkubb (Deacon) on Jan 30, 2001 at 10:28 UTC

    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.

Re: Dynamically Linked List
by MeowChow (Vicar) on Jan 30, 2001 at 13:40 UTC
    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.

Re: Dynamically Linked List
by ColonelPanic (Friar) on Jan 30, 2001 at 18:27 UTC
    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
Re: Dynamically Linked List
by Elgon (Curate) on Jan 30, 2001 at 22:48 UTC
    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.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://55194]
Approved by root
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (4)
As of 2018-01-21 16:42 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (228 votes). Check out past polls.