Re^3: Perl linked list

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};
[download]

(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
[download]

Very easy.

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

Je suis Charlie.

Comment on Re^3: Perl linked list Select or Download Code

Replies are listed 'Best First'.
Re^4: Perl linked list by Perl_is_Perl (Initiate) on Mar 31, 2015 at 19:15 UTC
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!	[reply]
Re^5: Perl linked list by Laurent_R (Canon) on Mar 31, 2015 at 20:14 UTC
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 };` [download] 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};` [download] 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.	[reply] [d/l] [select]
Re^4: Perl linked list by Perl_is_Perl (Initiate) on Mar 31, 2015 at 21:09 UTC
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? ^_^	[reply]
Re^5: Perl linked list by Laurent_R (Canon) on Apr 01, 2015 at 07:23 UTC
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.	[reply]