commit 7361bc4f84c46d7fbc4b819328c0b5cab0592b1f
parent e437c5a63c42caa3c8617003fbabb7cd11242512
Author: Samir Parikh <noreply@samirparikh.com>
Date: Wed, 23 Nov 2022 16:07:55 +0000
add linked lists file
Diffstat:
| A | linked_lists.pl | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 67 insertions(+), 0 deletions(-)
diff --git a/linked_lists.pl b/linked_lists.pl
@@ -0,0 +1,67 @@
+#!/usr/local/bin/perl
+
+use strict;
+use warnings;
+use v5.32;
+
+# Taken from Chapter 3, "Advanced Data Structures", of "Mastering
+# Algorithms with Perl" by Jon Orwant, Jarkko Hietaniemi, and John Macdonald
+
+# the following code creates a linked list of the first 5 squares
+my $list = undef;
+foreach ( reverse 1 .. 5 ) {
+ $list = [ $list, $_ * $_ ];
+}
+# which is the same as doing:
+# $list = [[[[[undef,25],16],9],4],1];
+
+# Each element of the linked list is a list containing two scalars. The first
+# scalar, [0], is a reference that points to the next element of the linked
+# list. The second scalar, [1], holds a value: 1, 4, 9, 16, or 25. By following
+# the reference in each element, you can work your way to the end of the list.
+# So, $list->[0][0][1] has the value 9—we followed two links to get to the
+# third element, and then looked at the element.
+
+say "the first value is: ", $list->[1]; # 1
+say "the second value is: ", $list->[0][1]; # 4
+say "the third value is: ", $list->[0][0][1]; # 9
+say "the last value is: ", $list->[0][0][0][0][1]; # 25
+
+# add some constants to improve readablity
+use constant NEXT => 0;
+use constant VAL => 1;
+
+# subroutine to print all values of linked list in sequential order
+sub print_linked_list {
+ say "------------------";
+ my $list = shift;
+ say $list->[ VAL ]; # value of first element
+ my $next = $list->[ NEXT ]; # link to second element
+ while ( defined $next ) { # if link to next element exists
+ say $next->[ VAL ]; # print the value
+ $next = $next->[ NEXT ]; # get link to next element
+ }
+ say "------------------";
+}
+
+print_linked_list( $list );
+
+## move some elements around
+my $four = $list->[ NEXT ]; # link, or pointer to what comes after the first
+ # element (4)
+my $nine = $four->[ NEXT ]; # link, or pointer to what comes after 4 (9)
+my $sixteen = $nine->[ NEXT ]; # link, or pointer to what comes after 9 (16)
+
+# just to confirm:
+foreach ( $four, $nine, $sixteen ) {
+ say $_->[ VAL ];
+}
+
+$nine->[ NEXT ] = $sixteen->[ NEXT ]; # the link from 9 now points to whatever
+ # 16 was pointing to (25)
+$sixteen->[ NEXT ] = $nine; # the link from 16 now points to 9
+$four->[ NEXT ] = $sixteen; # the link form 4 points to 16
+
+# final order should now be 1, 4, 16, 9, 25:
+print_linked_list( $list );
+# as $list is now equal to [[[[[undef,25],9],16],4],1].
