CODEWITHSUNDEEP
c++linked-listnodes
WombatCombat
WombatCombat

Reputation: 51

How do I properly delete nodes of linked list in C++

I feel as if I am not actually deleting the node and freeing up memory. I think I am just moving pointers around so when I print the linked list the list doesn't print the element I deleted. So my question is am I actually deleting the node or am I just simply rearranging the pointers so it looks like I am deleting the nodes(Essentially just breaking the links but not deleting the node)? Thank you for any help.

void SLL::deleteNode(int target){
Node *current = new Node;
Node *previous = new Node;

for (current = front->next, previous = front; current != NULL; current = current->next, previous=previous->next){
    if (previous->data == target && previous == front){
        front = previous->next;
        delete[] previous;
        return;
    //This if statement deletes the element if its the front
    }

    else {

        if (previous->data == target && previous->next == NULL){
            previous = NULL;
            delete[] current;
            return;
        //This if statement deletes the node if it is the back
        }


        else if (current->data==target)
        {
            previous->next = current->next;
            delete[] current;
            return;
        //This if statement deletes a node if it is in the middle
        }
    }
    }

    delete[] current;
    delete[] previous;
}

Upvotes: 3

Views: 20076

Answers (1)

Spock77
Spock77

Reputation: 3325

Node *current  = new Node;
Node *previous = new Node;

This code causes memory leaks - you are never deleting this memory. You can declare pointers without memory allocation:

Node *current  = nullptr;
Node *previous = nullptr;

delete will delete the memory of the pointer so you will actually delete Nodes. But using delete[] for the Node* is incorrect, it should be used only for arrays - the memory allocated with new[]. Improper use leads to undefined behaviour. So, to properly delete nodes delete them with operator delete.

Use memory leaks detection tools to know are there memory leaks in you program.

The code to delete a list element: say, we have pHead which points to the head of the list (but it would give you much more if you write such things yourself):

Node* pCur  = pHead;
Node* pPrev = pCur;

while (pCur && pCur->data != target) {
    pPrev = pCur;
    pCur  = pCur->next;
}

if (pCur==nullptr)  // not found
   return NOT_FOUND;

if (pCur == pHead) {   // first element matches
    pHead = pCur->next;
} else {
    pPrev->next = pCur->next;
}

// pCur now is excluded from the list

delete pCur;     // deallocate its memory

Alternative Using Pointer To Pointer (Community Addition)

The above can take on new light when you use the actual pointers in the list to perform the enumeration. The following starts with pp being assigned the address of the head pointer (not the node it points to; the actual pointer itself). We walk the list until pp hold the address of a pointer that is pointing to a node with the target to delete (could be the head pointer, could be a next pointer in some node, makes no difference). The pointer being addressed is set to its own node's next value, then the target node is removed.

This really should be watched in a debugger to see how it works, but the algorithm is remarkably simple given what is really going on:

Node **pp = &pHead;
while (*pp && (*pp)->data != target)
    pp = &(*pp)->next;

if (*pp)
{
    Node *victim = *pp;
    *pp = victim->next;
    delete victim;
}

Thats all of it. And you get head-node removal without having to special case it for free. Hope this helps as well.

Upvotes: 10

Related Questions