How to create a circular linked list in Perl without using arrays?-CodePudding

I've been assigned a task to create a circular linked list in Perl with given arguments, without using arrays or hashes to store the data, only using references. It should also support the traversal of the current chosen element using '-' and ' '. So the result should be like this:

./task.pl 3 2 1
3 2 1
./task.pl A D - B C   E
A B C D E
./task.pl A - B
B A

The current code I came up with is :

#!/usr/bin/perl

use strict;
use warnings;

my @elements = @ARGV;

my ($first, $last);
$first = { value => '0', 'prev' => $first, 'next' => $first };

my $pointer = \$first;

for (@elements) {
    if ($_ == '-') {

    } elsif ($_ == ' ') {

    } else {
        $_ = $pointer->{'next'};
        $_ = { value => "$_", 'prev' => $pointer, 'next' => undef};
        $pointer = \$_;
        $last = $_;
    }
}

I am not sure how to proceed further with this, also no imports like Class::Struct can be used.

CodePudding user response：

First of all, you are using a hash. {} creates a hash and returns a reference to it. THIS IS CORRECT. The hash is being used as a struct/class, which isn't what the assignment wants you to avoid.

Secondly, you have $first and $last and a bogus initial element. All of that is wrong. You just need my my $pointer;, although I would call it my $current;.

Thirdly, you use references to scalars (\$var). This is not useful here. The references to the hashes returned by {} are sufficient.

On to the code. There are three different components: Inserting the first element, and -, insertions, and printing the list that was built.

Inserting the first element

The first argument is special. It can't be and -. Other insertions always insert after another element, but that's not the case for the first insertion.

In short, we create a list that consists entirely of a node whose value is the first element.

We used undef to indicate a non-existent node.

my $pointer = { value => shift(@elements), prev => undef, next => undef };

and -

and - change the current node (as indicated by $pointer).

If is received, you want $pointer to the point to the node to which the current node's prev field points.

If - is received, you want $pointer to the point to the node to which the current node's prev field points.

You always have to ask yourself if there's a special cases, and there is one for each of and -. There could be an attempt to reach a node before the first (A - -), and there could be an attempt to reach a node after the last (A ). You should die if an attempt is made to reach a non-existent node.

Insertions

We always insert after the current node (the one $pointer references).

Again we ask ourselvves if there's a special case (like trying to use - when already at the first node). But there are none. $pointer will always point to a valid node.

After inserting a node in the list, we want to make $pointer reference the newly created/inserted node.

Printing the list

We want to print the entire list from start to end, so we will need to start by finding the start of the list. This is the same operation as - applied repeatedly until the first node is found. (The first node is the one which has no previous node.)

Then, it's just a question of traversing the list in the other direction (like does), printing the values as you go along.