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

---

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;

---

Yup - that fixed the other bug I was having! Thanks. But the removal of the node still does not succeed.

Quote:

---

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.

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;

I think your right, I will have a look..

Yup :)

Cheers, thanks for that. Lists are not my strong point, I really need to drill them into my head I think.