Thread: Deleting node from doubly linked list

  1. #1
    Registered User filler_bunny's Avatar
    Join Date
    Feb 2003
    Posts
    87

    Deleting node from doubly linked list

    Hi

    I am writing a program in which events are entered into a list (no particular order). As the event passes (it is based on time), the node is flagged for removal. If there are any nodes to be removed a variable "nodesToRemove" is set (elsewhere in the program), and once all of the nodes that are flagged are removed from this list, it is reset to false (i.e. nothing to be removed). The problem I am having is that I cannot remove the node correctly. The node doesn't appear to be removed, with the exception of the time member which was allocated memory as well as the node that encloses it.

    The "head" and "tail" (not used here) are private members of the class and are of type EVENT_NODE*.

    Any ideas how to tidy this up?
    Code:
    int CEventTime::removeNodes(void)
    {
            EVENT_NODE *current;
            EVENT_NODE *temp;
            int numOfNodesRemoved = 0;
    
            current = head;
    
            while(current != NULL)
            {
                    if (current->flaggedToRemove)
                    {
                            temp = current->next;
    
                            if( current->prev )
                                    current->prev->next = current->next;
                            if( current->next )
                                    current->next->prev = current->prev;
    
                            delete current->time; // This seems to work
                            delete current; // This does not!
                            // Update the counters
                            numOfNodesRemoved++;
                            numberOfEvents--;
                    }
                    current = temp;
            }
            nodesToRemove = false;  // There are no further nodes to be removed
    
            return numOfNodesRemoved;
    }
    Last edited by filler_bunny; 08-23-2003 at 10:13 PM.
    Visual C++ .net
    Windows XP profesional

  2. #2
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    You seem to remove it OK, but you infinite loop; what happens if you DON'T want to remove the node? You never increment the current variable unless you're removing it.

    I think you want:

    Code:
            while(current != NULL)
            {
                    if (current->flaggedToRemove)
                    {
                            temp = current->next;
    
                            if( current->prev )
                                    current->prev->next = current->next;
                            if( current->next )
                                    current->next->prev = current->prev;
    
                            delete current->time;
                            delete current;
                            // Update the counters
                            numOfNodesRemoved++;
                            numberOfEvents--;
                            current = temp;
                    }
                    else current = current->next;

  3. #3
    Registered User filler_bunny's Avatar
    Join Date
    Feb 2003
    Posts
    87
    Yup - that fixed the other bug I was having! Thanks. But the removal of the node still does not succeed.
    TIME MEMBERS
    tm_sec : 8782144
    tm_min : 8795676
    tm_hour : 8795676
    tm_mday : 8782160
    tm_mon : 8782160
    tm_year : 8782168
    tm_wday : 8782168
    tm_yday : 8782176
    tm_isdst : 8782176
    BOOLEAN VALUES
    Remove : TRUE
    Flagged to Remove : TRUE
    Ignore day field? : TRUE
    Ignore the week day?: FALSE
    Ignore month field? : FALSE
    Ignore year field? : FALSE
    REMAINING FIELDS
    Event Description : TEST: Manual
    The first time through, the tm node contains the correct values, after deleting the nodes marked for deletion I check the list again, and I should not see the output from above. It should be gone. However as you can see the tm_* members have garbage in them, they appear to have been deleted correctly. The actual node itself is still there, the links are unbroken.

    I have checked that the insertion routine is correct, I can follow the links in both directions, so I am conviced the problem lies in this code.
    Code:
    typedef struct eventNode
    {
            tm *time;                                                                                      
            bool remove;                           
            bool flaggedToRemove; 
            bool ignoreDayField;                         
            bool ignoreWeekDayField;              
            bool ignoreMonthField;                
            bool ignoreYearField;                 
            string eventDesc;                    
            eventNode *next;                     
            eventNode *prev;                     
    } EVENT_NODE;
    Memory is allocated for the tm structure and all values are copied to the members. Then memory is allocated for the node itself.
    Code:
    int CGameTime::removeNodes(void)
    {
            EVENT_NODE *current;
            EVENT_NODE *temp;
            int numOfNodesRemoved = 0;
    
            current = head;
    
            while(current != NULL)
            {
                    if (current->flaggedToRemove)
                    {
                            temp = current->next;
    
                            if( current->prev )
                                    current->prev->next = current->next;
                            if( current->next )
                                    current->next->prev = current->prev;
    
                            delete current->time;
                            delete current;
                            // Update the counters
                            numOfNodesRemoved++;
                            numberOfEvents--;
                            current = temp;
                    }
                    else
                            current = current->next;
    
            }
            nodesToRemove = false;  // There are no further nodes to be removed
    
            return numOfNodesRemoved;
    }
    Above is the modified code containing the changes suggested above.
    Last edited by filler_bunny; 08-23-2003 at 10:49 PM.
    Visual C++ .net
    Windows XP profesional

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    The code looks OK, but what happens if you removed the node pointed at by head? You never adjust head to take that into consideration. Same with tail.

    Remember, if you delete an element in a linked list, you may have to correct other pointers.

    for example, you can put this at the beginning of the deletion code:

    if (current == head) head = head->next;
    if (current == tail) tail = tail->prev;
    Last edited by Cat; 08-23-2003 at 11:53 PM.

  5. #5
    Registered User filler_bunny's Avatar
    Join Date
    Feb 2003
    Posts
    87
    I think your right, I will have a look..
    Visual C++ .net
    Windows XP profesional

  6. #6
    Registered User filler_bunny's Avatar
    Join Date
    Feb 2003
    Posts
    87
    Yup

    Cheers, thanks for that. Lists are not my strong point, I really need to drill them into my head I think.
    Visual C++ .net
    Windows XP profesional

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Memory Leak
    By jtullo in forum C Programming
    Replies: 7
    Last Post: 12-11-2006, 11:45 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM