CODEWITHSUNDEEP
perllinked-list
Amey
Amey

Reputation: 8548

Reverse a linked list in perl

So I know that there are hundred examples on Stack overflow, and in fact i have used all the information from there - so this is what i have 

use strict;
use warnings;
use Data::Dumper;

my $head= undef;
my $tail=\$head;

open FILE, "<datastored.txt" or die $!;

while (<FILE>){
    my $node = {
                "data" => $_ , 
                "next" => undef
            };
    $$tail=$node; 
    $tail = \$node->{"next"}; 
};
print Dumper $head; #before reversing
$head = reverse_list($head);
print Dumper $head; #after reversing
sub reverse_list{
    my ($list) =@_[0];
    my $previous = undef;
    while ($list->{next}){
        $forward = $list->{next}; 
        $list->{next}= $previous; 
        $previous = $list; 
        $list=$forward; 
    };
    return $previous;   
};

and this is the output I get

#this is the output before reversing (normal linked list)
$VAR1 = {
          'next' => {
                      'next' => {
                                  'next' => {
                                              'next' => undef,
                                              'data' => 'line 4
'
                                            },
                                  'data' => 'line 3
'
                                },
                      'data' => 'line 2
'
                    },
          'data' => 'line 1
'
        };
#this is the linked list after reversing (WITHOUT THE LAST DATA VARIABLE - "line 4")
$VAR1 = {
          'next' => {
                      'next' => {
                                  'next' => undef,
                                  'data' => 'line 1
'
                                },
                      'data' => 'line 2
'
                    },
          'data' => 'line 3
'
        };

Note - the content of the file datastored.txt is simply

line 1
line 2
line 3
line 4

So my question is where is the data "line 4" gone and what should i change to ACTUALLY reverse the linked list without losing any value.

Upvotes: 1

Views: 1302

Answers (1)

dirkgently
dirkgently

Reputation: 111150

Your reversal sub-routine is almost correct. However, it misses the last entry (i.e. adding it in the final reversed list) because of the condition you are using. You have two options:

  1. Change the while ($list->{next}) to while ($list) and make the code more idiomatic.

  2. Add a $list->{next}= $previous; after the end of the while loop to add back the last remaining node to your reversed list. (Think of a list of two elements and see what your code does).

Upvotes: 3

Related Questions