   (C++) Linked List Node Deletion Woes -- Solved
  Compiler: Dev-C++ 4.9.9.2OS: Win XP w/service pack 3Application: Console basedProgrammer: < 6 mos experienceI have been perplexed by a problem for days.  The jDeleteAfter member function of my linked list class should delete the node object after the node provided as an argument.  I do not know if it is even doing that, but it is causing my application to close abruptly when it executes.  I've narrowed the offending line of code down to "delete tlp;", but I suspect I have a logical error elsewhere that is the root of my problem.Any ideas?#include "JawaListT.h"#include <cstdlib>#include <iostream>#include <new.h>/*DEFAULT CONSTRUCTOR*/JawaListT::JawaListT(){if((this->jHead = new (nothrow) JawaLinkT) && (this->jTail = new (nothrow) JawaLinkT)){this->jHead->jSetNext(this->jTail);this->jTail->jSetNext(this->jTail);}//end if allocated}/*INSERT NODE AFTER*/void JawaListT::jInsertAfter(JawaLinkT* lp, int val){if(lp != this->jTail && lp != NULL)   //if passed not tail and not null{JawaLinkT* tlp;//new list nodeif((tlp = new (nothrow) JawaLinkT) != NULL)//if dynamically allocated{tlp->jSetNext(lp->jGetNext());  //temp.next = passed.nextlp->jSetNext(tlp);//passed.next = temptlp->jSetValue(val);//temp.data = val}//end if allocated}//end if not tail}/*INSERT NODE BEFORE*/void JawaListT::jInsertBefore(JawaLinkT* lp, int val){if(lp != this->jHead && lp != NULL)//if passed not head and not null{JawaLinkT* tlp;//new list nodeif((tlp = new (nothrow) JawaLinkT) != NULL)  //if dynamically allocated{*tlp = *lp;//copies passed node to temp nodelp->jSetNext(tlp);//passed.next = templp->jSetValue(val);//passed.data = valif(lp == this->jTail)//if passed is tail{this->jTail = tlp;//tail is tempthis->jTail->jSetNext(this->jTail);  //tail.next = tail}//end if lp}//end if tlp}//end if head}/*REMOVE NODE AFTER*/void JawaListT::jDeleteAfter(JawaLinkT* lp){if(lp->jGetNext() != this->jTail && lp != NULL)//if not tail and not null{JawaLinkT* tlp;//temp pointer to nodetlp = lp->jGetNext();//temp = passed.nextlp->jSetNext(tlp->jGetNext());//passed.next = temp.nextdelete tlp;//delete to what temp points}//end if next/*code that did not work any better*///tlp->jSetNext((lp->jGetNext())->jGetNext());//delete lp->jGetNext();//lp->jSetNext(tlp);/*Also tried declaring and/or deleting tlp outside of decision structure, andjDeleteCurrent(tlp) since that function works properly.*/}/*REMOVE CURRENT NODE*/void JawaListT::jDeleteCurrent(JawaLinkT* lp){if(lp != jHead && lp != jTail && lp != NULL)//if not head or tail, not null{JawaLinkT* tlp; //temp pointer to nodetlp = lp->jGetNext();//temp = passed.next*lp = *tlp;//copy temp to passedif(tlp == jTail)//if temp is tail{this->jSetTail(lp);//tail = passedlp->jSetNext(lp);//passed.next = passeddelete tlp;//delete to what temp points}//end if tail}//end if not head}/*LINEAR SENTINEL SEARCH*/JawaLinkT* JawaListT::jFindItemS(int item){JawaLinkT* tlp;//temp pointer to nodethis->jTail->jSetValue(item);//tail.data = itemfor(tlp = jHead->jGetNext(); tlp->jGetValue() != item; tlp = tlp->jGetNext());/*INIT: node after head, EXIT: data found, UPDATE: increment node*/if(tlp == jTail)//if sentinel foundstd::cout << item << " not in list" << std::endl;return((tlp != this->jTail->jGetNext()) ? tlp : NULL);/*If sentinel not found, return proper node, else return null*/} edited to update status to solved[Edited by - Uther Mortigast on May 30, 2009 9:57:59 PM]
  Unsure of the solution exactly, but my suspected culprit is the insertBefore method.It appears you are creating loops and breaking the linked list, If I am not mistaken, twice here.*tlp = *lp;//copies passed node to temp nodelp->jSetNext(tlp);//passed.next = templp->jSetValue(val);//passed.data = valif(lp == this->jTail)//if passed is tail{this->jTail = tlp;//tail is tempthis->jTail->jSetNext(this->jTail);  //tail.next = tail}//end if lpThe first line is throwing away the tlp u just dynamically allocated in the if statement previous to it, and the following line creates a loop by setting the next node of lp to itself! This is invariably going to cause problems! A similar thing is going on in the setting of jTail.Unless you have nodes keeping track of their previous node, inserting BEFORE a chosen node requires you to iterate through the list up to that node and link the previous node to the new node. Otherwise it isn't linked in. So, if your lists will be short and this iterating won't be a terrible performance hit, I would proceed that way, but if you plan to have very long lists, it would be wise to restructure your node objects to have a previous pointer, and be sure to add code that assigns this pointer correctly in your insert/delete methods.I'm happy to help in writing all this extra code if you find yourself confused, but I usually find I learn better if I try something first :) Let me know how it goes!-Will   ;Quote:Original post by Uther MortigastCompiler: Dev-C++ 4.9.9.2incidentally Dev-c++ is an IDE that uses the Mingw compiler.  It itself is not a compiler. Also Dev-c++ has been abandoned for several years, you may be interested in the free version of visual studio or WxDev-c++(a related project that is still being developed).   ;  Here's what I thought I was doing....myList.jInsertBefore(myList.jFindItemS(6), 9); //from mainjInsertBefore(JawaLinkT* lp, int val)JawaLinkT* tlp = new JawaLinkT;H| |  a|2|  b|4|  c|6|  T|6| |a|-> |b|-> |c|-> |T|-> |T|- ^\ _  tlp|0|   |0|*tlp = *lp;H| |  a|2|  b|4|  c|6|  T|6| |a|-> |b|-> |c|-> |T|-> |T|-^^  /  \ _tlp|6| / |T|/lp->jSetNext(tlp);H| |  a|2|  b|4|  c|6|  T|6| |a|-> |b|-> |c|-> |t|   |T|-    /l    ^^ / p   /  \ _    v    /  tlp|6| /|T|/lp->jSetValue(val);H| |  a|2|  b|4|  c|9|  T|6| |a|-> |b|-> |c|-> |t|   |T|-    /l    ^^ / p   /  \ _    v    /  tlp|6| /|T|/ Should I instead do tlp = lp to get my desired result?   The tail should be self-referential, so that's good.  And yes, I'm a little confused, but I am trying to learn by doing.  I'm just stumped on this mystery error in jDeleteAfter.  Thanks for the offer though, Will.   ;  Oh okay I kind of see what you're getting at, nice ASCII drawings there :) That isn't anything like what I've learned but I like the self referential Tail Pointer, that's an interesting idea for removing the danger of Null Pointer Exceptions.Anyways, though, the *tlp = *lp line is still going to cause you looping problems that break part off parts of the list, as you're letting go of the new node you create. A pseudo-code idea of what you wanna do would be something more like:Quote:Node * tlp = new Node; //Make the new node to link intlp->setNext(lp->getNext); tlp->setVal(lp->val);  // These lines make tlp the same as lp, as u desirelp->setVal(passed Value);lp->setNext(tlp);    // Now we overwrite the old lp with the new values // effectively inserting beforeNot sure if that quoting worked, anyone tell me how to do that proper?The key here is to just be copying the values and not making the pointers equal to each other. After this code, you can do your Tail setting logic and everything should be gravy.One thing that might help would be to write some test main code that runs these routines individually and write a print method that helps you see if each function is operating as you expect. That way it's easier to narrow down the problem :)Best of luck, come back with progress report/any more questions!-Will   ;Quote:Original post by WillBuckOh okay I kind of see what you're getting at, nice ASCII drawings there :) That isn't anything like what I've learned but I like the self referential Tail Pointer, that's an interesting idea for removing the danger of Null Pointer Exceptions.There are no "null pointer exceptions" in C++. What happens when you dereference a null pointer in C++ is undefined.Also, doing it this way may remove that danger, but it introduces the danger of unexpected infinite loops.Also, the entire project is useless; the standard library already provides a linked list.   ;  Zahlman -Quote:There are no "null pointer exceptions" in C++. What happens when you dereference a null pointer in C++ is undefined.Pardon my mistake, I was taught mostly in Java and default to that terminology sometimes. Point is it can cause problems, yes? ;)Quote:Also, doing it this way may remove that danger, but it introduces the danger of unexpected infinite loops.It's a danger, yes, but in my experience, checking if things like node->next are NULL causes more problems than here, where checking if next = current would more likely be safer. As long as you remember to do the check, you'd avoid the looping.Quote:Also, the entire project is useless; the standard library already provides a linked list.Now I'm new here and you're the moderator and I'm not, and I respect that I should show a great deal of humility. So, please pardon my objecting to the above statement, but why would learning something like this be useless? Sure, he could use the library for a linked list or hash table or whatever he needs for whatever project he's doing, and if he were on a deadline he'd be wise to do so, but how is learning to code something as crucial as data structures properly "useless"? That kind of wording seems a bit harsh and rude to me :/   ;if(lp->jGetNext() != this->jTail && lp != NULL)Without actually looking at the logic, this is most likely your culprit right here. You're checking to see if lp is not NULL *after* you dereference the pointer via ->GetNext(). If it is NULL, this will crash it. You should check if lp is NULL first, this way it will return false and not execute the second condition check.if( lp != NULL && lp->jGetNext() != this->jTail );  Alright, I've changed the the node shuffling so it uses the class accessors and mutators rather than indirect assignment.  I was just trying to get comfortable with pointers, but it's probably safer (and clearer) to do it the way you suggested, Will.  Sadly, I'm still getting the same error.I do have test code in main for each of my functions that evaluates valid and invalid arguments, that's how I discovered this problem, I just didn't include it here.  All of the methods except jDeleteAfter seem to work properly, (at least my toString method in a derived class displays what I expect to see) and that abruptly exits my application whether a valid or invalid node is passed.  Judicious use of system("PAUSE") indicates that it doesn't crash until "delete tlp;" gets read.Ookami, great idea on evaluating for != NULL first.  It didn't alleviate my current problem, but I'm sure that will prevent future ones.  I've adjusted all my code accordingly.Quote:Original post by ZahlmanAlso, the entire project is useless...Perhaps, but the exercise in creating my own linked list was not.   ;  It turned out to be a conflict with my destructor in my node class.  Thanks for your time and thoughts on my project.   