Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

OOP/Linked List Question

by hok_si_la (Curate)
on Feb 07, 2005 at 16:06 UTC ( #428711=perlquestion: print w/ replies, xml ) Need Help??
hok_si_la has asked for the wisdom of the Perl Monks concerning the following question:

Greetings Monks,

I am practicing my OOP in Perl, and decided I would try to create a Circly Linked List. Each node would contain a name, an id number, and a reference to the next node. I have done this several times in C++. How is it best accomplished in Perl? Would this simply be a hash of arrays or can it be built cheaper than that?

Thanks for your assistance,
hok_si_la

Comment on OOP/Linked List Question
Re: OOP/Linked List Question
by Grygonos (Chaplain) on Feb 07, 2005 at 16:21 UTC

    The following structure implements a two node circularly linked list... you can extend it as far as you want.. you still need to create the methods to add something to it, and delete something from it. the id number is the array position, the name is the data key of the hash.. and the next key is the reference to the next node.

    warning.. code contains infinite loop to demonstrate that what is considered to be the current node is changing
    use strict; use warnings; my $ll = [ {data=> 'x', next=> 1}, {data=> 'y', next=> 0}]; my $item = $ll->[0]; while(1) { print $item->{data}."\n"; $item = $ll->[$item->{next}]; }

    update addItem adds an item to the end of the list.. causing whatever pointed to the beginning of the list to now point to the new item and making the new item point to the beginning of the list.

    use strict; use warnings; use Data::Dumper; my $ll = [ {data=> 'x', next=> 1}, {data=> 'y', next=> 0}]; my $data = 'z'; addItem($ll,\$data); print Dumper($ll); sub addItem { my ($ll,$item) = @_; foreach(@{$ll}) { $_->{next} = @{$ll} if $_->{next} == 0; } $ll->[@{$ll}] = {data=>$$item, next=>0}; return; }
Re: OOP/Linked List Question
by holli (Monsignor) on Feb 07, 2005 at 16:22 UTC
    You can build a real linked list, you donīt even need objects:
    use strict; use warnings; #build a cyclic list of hashes my $root = {value => 0, next => undef}; my $last = $root; for (my $i=1; $i<5; $i++) { my $node = { value=>$i, next => undef}; $last->{next} = $node; $last = $node; } $last->{next} = $root; #cycle: my $node = $root; for ( my $j=0; $j<10; $j++ ) { print $node->{value}, "\n"; $node = $node->{next}; }
    Update:
    The basic algorithms are the same than in any other language. The most important here is an understanding of how references work (see perlre), so i leave the rest as excercise for the interested reader.
    holli, /regexed monk/
Re: OOP/Linked List Question
by demerphq (Chancellor) on Feb 07, 2005 at 16:28 UTC

    There isnt a huge need for linked lists in perl. However you can implement them using any number of representations. Probably the easiest to read is with HoH's, but AoA's are possible too. Remember that perl simulates 2d data structures by allowing collection objects to hold references to other collection objects. So if we have $obj1={}; and $obj2={}; then $obj1->{next}=$obj2; $obj2->{next}=$obj1 will make a circular data structure. Of course there are all kinds of odd issues associated with circular data structures, most importantly that if improperly used they will result in a memory leak as perls refcoutn based GC wont free them even if your code has "lost" track of the pointers.

    ---
    demerphq

Re: OOP/Linked List Question
by Tanktalus (Canon) on Feb 07, 2005 at 16:31 UTC

    I've created all sorts of ADTs in C/C++. I've used even more (Standard Template Library was great!). I've never even thought about it in perl. I'm sure someone will come along and tell me why it was such a great thing for what they were doing. That's fine - but AoH, HoA, HoHoHoH, AoAoH, etc., these kinda take the place of those other container types that you need so badly in other languages.

    That's not to say it can't be done in Perl, or even that, as an excersise in learning how references work, it's not worth doing in perl. Just that I've never had a reason to use it.

    Perl has great data structures internally which seem to solve the problems: hashes and arrays. And I can choose whichever one makes sense. Iterating over them is easy, whether that's foreach over an array, over the keys to a hash, or while/each over a hash.

    Usually, I think, a linked list is used to make things easy to add/remove from the beginning and the end of the list. That's what shift, unshift, push, and pop are for. Perl is already likely using a linked list as it is. And it's probably got some other abstractions put into its "array" type, too, to give you direct access to an arbitrary scalar (ref's are scalars, too ;->) in the array, to always know the length, etc.

    Circular lists - such that instead of falling off the list at the end, you simply wrap around to the beginning - are not something I found a lot of use for in C/C++ anyway, so perhaps you may still find the same use for them in perl. Mind you, if all you want to do is be able to start at an arbitrary point in the list, you can do the same in perl pretty easily: foreach my $s (@list[$n..$#list,0..$n-1]) { ... }.

    I guess my point is ... you might be better off learning perl idioms to get your job done faster rather than trying to write C/C++ in perl. ;-)

      I thank all of you for your insight. Each one of you brought something useful to the table.

      One reason I was interested in learning how to create a linked list data type is because of an app I am programming. I am mainly trying to improve the speed of one operation: removing or adding a record into the middle of a list. When done generically, the operation gets expensive as the number of records or nodes increase. Instead of shifting all the list elements up or down, I would prefer to just delete a node an update a pointer. I am probably making it more difficult than it has to be. Once I am able to understand the quickest way to do this I plan on creating another 'good ole ADT classic', the binary search tree.

      I'll post something this weekend for you hardcore coders with nothing better to do so you can see the project I am working on. It is called FACT. It simply translates mono-alphabetic substitution ciphers using an algorithmic/AI approach hybrid. I am attempting to solve cryotoquips quicker than the app located here: http://www.blisstonia.com/software/Decrypto/ . I believe by incorporating his pattern idea along with a group of AI rules, the results could be returned quicker.

      Thanks again for all of your insight,
      hok_si_la
        Instead of shifting all the list elements up or down, I would prefer to just delete a node an update a pointer.

        How big is your list?

        I ask for two reasons:

        1. If your list is large, using hashes or arrays to create your linked list will cost you lots of memory.
        2. Despite it's O(N) credentials, splice is remarkably adept at inserting things into the middle of even fairly long ( < ~ 20,000 elements ) lists.

        And sometimes, the easy option is good enough. If your list is long enough for the cost of spliceing to become a problem, then you will also be approaching that point at which contructing linked lists from either hashes or arrays starts to consume very large volumes of memory.

        Using a heap, or even a string-based list may prove to be fast enough whilst keeping your memory consumption with the range of sanity.


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re: OOP/Linked List Question
by talexb (Canon) on Feb 07, 2005 at 16:44 UTC

    As already ably replied by Tanktalus above, your question sounds like a solution looking for a solution.

    Instead, think about why you need a linked list, and see if a hash won't solve your problem instead.

    Alex / talexb / Toronto

    "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

Re: OOP/Linked List Question
by RazorbladeBidet (Friar) on Feb 07, 2005 at 16:47 UTC
    Here's an exercise in fun OOP that's fairly unnecessary, but just in case you REALLY want objects :)
    package LinkedList; use strict; my $HEAD_NODE = undef; # use a global var to get the head node sub new { my $this = shift; my $class = ref($this) || $this; my $self = {}; $self->{_ID} = shift || "Id"; $self->{_NAME} = shift || "Default"; $HEAD_NODE = $self unless defined $HEAD_NODE; $self->{_NEXT} = $HEAD_NODE; bless $self, $class; } sub name { my $self = shift; $self->{_NAME} = shift if @_; return $self->{_NAME}; } sub id { my $self = shift; $self->{_ID} = shift if @_; return $self->{_ID}; } # this really should handle references to objects, and not # the object itself... sub add_node { my $self = shift; my $node_to_add = shift; $self->{_NEXT} = $node_to_add; } # this really should handle references to objects, and not # the object itself... sub next { my $self = shift; return $self->{_NEXT}; } # may not be necessary DESTROY { my $self = shift; $self->{_NEXT} = undef; } 1; ---- #!/usr/bin/perl use strict; use LinkedList; my $first_node = LinkedList->new( 1, "data" ); my $second_node = LinkedList->new( 2, "more data"); my $third_node = LinkedList->new(3, "even more data"); $first_node->add_node( $second_node ); $second_node->add_node( $third_node ); my $node = $first_node; for ( my $i = 0; $i < 100; $i++ ) { print $node->id." ".$node->name."\n"; $i++; $node = $node->next; }
    Update: A note from perlobj:
    In the meantime, the best solution is to create a non-
    recursive container class that holds a pointer to the self-
    referential data structure. Define a DESTROY method for 
    the containing object's class that manually breaks the 
    circularities in the self-referential structure.
    
    So maybe instead, call the above package (class) LinkedListNode and have a container LinkedList, just to be safe.
Re: OOP/Linked List Question
by ambrus (Abbot) on Feb 07, 2005 at 17:08 UTC

    Just two words of caution. If you create a long list-like structure in perl, you have to take care how it is deleted when the reference count drops to zero. For example, this code causes a segfault on my machine:

    perl -we '$x = 1; $x = [$x] for 0 .. 0 + $ARGV[0]; $x = ();' 50000
    (you might have to increase the numeric argument to reproduce this). This is because as the reference-count garbage-collector deletes $x<code>, it has to delete <code>$$x[0] first, for which it has to delete $$x[0][0] first etc, and it does this thing recursively. This would not normally be a problem, but can cause a problem in two cases. Firstly, stack space is used for this recursion, which is limited, so in the case of such a long list, the stack will be full and that's why you get the error. Indeed, if you look at the backtrace, you'll see a long stream of frames like this:
    ... #78 0x080bd016 in Perl_sv_free () #79 0x080acd3e in Perl_av_undef () #80 0x080bcd9a in Perl_sv_clear () #81 0x080bd016 in Perl_sv_free () #82 0x080bcad5 in Perl_sv_clear () #83 0x080bd016 in Perl_sv_free () #84 0x080acd3e in Perl_av_undef () #85 0x080bcd9a in Perl_sv_clear () #86 0x080bd016 in Perl_sv_free () #87 0x080bcad5 in Perl_sv_clear () #88 0x080bd016 in Perl_sv_free () #89 0x080acd3e in Perl_av_undef () #90 0x080bcd9a in Perl_sv_clear () #91 0x080bd016 in Perl_sv_free () #92 0x080bcad5 in Perl_sv_clear () ...

    The other problem is circular references. A doubly-linked list contains circular references, so if you just undef a reference to it, it will contain circular references, the reference count will never drop to zero, and memory will leak. You can usually avoid this by explicitly undefing some refernces inside the data structure when you want to free the list. The DESTROY method can help you in this. For example, this code leaks memory (again, increase the numeric argument to make it leak more):

    perl -we 'for (0 .. $ARGV[0]) { my $y = 1; my $x = \$y; $x = [$x] for +0 .. 1000; $y = $$x[0]; }; system "ps u $$"' 1000

    Update: The first problem is not that easy to cure, but it is possible. Doing some quick tests, it seems that the garbage-collector in (newer) pythons, the one in Mathematica, and the one in maple are free from this defect; while the simple one in ruby, -- wierdly -- that of bigloo scheme, and (Update) that of guile too have the same limitation. (This of course doesn't mean anything as those are not refcounting gcs, but mark-and-sweep or some similar.) As for the second one, it's specific to reference counting.

Linked Lists With No Memory Leak
by jdporter (Canon) on Feb 07, 2005 at 22:53 UTC

    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.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (7)
As of 2014-12-22 12:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (116 votes), past polls