in reply to Re: Doubly link list implementation
in thread Doubly link list implementation

Hello, Thanks so much for the help. I was trying to study doubly linked list and was struggling with its understanding. Thanks again.

Replies are listed 'Best First'.
Re^3: Doubly link list implementation
by punitpawar (Sexton) on Nov 25, 2015 at 19:04 UTC
    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]

In Section Seekers of Perl Wisdom