in reply to Doubly link list implementation

As aptly said by BrowserUk and other monks, it is almost never necessary to use linked lists in Perl. And, as illustrated by GotToBTru, a simple array can do it just as well in Perl (because it is so easy in Perl to add or remove items anywhere in the array).

However, this is your code quickly modified to make a doubly-linkled list in the old fashion (I leave out the tail as an exercise): 

#!/usr/bin/perl

use strict;
use warnings;

my $head = {data => 0, prev => undef, next => undef};
my $previous = $head;

while (<DATA>){
    chomp;
    $previous->{next} = {
                "data" => $_ , 
                "next" => undef,
                "prev" => $previous,
            };
    $previous = $previous->{next};
}

my $curr = $head;
while (1) {
    last unless defined $curr->{next};
    print "Current: ", $curr->{data}, 
          "\tPrevious: ", $curr->{prev}{data} // "", 
          "\tNext: ", $curr->{next}{data} // "", "\n";
    $curr = $curr->{next};
}

__DATA__
1
2
3
4
5

[download]
This prints the values of the items in the list: 
$ perl  doubly_linked.pl
Current: 0      Previous:       Next: 1
Current: 1      Previous: 0     Next: 2
Current: 2      Previous: 1     Next: 3
Current: 3      Previous: 2     Next: 4
Current: 4      Previous: 3     Next: 5

[download]
And this is a Data Dumper view of the structure: 
$VAR1 = {
          'next' => {
                      'next' => {
                                  'next' => {
                                              'next' => {
                                                          'next' => {
                                                                      
+'next' => undef,
                                                                      
+'prev' => $VAR1->{'next'}{'next'}{'next'}{'next'},
                                                                      
+'data' => '5'
                                                                    },
                                                          'prev' => $V
+AR1->{'next'}{'next'}{'next'},
                                                          'data' => '4
+'
                                                        },
                                              'prev' => $VAR1->{'next'
+}{'next'},
                                              'data' => '3'
                                            },
                                  'prev' => $VAR1->{'next'},
                                  'data' => '2'
                                },
                      'prev' => $VAR1,
                      'data' => '1'
                    },
          'prev' => undef,
          'data' => 0
        };

[download]

Replies are listed 'Best First'.
Re^2: Doubly link list implementation
by punitpawar (Sexton) on Nov 25, 2015 at 02:26 UTC
    Hello, Thanks so much for the help. I was trying to study doubly linked list and was struggling with its understanding. Thanks again.
[reply]
      Hello, I do have a follow up question regarding node insertion in doubly linked list. so my intent is to insert a node after the head node and before the last node.
      Although I am able to do the insert correctly , when I try to print the output starting from the head . I do not see node that I had inserted before the tail node.
      Similarly when I print the output starting from the tail node , I do not see node that I inserted after the head node.

      Observe the values printed in the "current" field from my output.

      Any corrections/ suggestions which you can provide will be very helpful

      here is my code 
      
#!/usr/bin/perl

use strict;
use warnings;

my $head = {data => 0, prev => undef, next => undef};
my $previous = $head;

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

while (<FILE>){
    chomp;
    $previous->{next} = {
                "data" => $_ , 
                "next" => undef,
                "prev" => $previous,
            };
    $previous = $previous->{next};
    
}

### Inserting element at the beginning of the list after the head node
my $curr = $head;
$curr->{next}= {
                 "data" => 30, 
                "next" => $curr->{next},
                "prev" => $curr,    
};


### Inserting element at the end of the list before the tail node
$curr = $previous;
$curr->{prev}= {
                 "data" => 40, 
                "next" => $curr,
                "prev" => $curr->{prev},    
};


## Printing from head
print "printing from head \n";

 $curr = $head;
while (1) {
    last unless defined $curr->{next};
    print "Current: ", $curr->{data}, 
          "\tPrevious: ", $curr->{prev}{data} // "", 
          "\tNext: ", $curr->{next}{data} // "", "\n";
    $curr = $curr->{next};
}


## printing from tail


print "Printing From tail \n";

while (1) {
    last unless defined $curr->{prev};
    print "Current: ", $curr->{data}, 
          "\tPrevious: ", $curr->{prev}{data} // "", 
          "\tNext: ", $curr->{next}{data} // "", "\n";
    $curr = $curr->{prev};
}

      [download]
      Output form this program 
      
printing from head 
Current: 0    Previous:     Next: 30
Current: 30    Previous: 0    Next: line1
Current: line1    Previous: 0    Next: line2
Current: line2    Previous: line1    Next: line3
Current: line3    Previous: line2    Next: line4
Current: line4    Previous: line3    Next: line5


Printing From tail 
Current: line5    Previous: 40    Next: 
Current: 40    Previous: line4    Next: line5
Current: line4    Previous: line3    Next: line5
Current: line3    Previous: line2    Next: line4
Current: line2    Previous: line1    Next: line3
Current: line1    Previous: 0    Next: line2
Current: 0    Previous:     Next: 30

      [download]
      content of datastored.txt 
      line1
line2
line3
line4
line5

      [download]
[reply]
[d/l]
[select]
        Hi punitpawar,

        It seems that you've found a solution by now, but if you really want to build a doubly-linked list, you should most probably create separate subs to insert new nodes (and also subs to delete nodes).

        Subs to insert nodes could go like this: 

        sub insert_after {
    my ($previous, $val) = @_;
    my $curr_next = $previous->{next};
    $previous->{next} = {
                "data" => $val , 
                "next" => $curr_next,
                "prev" => $previous,
            };
    my $new_next = $previous->{next};
    $curr_next->{prev} = $new_next if defined $curr_next;
    return $new_next;
}    

sub insert_before {
    # simply call insert_after on the previous node
    my ($previous, $val) = @_;
    return insert_after($previous->{prev}, $val);
}

        [download]
        While we are at it, I think we should also move the displaying of the content into a separate sub: 
        sub display {
    my $curr = shift;
    while (1) {
        last unless defined $curr->{next};
        print "Current: ", $curr->{data}, 
              "\tPrevious: ", $curr->{prev}{data} // "", 
              "\tNext: ", $curr->{next}{data} // "", "\n";
        $curr = $curr->{next};
    }
    print "\n";
}

        [download]
        I now change the program of my previous post to add two nodes after the original construction of the data structure, and display the structure before and after these insertions: 
        my $head = {data => 0, prev => undef, next => undef};
my $previous = $head;

while (<DATA>){
    # ... same as in previous post
}

display($head);
my $new_node = insert_after ($head, 0.5);
$new_node = insert_before ($new_node->{next}, 0.7);
display($head);

        [download]
        This prints out the following: 
        $ perl  doubly_linked.pl
Current: 0      Previous:       Next: 1
Current: 1      Previous: 0     Next: 2
Current: 2      Previous: 1     Next: 3
Current: 3      Previous: 2     Next: 4
Current: 4      Previous: 3     Next: 5

Current: 0      Previous:       Next: 0.5
Current: 0.5    Previous: 0     Next: 0.7
Current: 0.7    Previous: 0.5   Next: 1
Current: 1      Previous: 0.7   Next: 2
Current: 2      Previous: 1     Next: 3
Current: 3      Previous: 2     Next: 4
Current: 4      Previous: 3     Next: 5

        [download]
        But, there is more to it.

        Read more... (2 kB)
        I hope this helps.
[reply]
[d/l]
[select]
        Ok I was able to get the solution. I was doing a dumb mistake.
        I never created the link backward from the newly added node.
        Again thanks everyone for your responses and help


        See my revised code below . 
        
#!/usr/bin/perl

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

my $head = {data => 0, prev => undef, next => undef};
my $previous = $head;

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

while (<FILE>){
    chomp;
    $previous->{next} = {
                "data" => $_ ,
                "next" => undef,
                "prev" => $previous,
            };
    $previous = $previous->{next};

}

### Inserting element after the head node
my $curr = $head;
$curr->{next}= {
                 "data" => 30, 
                "next" => $curr->{next},
                "prev" => $curr,
};

$curr->{next}{next}{prev}=$curr->{next};

#
# Inserting element before the tail node
 $curr = $previous;
 $curr->{prev}= {
                 "data" => 40, 
                "next" => $curr,
                "prev" => $curr->{prev},
};

$curr->{prev}{prev}{next}=$curr->{prev};

## Printing from head
print "printing from head \n";

print Dumper($head);


 $curr = $head;
while (1) {
    last unless defined $curr->{next};
    print "Current: ", $curr->{data},
          "\tPrevious: ", $curr->{prev}{data} // "",
          "\tNext: ", $curr->{next}{data} // "", "\n";
    $curr = $curr->{next};
}


## printing from tail


print "\n Printing From tail \n";

while (1) {
    last unless defined $curr->{prev};
    print "Current: ", $curr->{data}, 
          "\tPrevious: ", $curr->{prev}{data} // "",
          "\tNext: ", $curr->{next}{data} // "", "\n";
    $curr = $curr->{prev};
}

        [download]
        Output 
        
punit:Desktop punitpawar$ perl test1.pl 
printing Dumper 
$VAR1 = {
          'data' => 0,
          'prev' => undef,
          'next' => {
                      'prev' => $VAR1,
                      'next' => {
                                  'next' => {
                                              'data' => 'line 2',
                                              'next' => {
                                                          'next' => {
                                                                      
+'prev' => $VAR1->{'next'}{'next'}{'next'}{'next'},
                                                                      
+'next' => {
                                                                      
+            'data' => 'line 4',
                                                                      
+            'next' => undef,
                                                                      
+            'prev' => $VAR1->{'next'}{'next'}{'next'}{'next'}{'next'}
                                                                      
+          },
                                                                      
+'data' => 40
                                                                    },
                                                          'prev' => $V
+AR1->{'next'}{'next'}{'next'},
                                                          'data' => 'l
+ine 3'
                                                        },
                                              'prev' => $VAR1->{'next'
+}{'next'}
                                            },
                                  'prev' => $VAR1->{'next'},
                                  'data' => 'line 1'
                                },
                      'data' => 30
                    }
        };



 printing from head 
Current: 0    Previous:     Next: 30
Current: 30    Previous: 0    Next: line 1
Current: line 1    Previous: 30    Next: line 2
Current: line 2    Previous: line 1    Next: line 3
Current: line 3    Previous: line 2    Next: 40
Current: 40    Previous: line 3    Next: line 4

 Printing From tail 
Current: line 4    Previous: 40    Next: 
Current: 40    Previous: line 3    Next: line 4
Current: line 3    Previous: line 2    Next: 40
Current: line 2    Previous: line 1    Next: line 3
Current: line 1    Previous: 30    Next: line 2
Current: 30    Previous: 0    Next: line 1
Current: 0    Previous:     Next: 30

        [download]
        Content of datastored.txt 
        line1
line2
line3
line4

        [download]
[reply]
[d/l]
[select]
Re^2: Doubly link list implementation
by punitpawar (Sexton) on Nov 25, 2015 at 02:26 UTC
    Hello, Thanks so much for the help. I was trying to study doubly linked list and was struggling with its understanding. Thanks again.
[reply]

In Section Seekers of Perl Wisdom