#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0

    Removing from a doubly linked list


    When i remove a winery i get garbage output when i list the remaining wineries. I have been banging my head against the wall trying to figure this out, probably need a fresh set of eyes.
    Code:
    bool list::remove(const char* name)
    {
    	node* ptr = headByName;
    	
    	while (ptr) {
    		
    		if(strcmp(ptr->item.getName(),name) == 0) {
    			node* temp = headByName;
    			node* previous = headByName;
    			node* next = NULL;
    
    			while (temp != ptr && temp->nextByName != NULL) {//while they are both not the head and the next node isnt null
    				previous = temp;
    				temp = temp->nextByName;
    			}
    			if(temp == headByName)
    				headByName = headByName->nextByName;
    			else
    			if (previous == headByName)
    				headByName->nextByName = temp->nextByName;
    			else {
    				next = ptr->nextByName;
    				previous->nextByName = next;
    			}
    
    			
    			temp = headByRating;
    			previous = headByRating;
    			
    			while (temp != ptr ) {
    			previous = temp;
    			temp = temp->nextByRating;
    			}
    
    			if (previous == headByRating)
    			headByRating = previous->nextByRating;
    			else {
    			next = ptr->nextByRating;
    			previous->nextByRating = next;
    			}
    
    			delete ptr;
    			return true;
    		}
    		//if(ptr)
    		ptr = ptr->nextByName;
    	}
    	return false;
    }//end remove
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    Question:
    You cover special cases, such as the node to be removed being the first, second, or apparently also last in the list.

    Do any of these special cases apply in the situation you're having a problem with? Or does it happen in any and all cases?


    If you've been staring at it trying to figure it out, then you're most likely seeing what you "know" is there rather than what actually is there. That's a common problem and is why a second pair of eyes is often needed. But there are a couple techniques that you can try instead.

    1. Play computer. With pencil and paper, sketch out a doubly linked list. Then remove a node by stepping through the code line-by-line and doing exactly what each line tells you to do. The problem should present itself very quickly. The purpose of this evolution is force you to deal with exactly what's written and hence remove your preconceived notions about your own code -- the same basic technique applies to proof-reading your own writing.

    2. Use a debugger to step through the code.

    A third alternative that involves another person is to sit them down and explain to them exactly what your code does, line-by-line. This forces you to think through each line in order to be able to explain what it does. The other person doesn't even need to be able to understand what you're talking about. In the middle of the explanation, you will see your error, thank the other person for their help, and the other person will just sit there confused as ever.
    Last edited by dwise1_aol; April 17th, 2013 at 02:04 PM.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    I have actually done both of your suggestions and I may be just to close to the problem. I know that when you remove by name it does the first case fine, so the first case is working, But the second and 3rd cases are not. I am working on it now to just get the ByName working first and then i can work on the ByRating as it will be easier to figure out in smaller pieces. Thank you for the suggestions, do you see anything i have missed...i am just stumped, but i am not going to give up haha.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    OK so i have it working with just ByName, it seems the problems start when i add the code in for the ByRating...a little progress is better than none.
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    So then what you have is a collection of nodes, each of which is involved in two different doubly-linked lists. Interesting and logical.

    I notice that you rely a lot on testing whether a pointer is equal to the head-of-the-list pointer, which is not what I had learned (my training comes from the old segmented-memory days (eg, IBM-XT) where pointer comparisons could be unreliable). I also notice that the next pointers of the last node are set to NULL, which is how I had learned to terminate a linked list. What do the previous pointers of the first node point to? Are they also set to NULL?

    I ask because it might be that testing whether a previous pointer is NULL would be easier and less prone to error or confusion. IOW, maybe a procedure like this:
    1. Starting at the head of the byname list, you search for and find the node you want to remove. You use a temporary pointer, like ptr, for this.

    2. If the nextbyname pointer is not NULL, you set the next byname-node's previousbyname field to the current's previousbyname field. Do the same for nextbyrating.

    3. If the previousbyname pointer is not NULL, then set the previous byname node's nextbyname field to the current's nextbyname field. Do the same for previousbyrating.

    4. delete ptr;

    I can only see two special cases:
    1. the node to be removed is the first one in a list.
    2. the node to be removed is the only one in a list.

    I think that both special cases can be handled the same. You detect the special case by the previous pointer being NULL (this is why I ask how you set that field in the first node of a list). In that case, you will need to set the head pointer to the next field in the current to be removed; if that next field is also NULL, then you also took care of the second special case automatically.

    Perhaps thinking about the procedure in terms like this might suggest a cleaner approach. Or you could translate what you have into a similar procedural form to evaluate what your code is doing.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    I am not using a previousByName field at all. here is my struct for the node
    Code:
    struct node
        {
            node(const winery & winery);     // constructor
    		
            winery item;
            node * nextByName;
            node * nextByRating;
        };
     
        node * headByName;
        node * headByRating;
    };
  12. #7
  13. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    Oh! So then this is a different definition for "doubly-linked list" that I had never heard of before!

    A doubly linked list is where each node links both ways, both to the next and to the previous nodes -- see Wikipedia at http://en.wikipedia.org/wiki/Doubly_linked_list. The feature of a doubly linked list that a singly linked list does not have is the ability to traverse the list in either direction; a singly linked list can only be traversed in one direction.

    What you have is not a doubly linked list, but rather two singly linked lists. The term "doubly linked list" has a definite meaning and your using it to mean something quite different had confused me as it would any other programmer familiar with data structures. If you had provided the node declaration along with the function, then we would have been able to avoid or at least clear up the confusion caused by your misuse of the terminology.

    So you would need to traverse both lists until they find the same node. At that point, you will have two pointers pointing to the two nodes that precede the target node and with which you will need to update the appropriate pointer fields for their list -- a special case could be if both nodes are one and the same, or maybe not.

    PS

    A possible caveat with comparing pointers. If you are using a 32-bit system and compiler, then a flat memory model should be the case and comparing pointers should work, I believe. But if you are using a 16-bit compiler, then that would mean that you'd be using a segmented memory model in which case two pointers pointing to the same location could conceivably have different pointer values -- that is the reason why I had learned to not trust comparing pointers directly.

    Are you using a 16- or a 32-bit compiler? We get a lot of traffic here from students whose instructors saddle them with Turbo C, so it's a valid question. Maybe you'd do better to find the node in the byrating list the same way as you found it in the byname list, by comparing its name field with the name parameter that was passed in.
    Last edited by dwise1_aol; April 17th, 2013 at 03:44 PM.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    So, I think i am having a problem traversing both lists simultaneously. If i use one or the other it works perfectly, so it is something to do with how i'm traversing both. as you notice i am resetting temp and previous and setting them equal to headByRating, This is not correct. so when i get down to the point where it says ptr = ptr->nextByName; what do i do about nextByRating? because it needs to traverse the rating list to. I am thinking this is where my logic has gone askew.

    Thanks a lot for your help.

    P.S. when i reset temp and previous it is wrong, I know that now because if it moves to another node in the list for nextbyName then temp and previous are now incorrect values. Does this sound right?
  16. #9
  17. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    {Caveat: I had started writing this before noticing your reply and have not had time to read it yet.}

    Admittedly, it's been a few decades since I have played with singly linked lists. But I remember always using a look-ahead-by-one approach, since I had to keep a pointer on the previous node so I could modify its next field.

    So my test for a match would be:
    [b]if(strcmp(ptr->nextByName->item.getName(),name) == 0)
    such that when it succeeds then ptr is pointing to the previous node. So then I would save ptr->nextByName to a temp pointer so that I wouldn't drop that node when I did
    ptr->nextByName = ptr->nextByName->nextByName;
    At that point, I wouldn't need the previous node anymore.

    It looks like you're first scanning the linked list to find the node, then you scan it again to find the previous node. In really long lists, such as you would find in the real world, this is inefficient and can cause noticable delays. Using a look-ahead approach in the initial search will eliminate that second scan.

    Now referring to your latest reply. I would feel inclined to use different local variables for each list rather than reuse the same ones. Just to avoid possible confusion. And I'd rather do a name search in the byRating list to find the target node; still shy about comparing pointers because of bad experiences while working in older systems. Other than that I've not had time to think about it and need to get back to work.
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    23
    Rep Power
    0
    Ok so i got it thanks to you i followed your advice , i did set the variables to the same names but only because the scope was within the while loops they were in. basically i have to while loops with 2 different pointers, it goes through the while loops just like you see above and then it deletes both pointers and returns from the ratings while loop. Thanks for your help, it was really good.

IMN logo majestic logo threadwatch logo seochat tools logo