Deleting nodes in a doubly linked list (C++)

Question

I have problems understanding why when I create two or more nodes (as shown below), the function void del_end()will only delete the char name[20] and not the whole node . How do I fix this problem without memory leak?

#include <iostream>
using namespace std;

struct node
{
    char name[20];
    char profession[20];
    int age;
    node *nxt;
    node *prv;
};

node *start_ptr = NULL;

void del_end()
{
    node *temp, *temp2;
    temp = start_ptr;
    if (start_ptr == NULL)
        cout << "Can't delete: there are no nodes" << endl;
    else if (start_ptr != NULL && start_ptr->nxt == NULL)
    {start_ptr=NULL;}
    else
    {
    while (temp->nxt != NULL)
    {
        temp = temp->nxt;
    }
    temp2=temp->prv;
    delete temp;
    temp->nxt= NULL;
    }
}

Answer 1

delete temp2;

WILL delete whole node.

Answer 2

Your code has some problems, the worst being here:

temp2=temp->prv;
delete temp2;
temp->nxt= NULL;

You're deleting the next-to-last node, leaving any pointers to it dangling, and losing the last node.

But if you post more of the real code, we can tell you more.

EDIT:
Here's a slightly cleaned-up version of del_end (and there's still plenty of room for improvement).

void del_end()
{
  if (start_ptr == NULL)
  {
    cout << "Can't delete: there are no nodes" << endl;
    return;
  }

  if (start_ptr->nxt == NULL)
  {
    delete start_ptr;
    start_ptr = NULL;
    return;
  }

  node *nextToLast = start_ptr;
  node *last = start_ptr->nxt;

  while(last->nxt != NULL)
  {
    nextToLast = last;
    last = last->nxt;
  }

  delete last;
  nextToLast->nxt = NULL;

  return;
}

Note that this does not assume that the prev links are correct, which seems prudent here.

Answer 3

If you're concerned about memory, I highly recommend learning to work with Valgrind http://valgrind.org/. It is a great tool. Valgrind divides memory leaks into 3 categories:

• "definitely lost" - pointer to dynamically allocated memory is lost and there is no way to recover it
• "possibly lost" - pointer to the dynamically allocated memory is pointing to the interior of a block and may be unrelated
• "still reachable" - pointer to the dynamically allocated memory still exists, but the memory was never freed at the end of the programs execution

Running Valgrind is also very simple. Here's a link to the User Manual http://valgrind.org/docs/manual/manual.html. Some useful flags when running valgrind:

• --leak-check=<no|summary|yes|full>
• --show-reachable=<no|yes>

Now, the way I would remove a node in a doubly-linked list is:

// if the node to be removed is the head node
if (nodeToRemove->prev == NULL) {
    // reassign the head node pointer
    start_ptr = nodeToRemove->next;
} else {
    // correct previous node pointer
    nodeToRemove->prev->next = nodeToRemove->next;
}

// if the node to be removed node is the tail node
if (nodeToRemove->next == NULL) {
    // reassign the tail node pointer
    end_ptr = nodeToRemove->prev;
} else {
    // correct next node pointer
    nodeToRemove->next->prev = nodeToRemove->prev;
}

// deallocate memory
delete(nodeToRemove);
nodeToRemove = NULL;

Just declare node *end_ptr = NULL; after you declare start_ptr and when you append a node to the list, make sure the end_ptr is always pointing to the end of the list... and if you're adding to the end of the list, its easy... just point the end_ptr to the node being added.

You might as well keep a tail pointer, if you always have to delete the last node. So once you have the node you want to delete, I just check if its the head/tail node, reassign the next/prev pointers, and free the memory.

Btw... I took this from my C implementation, so if the syntax is off I apologize... but the logic is there.

Hope that helps.

Answer 4

The problem is that you appear to be trying to delete the last node, but you are in fact deleting the one right before it.

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL; 

This is your issue. Change it to this:

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp; 
temp2->nxt= NULL;

And I believe it will work as intended. This saves off the next to last node, deletes the end and then sets the next to last node's nxt pointer to null, making it the last one.