Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Efficient Linked Lists

by Ionizor (Pilgrim)
on Jan 31, 2003 at 20:00 UTC ( #231698=perlquestion: print w/ replies, xml ) Need Help??
Ionizor has asked for the wisdom of the Perl Monks concerning the following question:

I'm trying to create a pair of hashes so that I can easily traverse a list of filenames in either direction. The code I've come up with follows. Does anybody know a more efficient way to do this? Preferably so that I can remove the ugly "do first case, loop by index, do last case" thing I've got. I'd prefer one loop but didn't want to put a pair of ifs inside that will only be used once each.

# populate filename array my @filenames = qw(file1 file2 file3 file4 file5 file6); my %next; my %prev; # Link next to first filename $next{$filenames[0]} = $filenames[1]; # Link next and prev to all the filenames for (my $fileindex = 1; $fileindex < scalar (@filenames) - 1; $fileind +ex++) { $next{$filenames[$fileindex]} = $filenames[$fileindex + 1]; $prev{$filenames[$fileindex]} = $filenames[$fileindex - 1]; } # Link prev to last filename $prev{$filenames[-1]} = $filenames[-2];

Thanks, monks.

--
Grant me the wisdom to shut my mouth when I don't know what I'm talking about.

Comment on Efficient Linked Lists
Download Code
Re: Efficient Linked Lists
by jdporter (Canon) on Jan 31, 2003 at 20:13 UTC
    Why do you need a linked list? You already have an array; can't you just iterate over the array backwards and forwards?

    What I sometimes do is create a reverse-lookup table:
    my %index_of; @index_of{ @filenames } = (0..$#filenames); # given a filename, find its predecessor or successor: my $predecessor = $filenames[ $index_of{ $filename } - 1 ]; my $successor = $filenames[ $index_of{ $filename } + 1 ];

    jdporter
    The 6th Rule of Perl Club is -- There is no Rule #6.

      The goal is to create a set of static HTML pages with previous and next links to move from file to file, so it's not straight iteration (Note to self: Think while typing). I need to print out the filename, then a link to the previous filename, then a link to the next filename.

      I think a reverse lookup table will do the job nicely. Thanks.

      --
      Grant me the wisdom to shut my mouth when I don't know what I'm talking about.

        I think a reverse lookup table will do the job nicely. Thanks.
        A whuh?

        Sounds like just a simple list, again. As four or five answers in this thread have already said. What requirement prevents you from using the code that has been posted four or five times?

        Do not construct a doubly linked list. People build those things because they don't have perlfunc:splice, so in Perl, it's almost always the wrong way to go.

        -- Randal L. Schwartz, Perl hacker
        Be sure to read my standard disclaimer if this is a reply.

Re: Efficient Linked Lists
by dpuu (Chaplain) on Jan 31, 2003 at 20:26 UTC
    I'm not sure that its more efficient, but you could try:
    # create pairs my @tmp = map { $_, $_ } @filenames; # rotate push @tmp, shift @tmp; # create the result my %next = @tmp; my %prev = reverse @tmp;
    In this code, the hashes form loops: to avoid that, replace the rotate step by code that remove the first and last elements. --Dave
Re: Efficient Linked Lists
by YuckFoo (Abbot) on Jan 31, 2003 at 20:50 UTC
    Go ahead, link the whole list, then delete the previous entry of the first and the next entry of the last.

    LinkFoo

    for my $fileindex (0..$#filenames) { $next{$filenames[$fileindex]} = $filenames[$fileindex + 1]; $prev{$filenames[$fileindex]} = $filenames[$fileindex - 1]; } delete($prev{$filenames[0]}); delete($next{$filenames[-1]});
Re: Efficient Linked Lists
by pg (Canon) on Feb 01, 2003 at 07:09 UTC
    Linked list is doable in Perl, and in general, linked list has its own benefits under certain context. You are not the first person talking about this, and you are not alone. I read about this topic a while ago, in couple of published Perl books.

    Here is a quick OO solution I put together. It is only to prove the concept, and it obviously does not implement all the needed methods. The test case I given below worked, but there is no other test case being tried.

    The solution is OO. In DoubleLinkedList.pm, the process_thru_forward and process_thru_backward functions allow you to specify callback functions and parameters to callback functions, and they are very flexible.
    DoubleLinkedListElement.pm: package DoubleLinkedListElement; use Hash::Util (lock_keys); use strict; sub new { my $self = {}; $self->{VALUE} = undef; $self->{NEXT} = undef; $self->{PREV} = undef; bless $self; lock_keys(%$self); return $self; } sub value { my $self = shift; if (@_) { $self->{VALUE} = shift; } return $self->{VALUE}; } sub next { my $self = shift; my $ret = $self->{NEXT}; if (@_) { $self->{NEXT} = shift; } return $ret; } sub prev { my $self = shift; my $ret = $self->{PREV}; if (@_) { $self->{PREV} = shift; } return $ret; } 1; DoubleLinkedList.pm: package DoubleLinkedList; use DoubleLinkedListElement; use Hash::Util (lock_keys); use strict; sub new { my $self = {}; $self->{FIRST} = undef; $self->{LAST} = undef; bless $self; lock_keys(%$self); return $self; } sub first { my $self = shift; return $self->{FIRST}; } sub last { my $self = shift; return $self->{LAST}; } sub append { my ($self, $value) = @_; my $element = new DoubleLinkedListElement(); $element->value($value); if ($self->last()) { $self->last()->next($element); $element->prev($self->last()); $self->{LAST} = $element; } else { $self->{FIRST} = $element; $self->{LAST} = $element; } } sub process_thru_forward { my ($self, $func, @param) = @_; for (my $this = $self->first(); $this; $this = $this->next()) { &$func($this, @param); } } sub process_thru_backward { my ($self, $func, @param) = @_; for (my $this = $self->last(); $this; $this = $this->prev()) { &$func($this, @param); } } 1; test.pl: use Data::Dumper; use DoubleLinkedList; use strict; my $dl_list = new DoubleLinkedList; foreach (1..10) { $dl_list->append($_); } $dl_list->process_thru_forward(\&plus_and_display, 10); $dl_list->process_thru_backward(\&plus_and_display, 10); sub plus_and_display { my ($this, $adj) = @_; print $this->value + $adj, "\n"; }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://231698]
Approved by BazB
Front-paged by jdporter
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (14)
As of 2014-07-11 14:28 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (227 votes), past polls