|
Perl_is_Perl has asked for the wisdom of the Perl Monks concerning the following question:
Dose anyone know how to count nodes numbers in a linked list or could anyone tell me which book should I start with to learn about linked list? Thanks a lot !
The question is from codility.com, which I use it to evaluate my coding ability recently. Due to the copyright problem, I need to remove it from here, My bad ! please check the original qestion below:
https://codility.com/honeypot/Perl_is_Perls-Perl-test-1
Here comes the codes I come up with, thanks for all your explanation of linked list data structure :
sub solution
{
my ($L)=@_;
my $count=1;
while($L=$L->{'next'})
{
$count++;
last if $L->{'value'} eq 'undef';
}
return $count;
} |
Re: Nodes count in Linked List
by Corion (Patriarch) on Mar 31, 2015 at 12:46 UTC
|
The easiest approach would be to review your course material for hints about how to do so.
The second easiest approach is to do this manually for the given example and then encode each step that you do manually into a program.
Maybe the following observations help you analyze the steps to find the length of a linked list:
- Each list is finite, that is, it has finitely many nodes and no node is referenced more than once by any next entry.
- The length of the empty list is zero.
- The length of a list that is not empty is one larger than the length of the list in the next entry.
| [reply]
[d/l]
[select] |
|
|
Thanks for your kindly help!
The thing confuses me is what exact data type $L is in the given question?
The test data set would be something like [ 3,2,2,3,3,3,1 ]. I don't understand how the data set get passed into @_ and assigned to $L. [ 3,2,2,3,3,3,1 ] seems like an anonymous array to me if assigned to a $scalar . Could you tell me how it assigned to @_ and $L ?
| [reply] |
|
|
In common with others, I'm not sure how this question relates to your OP ([ 3,2,2,3,3,3,1 ] doesn't look like a linked list to me, either), but I can answer your specific questions.
... what exact data type [is] $L ...
$L is a scalar. This is determined by the $ sigil before the symbol.
... how [does] the data set get passed into @_ and assigned to $L.
The expression [ 3,2,2,3,3,3,1 ] returns a reference (to an array). A reference is always a scalar value even though the referent, e.g., an array or hash, is not. A scalar is passed to a subroutine in the usual way:
c:\@Work\Perl>perl -wMstrict -le
"my $arrayref = [ 3,2,2,3,3,3,1 ];
;;
sub func {
my ($msg, $ar) = @_;
;;
printf qq{$msg: scalar ref: $ar };
printf qq{'$_' } for @$ar;
printf qq{(%d elements) \n}, scalar @$ar;
}
;;
func('A', [ 9, 8, 7 ]);
func('B', $arrayref);
"
A: scalar ref: ARRAY(0x1cb226c) '9' '8' '7' (3 elements)
B: scalar ref: ARRAY(0x6fd05c) '3' '2' '2' '3' '3' '3' '1' (7 elements
+)
Update: Changed code example: added element count. Slight wording change.
Give a man a fish: <%-(-(-(-<
| [reply]
[d/l]
[select] |
|
|
What you show as test data seems to contradict what your assignment says what the test data would be.
Maybe you can review the assignment description and visualize the data as it is described. Note that a "dictionary" is not an "anonymous array".
| [reply] |
|
|
[ 3,[2,[2,[3,[3,[3,[1, undef ]]]]]]]].
But I fear the author if this assignment just lazily copied a task from Lisp and has no big idea what Perl is.
| [reply]
[d/l] |
|
|
|
|
Re: Nodes count in Linked List
by LanX (Saint) on Mar 31, 2015 at 13:16 UTC
|
MJD shows an implementation of linked lists in Higher Order Perl
which looks quite convincing (though costly)
Each node is a two element array [value,tail_ref] with tail_ref being an array ref to the next node or undef.
To count length iterate through the list till you get undef.
Perl has no built in linked lists b/c arrays cover almost all use cases.
| [reply]
[d/l] |
Re: Perl linked list
by Laurent_R (Canon) on Mar 31, 2015 at 17:37 UTC
|
With the material removed, it is now impossible to help the original poster.
Not sure it would be a good idea to help him anyway, since the link provided in the OP (which I copy here to make sure that it does not also disappear from the OP: https://codility.com/honeypot/Perl_is_Perls-Perl-test-1 seems to indicate it is a test for admission to the South Dakota State University.
| [reply] |
|
|
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
| [reply] |
|
|
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?
| [reply]
[d/l]
[select] |
|
|
|
|
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.
| [reply]
[d/l]
[select] |
|
|
|
|
|
|
|
|
Re: Perl linked list (reasonable updates)
by LanX (Saint) on Mar 31, 2015 at 15:13 UTC
|
Please don't delete information in updates to your posts.
The thread is referencing you using the word "dictionary", but this information disappeared now.
You can use <strike> to disable invalid information, without damaging the thread.
| [reply]
[d/l] |
|
|
Further to LanX's post: Perl_is_Perl: I would also ask that you please restore, insofar as you can, what you have deleted or, if this is quite impossible, beg the janitors' help. Thank you very much!
Give a man a fish: <%-(-(-(-<
| [reply]
[d/l] |
|
|
The OP mentioned in his revised post that this was due to a copyright concern, rather than being invalid.
| [reply] |
Re: Perl linked list
by Laurent_R (Canon) on Apr 01, 2015 at 17:55 UTC
|
As promised yesterday, this is my code to create a linked list and count its nodes:
use strict;
use warnings;
use Data::Dumper;
my $pt = { value => "D", next => undef };
my $pt2 = {value => "C", next => $pt};
$pt = {value => "B", next => $pt2};
my $L = { value => "A", next => $pt};
sub solution {
my $list = shift;
my $length = 0;
while (1) {
return $length unless defined $list->{value}; # added for the
+case of an empty list
print $list->{value};
$length++;
return $length unless defined $list->{next};
$list = $list->{next};
}
}
my $len = solution($L);
print "\n$len \n";
print Dumper $L;
Which finds 4 nodes and prints this:
ABCD
4
$VAR1 = {
'next' => {
'next' => {
'next' => {
'next' => undef,
'value' => 'D'
},
'value' => 'C'
},
'value' => 'B'
},
'value' => 'A'
};
As I said yesterday, the initialization of the list could be simpler, but perhaps less easy to understand for a relative beginner. But this is how I would probably code the initialization of the linked list:
my $L = {
value => "A", next => {
value => "B", next => {
value => "C", next => {
value => "D", next => undef,
}
}
}
};
Or, better (especially if there are more nodes), I would construct it in a loop:
my $L;
for ( reverse qw / A B C D E F G/) {
my $pt = { value => $_, next => $L };
$L = $pt;
}
Which prints:
$ perl linked_list.pl
ABCDEFG
7
$VAR1 = {
'next' => {
'next' => {
'next' => {
'next' => {
'next' => {
+'next' => {
+ 'next' => undef,
+ 'value' => 'G'
+ },
+'value' => 'F'
},
'value' => '
+E'
},
'value' => 'D'
},
'value' => 'C'
},
'value' => 'B'
},
'value' => 'A'
};
| [reply]
[d/l]
[select] |
Re: Perl linked list
by LanX (Saint) on Apr 01, 2015 at 13:57 UTC
|
(and another unflagged update, please consider just replying to your initial post ... and please use code tags)
> Here comes the codes I come up with,
Which is double buggy, test next not value with defined not eq "undef" (data structure here).
Well triple, empty list aren't covered.
Consider a recursive solution.
| [reply]
[d/l]
[select] |
|
|
Consider a recursive solution.
Meh. Consider writing one, maybe, for fun and edification.
For production code, consider using iterators.
| [reply] |
Re: Perl linked list
by sundialsvc4 (Abbot) on Apr 01, 2015 at 12:58 UTC
|
As others have said, this entire scenario is very hypothetical. If you want to have “a list of <<whatever>>” in Perl, you don’t have to do it yourself. The Perl interpreter already provides “a list,” as well as hash-tables, as an intrinsic language feature. It also provides a sophisticated memory manager to make your memory calesthenics relatively painless.
Perl’s “references” feature also makes it possible to home-grow your own lists, or trees, or any other data structure you might have just pulled from your college textbook. But, there is a catch. It is easy to create circular references, which defeat the purpose of the built-in memory manager unless you know about, and properly account for, “weakened references.”
Finally, although Perl does offer the facilities needed to “homebrew” your own data structures from scratch, the CPAN library offers a cornucopia of data-structure modules which you can simply grab “off the shelf” and use, without having to write anything at all yourself. Since every one of them will be thoroughly tested (on your system) before they will consent to let themselves be installed, you can use them with confidence.
| |
|
|
| [reply] |
|
|
