Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Linked Lists With No Memory Leak

by jdporter (Paladin)
on Feb 07, 2005 at 22:53 UTC ( [id://428849]=note: print w/replies, xml ) Need Help??


in reply to OOP/Linked List Question

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.)

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://428849]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (5)
As of 2024-03-28 20:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found