#!/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].