Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Even though any implementation is going to need references internally to get its job done, it is a misconception that the links themselves must be references. In the implementation below, the nodes are linked together by the value of the ID. So, given the "next ID" of one node, you look it up in a hash to find the actual next node. Sometimes I find this a nicer way to work. One caveat is that, as a consequence, IDs are required to be unique. Not that that's a bad thing, most of the time...

Note also that by not having nodes contain references to other nodes, this kind of implementation is free from the memory leak problem cited by others in this thread. (On the other hand, it introduces a possibility for broken links, since they are essentially weak references.)

I never expose the structure of the node, nor any of the data members other than the id and the value. The caller must not be allowed to twiddle with the innards, or you'll have a recipe for disaster.

package CircList; use strict; use warnings; sub new { my( $pkg ) = @_; bless { list => {}, cur => undef, # cursor. Circular lists don't really have a "r +oot" }, $pkg } # if the list is currently empty, after_id must be undef. # otherwise, after_id must NOT be undef. sub insert { my( $self, $id, $value, $after_id ) = @_; if ( defined $self->{'cur'} ) { defined $after_id or die "Can't insert ($id => $value): previous node not specified +."; exists $self->{'list'}{$after_id} or die "Can't insert ($id => $value): no previous id '$after_id' +in list."; exists $self->{'list'}{$id} and die "Can't insert ($id => $value): id ($id => $self->{'list'}{ +$id}{'value'}) already exists!"; # link in a new node: $self->{'list'}{$id} = { id => $id, value => $value, next_id => $self->{'list'}{$after_id}{'next_id'}, }; $self->{'list'}{$after_id}{'next_id'} = $id; } else { defined $after_id and die "Can't insert ($id => $value): no previous id '$after_id' +(list is currently empty)."; # link in the first node: $self->{'list'}{$id} = { id => $id, value => $value, next_id => $id, }; $self->{'cur'} = $id; } $self->{'list'}{$id} } sub find_prev { my( $self, $id ) = @_; $self->{'list'}{$id} or die "Id '$id' does not exist in list!"; for ( keys %{ $self->{'list'} } ) { $self->{'list'}{$_}{'next_id'} eq $id and return $_; } die "Integrity fault: '$id' is not the next_id of any node in list +!"; } # relatively expensive sub remove # return ( id, value ) pair { my( $self, $id ) = @_; $self->{'list'}{$id} or die "Id '$id' does not exist in list!"; my $prev_id = $self->find_prev($id); if ( $prev_id eq $id ) { # special case: removing the last node in the list $self->{'cur'} = undef; } else { # re-link to skip the one being removed: $self->{'list'}{$prev_id}{'next_id'} = $self->{'list'}{$id}{'n +ext_id'}; $self->{'cur'} eq $id and $self->{'cur'} = $self->{'list'}{$id +}{'next_id'}; } my $val = $self->{'list'}{$id}{'value'}; delete $self->{'list'}{$id}; ( $id, $val ) } # (could be generalized to accept a pattern, or some other criteria te +ster) sub look_up # return ( id, value ) pair { my( $self, $id ) = @_; $self->{'list'}{$id} or die "Id '$id' does not exist in list!"; ( $id, $self->{'list'}{$id}{'value'} ) } sub traverse_from { my( $self, $id, $callback ) = @_; $self->{'list'}{$id} or die "Id '$id' does not exist in list!"; my $cur_id = $id; do { $callback->( $cur_id, $self->{'list'}{$cur_id}{'value'} ); $cur_id = $self->{'list'}{$cur_id}{'next_id'}; } while $cur_id ne $id; } # example: package main; my $l = new CircList; $l->insert( 'alpha', 1 ); $l->insert( 'gamma', 3, 'alpha' ); $l->insert( 'beta', 2, 'alpha' ); $l->traverse_from( 'beta', sub { print "( @_ )\n" } );
You could, of course, extend this with methods to set/get the cursor ($self->{'cur'}), and other fun things. (A traverse_from_cursor comes readily to mind.)

In reply to Linked Lists With No Memory Leak by jdporter
in thread OOP/Linked List Question by hok_si_la

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • 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! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

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

      My preferred Perl binaries come from:














      Results (164 votes), past polls