Linked-list Style Data Structure

impossiblerobot has asked for the wisdom of the Perl Monks concerning the following question:

Again, I humbly approach the monastery ...

In a wizard-style web application I've created, I use the following data structure to track navigation:

$navigation_map = {
    first_page       => {
        PREVIOUS => '',
        NEXT     => 'second_page',
    },
    second_page      => {
        PREVIOUS => 'first_page',
        NEXT     => 'third_page',
    },
     third_page         => {
        PREVIOUS => 'second_page',
        NEXT     => 'fourth_page',
    },
    fourth_page         => {
        PREVIOUS => 'third_page',
        NEXT     => '',
    },
};
[download]

which allows me to say $navigation_map->{second_page}{NEXT} to find out what the next screen should be.

Unfortunately, the same list of pages does not appear in each of the installations of this app, so constructing the navigation map and editing the links for each instance is a pain. What I should be able to do is use an array, so I can just do this:

$navigation_map = [qw(first_page second_page third_page fourth_page)];
[download]

So I created an object to build the hash structure for me (from an array):

package List::Navigator;

sub new
{
    my $class = shift;
    my ($list) = @_;

    my $data = {};
    my ($previous, $next);
    for my $item (@$list)
    {
        $data->{$item}{PREVIOUS} = $previous;
        $data->{$previous}{NEXT} = $item if defined $previous;
        $previous = $item;
    }
    bless $data, $class;
}
[download]

I could then use it as:

my $nav_list = [qw( first_page second_page third_page fourth_page )];

my $navigation_map = List::Navigator->new( $nav_list );
[download]

Of course the next natural step was creating accessors so that I could say $navigation_map->next('second_page') instead of $navigation_map->{second_page}{NEXT}. I also created a "current page" pointer so I could use the class as an iterator.

This solution seems to work well for my current usage, since I currently have no need to insert or delete entries (which would require building additional methods). However, my question (finally) is: What better (or alternate) ways would you suggest for implementing this functionality? Is there a generic solution I should be looking at?

Impossible Robot

Comment on Linked-list Style Data Structure Select or Download Code

Replies are listed 'Best First'.
•Re: Linked-list Style Data Structure by merlyn (Sage) on Oct 01, 2002 at 15:53 UTC
If the data were more structured, I'd look at marshalling it as XML, and using XML::XPath for queries and updates. This would let you find pages based on name to get the "next" or "previous" pages trivially, including doing inserts and rewriting the XML to your marshall file if you need. You could also find associated data by storing it deeper in the same node: `<pages> <page ident="first page" /> <page ident="second page"> <validation type="numeric"/> </page> <page ident="third page" /> </pages>` [download] This would be a simple format to edit, and to process electronically. -- Randal L. Schwartz, Perl hacker	[reply] [d/l]
Re: •Re: Linked-list Style Data Structure by impossiblerobot (Deacon) on Oct 07, 2002 at 13:08 UTC
Thanks, merlyn. Although it seems a little heavy for this particular application, it is a useful approach that I had not considered and might find a use for. Impossible Robot	[reply]
Re: Linked-list Style Data Structure by Abigail-II (Bishop) on Oct 01, 2002 at 16:40 UTC
You are asking about alternative ways to implement "this functionality", but what is your module actually offering as functionality? Is there more than just next/previous based on named indices? If not, I'd keep the entries in an array, and use a hash to map names to indices. The only reason to use linked lists instead of arrays is performance for inserts and deletes. But you aren't inserting or deleting. Abigail	[reply]
Re: Re: Linked-list Style Data Structure by impossiblerobot (Deacon) on Oct 07, 2002 at 13:06 UTC
Thanks, Abigail-II, for pointing out the vagueness in my question. The specific functionality that I am looking for at this point is essentially as you stated: The ability to define the data structure simply (preferably using an array or list). The ability to find out the name of the next or previous item based on the the current (or a named) item. Although I currently do not need to insert or delete elements, I might need to in the future. However, since my lists will never be that long, and I would not do it that often, I could probably still use your suggestion (and rebuild the entire index when necessary) without any noticable performance issues. In any case, it seems that you are advocating trying to use a data structure appropriate to the task, rather than relying on a generic structure that might be less suited. Am I understanding correctly? Impossible Robot	[reply]
Re: Linked-list Style Data Structure by Abigail-II (Bishop) on Oct 07, 2002 at 14:12 UTC
In any case, it seems that you are advocating trying to use a data structure appropriate to the task, rather than relying on a generic structure that might be less suited. Am I understanding correctly? Yes, that's the Perl (and Unix) way. You have a large toolkit at your disposal, with lots of different tools. Different tools for different jobs. Use your toolkit. The saying "if all you have is a hammer, everything looks like a nail" is not at all appropriate for Perl. Abigail	[reply]
Re: Linked-list Style Data Structure by Zaxo (Archbishop) on Oct 01, 2002 at 16:16 UTC
Linked lists have a gotcha in perl. If you implement them with references, you can easily create cycles which perl cannot destroy. That happens because each element's refcount is held up by its predecessor. That is easily handled with a DESTROY method which breaks the cycle by overwriting the reference to successor with other data. In recent perl, it is possible to use weak references to avert the problem. I like the idea of using Graph for the sort of thing you're doing. After Compline, Zaxo	[reply]
Re: Linked-list Style Data Structure by Juerd (Abbot) on Oct 01, 2002 at 16:14 UTC
I'm not familiar with linked lists, and have never used them. They don't seem to be worth the trouble (normal Perl arrays work well enough). For wizardish web applications, I often just use numeric indexes (internally mapped to page names), or I store only the next page's name and let the browser handle the history.back(). Even iterating over an array each time would be more efficient than building a large data structure, I think. Your list thingy would be quite a bit faster if you used arrays instead of hashes for saving the NEXT and PREVIOUS. You can use constants for array indexes to maintain readability. - Yes, I reinvent wheels. - Spam: Visit eurotraQ.	[reply]
Re: Re: Linked-list Style Data Structure by impossiblerobot (Deacon) on Oct 29, 2002 at 18:42 UTC
Thanks, Juerd. Unfortunately, the application I am working with already requires knowing both the 'next' and 'previous' views, and I don't have time to completely restructure it at this time. Since this navigation list will be fairly short, and it will only be accessed a few times in each invocation of the script, efficiency probably won't be as much of an issue. However... Modifying my code to use arrays (with constants) was trivial, and it is much faster than using a hash (which will be useful if I need to use this code with longer lists or access it more often). However, iterating over the array each time (even with exiting on a successful match) was slower than building the data structure when accessing it a couple of times. Impossible Robot	[reply]
Re: Linked-list Style Data Structure by BUU (Prior) on Oct 01, 2002 at 21:31 UTC
(cheating horribly, since your using the First page, second page etc) `my @pages=(page1=>page2=>page3=>page4=>); my $i=get_current_page(); my $next_page=$pages[$i+1]; my $prev_page=$page[$i-1];` [download] Or somethign like that? Or am i totally missing something	[reply] [d/l]
Navigatible list structure by rir (Vicar) on Oct 07, 2002 at 16:13 UTC
It seems you could just use an array with a current position marker. `sub new { die "bad param count" unless 2 == @_; my ($me, $arr_ref) = @_; bless { current => 0, data => $arr_ref}, ref $me \|\|$me; }` [download]	[reply] [d/l]


laziness, impatience, and hubris
	PerlMonks