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 (Vicar) 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 rifling through the Monastery: (7)
As of 2015-07-03 06:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (48 votes), past polls