in reply to Re: Perl linked list
in thread Perl linked list

Believe or not,I am working at SDSU... and the test link is given public access by me also. It is just used for self-evaluation purpose. You can log in the account using happye321@gmail.com the password is Happye321

Replies are listed 'Best First'.
Re^3: Perl linked list (HoH)
by LanX (Saint) on Mar 31, 2015 at 18:37 UTC
    OK, I ran the following code

    # you can use print for debugging purposes, e.g. # print "this is a debug message\n"; use Data::Dumper; sub solution { my ($L)=@_; print Dumper $L; # write your code in Perl 5.14 }

    and got this output, which clarifies that the implementation is done with hashes of hashes

    (sorry indentation lost while copying)

    Running solution... Compilation successful. Example test: [1, 1, 1, 1] Output (stderr): WARNING: producing output may seriously slow down your code! Output:

    $VAR1 = {
    next => {
    next => {
    next => {
    next => undef,
    value => 1
    },
    value => 1
    },
    value => 1
    },
    value => 1
    };

    Reading the confusing text reveals that those lazy people didn't even try to use proper Perl terminology.

    Pointer? Dictionary? Empty? WTF?

    Cheers Rolf
    (addicted to the Perl Programming Language and ☆☆☆☆ :)

    PS: Je suis Charlie!

      Thanks for your help LanX, once Known the data structure, everything make sense now!
Re^3: Perl linked list
by Laurent_R (Canon) on Mar 31, 2015 at 19:08 UTC
    A quick try. My understanding of the data structure is as follows:
    use strict; use warnings; my $pt = { value => "D", next => undef }; my $pt2 = {value => "C", next => $pt}; $pt = {value => "B", next => $pt2}; my $L = { value => "A", next => $pt};
    (It could be much simpler, but I wanted to stay at a relative beginner level.

    It took me less than 5 minutes to write the code to count the nodes, but I'll reveal it only later, once I am sure that this cannot used for other purpose.

    My iterative solution subroutine prints out the node being visited and the node count as follows:

    ABCD 4
    Very easy.

    A recursive solution would probably be even simpler, but I haven't tried so far.

    Je suis Charlie.
      Thanks Laurent, beginner lever is good for me. I actually worked in biology department, and learned Perl just for analyzing data generated from our Next generation sequencing project. I guess linked list will not be something I will use in my data analysis in near future since it seems quite complex to me..... Thanks a lot for your code,though!
        Hmm, linked lists are not that complicated, but it is a data structure that you almost never need in Perl (I don't think that I ever implemented one in Perl for actual work problem), because Perl's arrays and hashes are very versatile and provide easier solutions for most of the same types of problems (circular buffer, for example).

        If you look at the code I posted, it is really not very complicated.

        my $pt = { value => "D", next => undef };
        I am starting with the terminator, the last element of the linked list. Therefore, the next field is undefined and the value is "D". The $pt variable (for "pointer", but I should not use that terminology, it is a reference, not a pointer) is something that gives me access to the data structure. This reference will be used in the next code line:
        my $pt2 = {value => "C", next => $pt};
        There, I am saying that the value is "C", and that the next record is the one I just created before. And so on until the first element. Please feel free to ask if you don't understand.

        In lower level languages such as C or C++, linked lists are needed much more often and they are also often more difficult to implement.

        Je suis Charlie.
      Thanks for your explanation! So basically, it is just a data structure as hash of hashes or array of hash, right? Like in your example code, all scalar on the left are references. If I want to access the last element in the linked list, all I need to do is just keep deference it until the last one is reached, right? Something like $L->{'next'}->{'next'}->{'next'}->{'value'} right? ^_^
        Yes, more or less, it is basically a collection of anonymous hashes, each or which contains a reference to the next element in the collection (except of course the terminator in which the reference to the next element is not defined). It could also be implemented as a bunch of arrays in which, for example, the first element would be the value and the seccond one the reference to the next array.

        Je suis Charlie.