Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Linked List

by code-ninja (Scribe)
on Sep 04, 2013 at 06:19 UTC ( #1052219=perlquestion: print w/ replies, xml ) Need Help??
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]; }
The insertion works perfectly. The output is as follows:
1 4 9 16 25
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
where am I going wrong?

Comment on Linked List
Select or Download Code
Re: Linked List
by Ratazong (Prior) 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) {
    and if it isn't, you move to the next element:
    $temp = $temp->[NEXT];
    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

      perfect. That was a stupid mistake. :/
      ... } else { $temp = $temp->[NEXT]; $pred = $pred->[NEXT]; # this is what you are saying. } ...
Re: Linked List
by RichardK (Priest) 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]; }

    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 ;)

      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 ;)
      Only the leftmost dereference arrow is mandatory:
      while ( defined $curr ) { if ($curr->[NEXT][VALUE] == $value) { $curr->[NEXT] = $curr->[NEXT][NEXT]; } else { $curr = $curr->[NEXT]; }
      لսႽ ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1052219]
Approved by Happy-the-monk
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (11)
As of 2014-07-22 21:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (129 votes), past polls