Why doesn't this code work for deleting nodes in a linked list?

Question

I've been learning how Linked Lists work,and started building an implementation in C++ to reinforce the concepts. It was going well until I made a function to remove all nodes. I figured out a solution (which is the commented code) but I can't seem to figure out why the other code didn't work.

The Node object is an instance of a class that was created using 'new'. Therefore 'delete' is used to, well, delete it.

I thought it may have been related to deleting the object and reusing the pointer variable. Then I came across this: What happens to a pointer itself after delete? I've been staring at it for a while trying to figure out what it could be, and nothing I have researched seems to be providing an answer.

I don't believe it is something with my implementation so far because the programs works as expected when replacing the code with the solution code.

The code outputs every address, but it doesn't seem to actually delete the object. If I run the program in Windows, the program will actually lock and never leave the while loop. Not an infinite loop, it just gets stuck and the function never finishes. If I run it on C4Droid the program doesn't lock, but the nodes still exist after the function exits.

So my question is, why doesn't the current code work? (Ignore the commented code. That is a working solution.) Is there something simple I'm overlooking with pointer variables? Thank you in advance.

void LinkedList::deleteAll() {
Node *pCurrent = pHead;

while(pCurrent){
    Node *pNext = pCurrent->pNext;
    std::cout << pCurrent << std::endl;
    delete pCurrent;
    pCurrent = nullptr;
    pCurrent = pNext;

//  pHead = pHead->pNext;
//  delete pCurrent;
//  pCurrent = pHead;
}
}

Node class

class  Node{
    public:
        Node(string content):data(content){}
        string getData(){
            return data;
        }
        Node *pNext = nullptr;
    private:
        string data;
    };

LinkedList.h

/*
 * LinkedList.h
 *
 *  Created on: Oct 3, 2015
 *      Author: Anthony
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

#include<string>
using std::string;

class LinkedList {
public:
    LinkedList();
    virtual ~LinkedList();
    int length();
    void addNode(string nodeContent);
    void deleteNode(string nodeContent);
    void deleteAll();
private:
    class  Node{
    public:
        Node(string content):data(content){}
        string getData(){
            return data;
        }
        Node *pNext = nullptr;
    private:
        string data;
    };

    Node *pHead = nullptr;

};

#endif /* LINKEDLIST_H_ */

LinkedList.cpp

    /*
 * LinkedList.cpp
 *
 *  Created on: Oct 3, 2015
 *      Author: Anthony
 */

#include "LinkedList.h"
#include <iostream>
LinkedList::LinkedList() {
    // TODO Auto-generated constructor stub

}

LinkedList::~LinkedList() {
    // TODO Auto-generated destructor stub
}

int LinkedList::length() {
    Node *current = pHead;
    int count = 0;
    while(current){
        count++;
        current = current->pNext;
    }
    return count;
}

void LinkedList::addNode(std::string nodeContent) {
    Node *newNode = new Node(nodeContent);
    newNode->pNext = pHead;
    pHead = newNode;
}

void LinkedList::deleteNode(std::string nodeContent) {
}

void LinkedList::deleteAll() {
    Node *pCurrent = pHead;

    while(pCurrent){
        Node *pNext = pCurrent->pNext;
        std::cout << pCurrent->pNext << std::endl;
        delete pCurrent;
        pCurrent = nullptr;
        pCurrent = pNext;

    //  pHead = pHead->pNext;
    //  delete pCurrent;
    //  pCurrent = pHead;
    }
}

main.cpp

/*
 * main.cpp
 *
 *  Created on: Oct 3, 2015
 *      Author: Anthony
 */

#include<iostream>
#include "LinkedList.h"

int main(int argc, char **argv){

    using namespace std;

    LinkedList list = LinkedList();
    list.addNode(string("Test"));
    list.addNode(string("Test1"));

    list.deleteAll();
    cout << list.length() << endl;

    return 0;
}

Answer 1

Assuming (and this is a big assumption) that your linked list is put together correctly, the issues with why the commented code works and the new code doesn't is rather simple.

  pHead = pHead->pNext;
  delete pCurrent;
  pCurrent = pHead;

In the above code, you are moving the pHead pointer through the list while you're looping. When the loop has finished, the pHead pointer is nullptr, which is correct since the list is now empty.

Node *pNext = pCurrent->pNext;
    std::cout << pCurrent << std::endl;
    delete pCurrent;
    pCurrent = nullptr;
    pCurrent = pNext;

With your new, uncommented code, you did not set the pHead pointer after the end of the loop, thus leaving it pointing to garbage. Any usage of the linked list after that becomes invalid.

So it isn't the function isn't deleting all of the nodes, it is that after you've deleted the nodes, the linked list has a wild pHead pointer, and using the linked list's pHead node in any subsequent functions becomes unstable.

Try the following:

void LinkedList::deleteAll() {
Node *pCurrent = pHead;
while(pCurrent){
    Node *pNext = pCurrent->pNext;
    delete pCurrent;
    pCurrent = nullptr;
    pCurrent = pNext;
}
pHead = nullptr;  // Sets the head pointer to nullptr, denoting that the list is empty.

Answer 2

There are two major memory regions involved when you create an object with the "new" keyword, the "call stack," which keeps track of local variables and which functions have been called, and the "heap," which is designed to hold larger amounts of data at the expense of speed.

When you declare your local variable pCurrent, a pointer gets created on the "call stack," just like an local integer variable would be put on the stack with the declaration "int a;" Local variables, variables on the stack, do not need to be deleted.

All objects created with "new" need to be deleted, though, as they are created on the heap.

As PaulMcKenzie wrote, make sure to set your head pointer to null as well.

void LinkedList::deleteAll() {

    Node *pCurrent = pHead;

    while(pCurrent){
        Node *pNext = pCurrent->pNext;
        std::cout << pCurrent << std::end;
        delete pCurrent;

        pCurrent = pNext;
    }

    pHead = nullptr;
}