http://www.perlmonks.org?node_id=1052219

code-ninja has asked for the wisdom of the Perl Monks concerning the following question:

I'm sure that I'm making a very novice mistake. 
#!/usr/bin/perl

use strict;
use warnings;
use constant NEXT => 0;
use constant VAL => 1;

my ($list, $tail);
my($pred, $temp);
$list = $tail = undef;

# insertion. A linked queue.

foreach (1 .. 5) {
    my $node = [undef, $_ * $_];
    if(not defined $tail) {
        $list = $tail = $node;
    } else {
        $tail->[NEXT] = $node;
        $tail = $node;
    }
}
$temp = $list;

# print the values in the list.

while (defined $temp) {
    print $temp->[VAL], "\n";
    $temp = $temp->[NEXT];
}

# deletion

print "Enter element to be destroyed\n";
my $ele = <>;
chomp $ele;
$pred = $list;
$temp = $list->[NEXT];

while (defined $temp) {
    if($temp->[VAL] == $ele) {
        $pred->[NEXT] = $temp->[NEXT];
        print "$temp->[VAL] found!\n";
        $temp->[NEXT] = undef;
        last;
    } else {
        $temp = $temp->[NEXT];
    }
}

print "list after deleting $ele\n";

while (defined $list) {
    print $list->[VAL], "\n";
    $list = $list->[NEXT];
}

[download]
The insertion works perfectly. The output is as follows: 
1
4
9
16
25

[download]
now when I delete an element, I entered 4 and the output was the same minus 4. But when I delete 16, the output is: 
1
25

[download]
where am I going wrong?

Replies are listed 'Best First'.
Re: Linked List
by Ratazong (Monsignor) on Sep 04, 2013 at 06:51 UTC

    Hi code-ninja!

    When you pass through the list you check if the current element is the one you want to remove: 

    if($temp->[VAL] == $ele) {

    [download]
    and if it isn't, you move to the next element: 
    $temp = $temp->[NEXT];

    [download]
    However the pred-Element still stays the first one ... so when you remove the 16, you would link the 25 directly after the 1. You will need to adjust pred also.

    note: your code also needs some adjustment if you want the possibility to delete the first element.

    HTH, Rata

[reply]
[d/l]
[select]
      perfect. That was a stupid mistake. :/ 
      ...

} else {
    $temp = $temp->[NEXT];
    $pred = $pred->[NEXT]; # this is what you are saying.
}

...

      [download]
[reply]
[d/l]
Re: Linked List
by RichardK (Parson) on Sep 04, 2013 at 08:42 UTC

    You could remove the need for the $pred variable altogether, if you work with a little more indirection. So something along these lines :- 

    
while ( defined $curr ) {
    if ($curr->[NEXT]->[VALUE] == $value) {
        $curr->[NEXT] = $curr->[NEXT]->[NEXT];
    } else {
        $curr = $curr->[NEXT];
}

    [download]

    You'll have to think about what happens at the start and end of your list.

    The next thing to do is to write a sort by insertion routine ;)

[reply]
[d/l]
      Only the leftmost dereference arrow is mandatory: 
      while ( defined $curr ) {
    if ($curr->[NEXT][VALUE] == $value) {
        $curr->[NEXT] = $curr->[NEXT][NEXT];
    } else {
        $curr = $curr->[NEXT];
}

      [download]
      لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ
[reply]
[d/l]
      Working on it! Insertion sort and all.

      well, to be frank enough, I find Perl's syntax a bit more cryptic than C (though that might be because I've mostly programmed in C throughout my academic life). I'm using this book but it assumes that you are Perl samurai if not a ninja (or a Jedi) if you get what I mean. :/

      but whatever, I learn better (with a steep learning curve) by doing... so I'll soon be asking doubts about insertion sorting ;)
[reply]

Back to Seekers of Perl Wisdom