Proper way to delete a linked list

[Elixir42]

Hi

I am allocating memory space and adding nodes like this:

            CSprite* pNewSprite = new CSprite;   // Create new sprite
            pNewSprite->iData = iChoice;         // Attach data
            EnemyList->AddNode(pNewSprite);      // Send to AddNode

and also in the ::AddNode:

void CLinkedList::AddNode(VOID* pData)
{
    CNode* pNewNode = new CNode;      // Create the Node
    pNewNode->pData = pData;          // Assign the Sprite data

    ...

    m_iNumberOfNodes++;
}

And then (trying) to delete them like this:

    // Clear up and delete resources
    CurrentNode = EnemyList->m_pHeadNode->pNext;     // Point to first in list
    while (CurrentNode != EnemyList->m_pEndNode)
    {
        delete CurrentNode->pData;  // <======= Second time around access violation ========
        delete CurrentNode;
        CurrentNode = CurrentNode->pNext;            // Go to next in the list
    }
    delete CurrentNode;
    delete EnemyList;

The second time around the CurrentNode->pData is presumabley NULL. You see I am allocating memory for the Sprite and the Node so need to delete them both. Whats the proper way...? Do I have to cast them to a Sprite* then delete the objects then the node...?

[CGSMCMLXXV]

There is something I don't quite understand in your code: you delete CurrentNode and you call CurrentNode->pNext after. Does it really call anything that way?

[deceptikon]

delete CurrentNode;
CurrentNode = CurrentNode->pNext;

This is the problem. You aren't guaranteed to have a valid pointer even immediately after deleting it. It could be reused just that fast, or more likely, invalidated for debugging purposes. The correct way to traverse and delete a linked list is with two pointers:

CurrentNode = EnemyList->m_pHeadNode;

while (CurrentNode != EnemyList->m_pEndNode)
{
    // Save the current node for deletion
    Node *pTemp = CurrentNode;

    // Move the traversal pointer forward
    CurrentNode = CurrentNode->pNext;

    // Now you can safely delete the saved node
    delete pTemp;
}

// Clean up remaining EnemyList members as needed

[Elixir42]

That's really good, thanks. Why didnt I think of that...!
But when I check the debugger the memory address for pTempNode is still there... but the sprite contained in pTempNode->pData is NULL. See here:

        // Clear up and delete resources
        pCurrentNode = EnemyList->m_pHeadNode->pNext;      // Point to first in list
        while (pCurrentNode != EnemyList->m_pEndNode)
        {
            CNode* pTempNode = pCurrentNode;               // Save this node

            pCurrentNode = pCurrentNode->pNext;            // Go to next in the list

            delete (pTempNode->pData);    //<=== seems to do nothing
            delete pTempNode;             //<=== sets pTempNode->pData to NULL
            if (pTempNode == NULL) 
                cout << "pTempNode is NULL" << endl;        //<=== doesnt run
            if (pTempNode->pData == NULL)              
                cout << "pTempNode->pData is NULL" << endl; //<=== doesnt run
        }
        delete pCurrentNode;
        delete EnemyList;

Are you sure they are deleted...?

[CGSMCMLXXV]

delete calls the destructor, so, if you want to see if your object came to an end, you should add your message in the destructor. Also, if you want to free all the resources alocated by your object, one recommended way is to call delete/free in the destructor of your class (see RAII). Following your example, you can define something like that:

CNode::~CNode()
{
    delete pData;
}

In such way, whenever you call the destructor of the CNode class (by calling delete or exiting the scope), you get all your resources freed (see implementation of the smart pointers from boost library).

Also, I would recommend to add if(this != EnemyList->m_pEndNode) delete pNext; (or whatever condition you impose for defining the leaf) in the destructor, so, if you delete the root node, then all the branches are destroyed recursively.

This is just a suggestion. The solution is up to you. ;)

[Elixir42]

Brilliant, Thanks

[deceptikon]

delete (pTempNode->pData); //<=== seems to do nothing
delete pTempNode; //<=== sets pTempNode->pData to NULL

If pTempNode->pData was pointing to something previously allocated by new (not new[]), then the memory will be released. Likewise, deleting pTempNode will release the memory owned by pTempNode and call the destructor. Unless you're setting pData to NULL in the destructor of pTempNode, it may or may not be overwritten with a suitable "invalid" value.

If you don't reset the pointer to NULL explicitly, you cannnot assume that testing it against NULL will have predictable results.

Finally, this line is incorrect for the same reason that your original loop was incorrect:

if (pTempNode->pData == NULL)   

At this point pTempNode has been deleted, you no longer own it. Therefore any attempt to dereference it or use it for anything other than assigning a new address (or NULL) is undefined behavior.

[Elixir42]

I changed the creation of CLinkedList from dynamic to static as I was getting an error when trying to delete it at the end of the program!! Now the code is a little uglier with all the &s and *s to reference the nodes.

Now I am getting an error when calling the final destructor of the CNode class at the end of the program because it is trying to deleting pData (while it is NULL) from the head node (declared as CNode m_HeadNode).

CNode::~CNode(void)
{
    cout << "::~CNode deleting pData " << endl;

    if (pData != NULL) 
        delete pData;   // <=== Access violation when deleting HeadNode/EndNode
}

I tried adding a check to see if it was an end node or not (setting m_NodeType) but it doenst work...! In the destructor the all the m_NodeTypes are set to Non End types.

Can you help...?

EDIT* btw the LL does work I have stepped through the code checking all the addresses. Its just the final destructor...!

[CGSMCMLXXV]

You can set an identifier within the class CNode to keep tracking of whether it is or not a leaf. For example, a simple bool, int or string which can have 2 values depending on its position.

Other option is to use getters and setters. For example, if pData contains something, a class variable is modified. Checking for pData against NULL does not help (see deceptikon's previous post).

An example of setter combined with identifier:

class CNode
{
...
public:
    void setPData(CSprite*);
    void removePData();
    void setHasPData(bool)
    ...

private:
    CSprite* pData;
    bool hasPData;
    ...
}

// in the constructor
CNode::CNode() { hasPData = false; }

// passing object through the setter
void CNode::setPData(CSprite* cs)
{
    pData = cs;
    hasPData = true;
}

// releasing pData
void CNode::removePData()
{
    if(hasPData) delete pData;
    hasPData = false;
}

// setter for hasPData
// needed in case pData is released from somewhere else
void setHasPData(bool hpd)
{
    hasPData = hpd;
}

If you prefer to not work with identifier, you can set explicitly pData to NULL and then you can work with identification against NULL (I would go with hasPData, but it's not up to me here):

CNode::CNode()
{
    pData = NULL;
}

void CNode::removePData()
{
    if(hasPData != NULL) delete pData;
    pData = NULL;
}

NB: Say, if you are passing somehow by reference in setter and you release the memory in some other part of the code, you just get yourself in a nasty situation where you want to access a non-existing data. I suppose something similar happened in your application (double deletion or trying to access pData after it was released).

There are other options as well, but this is one of the simplest which can help you in avoiding attempts of accessing released memory.

I hope it will help.

[Elixir42]

Thank you for helping me... After meticulous stepping through I found that...

A) I was setting the HeadNode.m_NodeType to CNODE_NODE in the AddNode function accidently instead of setting the pNewNode->m_NodeType to CNODE_NODE and...

B) I had a stray CNODE TempNode that was being called without its .m_NodeType being initialised to a non leaf number...! (All fixed)

** Fore head slapping time **