ring_dll.pl

package Ring::DoubleLinkedList;
use 5.16.1;
use Scalar::Util qw(looks_like_number);
use constant {
    PREV_NODE => 0,
    DATA_REF  => 1,
    NEXT_NODE => 2,
};

sub new {
    my ($class, $size)=@_;
    bless +{
        'size'      => (looks_like_number($size) and $size>0 and int($size)==$size) ? $size : die('You must specify the size of the list and it must be natural number'),
        'stackFree' => [reverse(0..($size-1))],
        'indexHead' => undef,
        'indexTail' => undef,
        'nodes'     => [],
    }, (ref($class) || $class)
}

sub add {
    my ($dl, $elPayLoad)=@_;
    if (@{$dl->{'stackFree'}}) {
        my $indexNewEl=pop($dl->{'stackFree'});
        # "Next" pointer of the head node will always point to undef
        # "Previous" pointer - to the index of the node which was the head before we add new element (and undef if there is only one element in the list)
        $dl->{'nodes'}[$indexNewEl] = [$dl->{'indexHead'}, \$elPayLoad, undef];
        if (defined $dl->{'indexHead'}) {
            $dl->{'nodes'}[$dl->{'indexHead'}][NEXT_NODE]=$indexNewEl
        } else {
            $dl->{'indexTail'}=$indexNewEl
        }
        $dl->{'indexHead'}=$indexNewEl
    } else {
        my $nodeOldTailNewHead=$dl->{'nodes'}[$dl->{'indexTail'}];
        $dl->{'indexHead'}=$dl->{'nodes'}[
            $nodeOldTailNewHead->[PREV_NODE]=$dl->{'indexHead'}
        ][NEXT_NODE]=$dl->{'indexTail'};

        $nodeOldTailNewHead->[DATA_REF]=\$elPayLoad;

        undef $dl->{'nodes'}[
            $dl->{'indexTail'}=$nodeOldTailNewHead->[NEXT_NODE]
        ][PREV_NODE];
        undef $nodeOldTailNewHead->[NEXT_NODE];
    }
}

sub del {
    my ($dl, $node)=@_;
    my ($prv, $nxt)=@{$node}[PREV_NODE,NEXT_NODE];
    my $indexSelf;
    if (defined $prv) {
        $indexSelf=$dl->{'nodes'}[$prv][NEXT_NODE];
        $dl->{'nodes'}[$prv][NEXT_NODE]=$nxt
    } else {
        $dl->{'indexTail'}=$nxt
    }

    if (defined $nxt) {
        $indexSelf=$dl->{'nodes'}[$nxt][PREV_NODE] unless defined $indexSelf;
        $dl->{'nodes'}[$nxt][PREV_NODE]=$prv
    } else {
        $dl->{'indexHead'}=$prv
    }
    if (defined $indexSelf) {
        push @{$dl->{'stackFree'}}, $indexSelf
    } else {
        $dl->reset
    }
    undef $node;
}

sub reset {
    @{$_[0]}{qw/stackFree nodes indexHead indexTail/}=(
        [reverse(0..$_[0]->{'size'})],  # stackFree ()<-
        [],                             # nodes ->()
        undef,                          # ->head
        undef                           # ->tail
    )
}

use Data::Dumper;
sub dump {
    my $dl=$_[0];
    print Dumper $dl;
    return unless defined $dl->{'indexTail'};
    my $node=$dl->{'nodes'}[$dl->{'indexTail'}];
    do {
        printf("<-(%s) || %s || (%s)->\n", $node->[PREV_NODE]//'nil', ${$node->[DATA_REF]}, $node->[NEXT_NODE]//'nil');
    } while defined($node->[NEXT_NODE]) and $node=$dl->{'nodes'}[$node->[NEXT_NODE]];
}

1;

package main;
print 'nElements='; my $n=<STDIN>; chomp;
my $rdll=Ring::DoubleLinkedList->new($n);
while (<STDIN>) {
    chomp;
    exit if $_ eq 'exit';
    $rdll->add($_);
    $rdll->dump;
}