linked_lists.pl (2507B) - raw
1 #!/usr/local/bin/perl 2 3 use strict; 4 use warnings; 5 use v5.32; 6 7 # Taken from Chapter 3, "Advanced Data Structures", of "Mastering 8 # Algorithms with Perl" by Jon Orwant, Jarkko Hietaniemi, and John Macdonald 9 10 # the following code creates a linked list of the first 5 squares 11 my $list = undef; 12 foreach ( reverse 1 .. 5 ) { 13 $list = [ $list, $_ * $_ ]; 14 } 15 # which is the same as doing: 16 # $list = [[[[[undef,25],16],9],4],1]; 17 18 # Each element of the linked list is a list containing two scalars. The first 19 # scalar, [0], is a reference that points to the next element of the linked 20 # list. The second scalar, [1], holds a value: 1, 4, 9, 16, or 25. By following 21 # the reference in each element, you can work your way to the end of the list. 22 # So, $list->[0][0][1] has the value 9—we followed two links to get to the 23 # third element, and then looked at the element. 24 25 say "the first value is: ", $list->[1]; # 1 26 say "the second value is: ", $list->[0][1]; # 4 27 say "the third value is: ", $list->[0][0][1]; # 9 28 say "the last value is: ", $list->[0][0][0][0][1]; # 25 29 30 # add some constants to improve readablity 31 use constant NEXT => 0; 32 use constant VAL => 1; 33 34 # subroutine to print all values of linked list in sequential order 35 sub print_linked_list { 36 say "------------------"; 37 my $list = shift; 38 say $list->[ VAL ]; # value of first element 39 my $next = $list->[ NEXT ]; # link to second element 40 while ( defined $next ) { # if link to next element exists 41 say $next->[ VAL ]; # print the value 42 $next = $next->[ NEXT ]; # get link to next element 43 } 44 say "------------------"; 45 } 46 47 print_linked_list( $list ); 48 49 ## move some elements around 50 my $four = $list->[ NEXT ]; # link, or pointer to what comes after the first 51 # element (4) 52 my $nine = $four->[ NEXT ]; # link, or pointer to what comes after 4 (9) 53 my $sixteen = $nine->[ NEXT ]; # link, or pointer to what comes after 9 (16) 54 55 # just to confirm: 56 foreach ( $four, $nine, $sixteen ) { 57 say $_->[ VAL ]; 58 } 59 60 $nine->[ NEXT ] = $sixteen->[ NEXT ]; # the link from 9 now points to whatever 61 # 16 was pointing to (25) 62 $sixteen->[ NEXT ] = $nine; # the link from 16 now points to 9 63 $four->[ NEXT ] = $sixteen; # the link form 4 points to 16 64 65 # final order should now be 1, 4, 16, 9, 25: 66 print_linked_list( $list ); 67 # as $list is now equal to [[[[[undef,25],9],16],4],1].