Why does use-after-free happen when a linked list node deletes its neighbors in the destructor?

I am having a problem with delete and destructor (I am sure I am making a stupid mistake here, but haven't been able to figure it out as of yet).

When I step through into the destructor, and attempt to call delete on a pointer, the message shows up "Cannot access memory at address some address."

The relevant code is:

/*
 * Removes the front item of the linked list and returns the value stored
 * in that node.
 *
 * TODO - Throws an exception if the list is empty
 */
std::string LinkedList::RemoveFront()
{
    LinkedListNode *n = pHead->GetNext(); // the node we are removing
    std::string rtnData = n->GetData(); // the data to return

    // un-hook the node from the linked list
    pHead->SetNext(n->GetNext());
    n->GetNext()->SetPrev(pHead);

    // delete the node
    delete n;
    n=0;

    size--;
    return rtnData;
}

and

/*
 * Destructor for a linked node.
 *
 * Deletes all the dynamically allocated memory, and sets those pointers to 0.
 */
LinkedListNode::~LinkedListNode()
{
    delete pNext; // This is where the error pops up
    delete pPrev;
    pNext=0;
    pPrev=0;
}

It seems that you are deleting the next and previous nodes of the list from the destructor. Which, if pNext and pPrev are LinkedListNode*, means that you are recursively deleting the whole list :-(

Try this:

std::string LinkedList::RemoveFront()
{
    LinkedListNode *n = pHead->GetNext(); // the node we are removing
    std::string rtnData = n->GetData(); // the data to return

    // un-hook the node from the linked list
    pHead->SetNext(n->GetNext());
    n->GetNext()->SetPrev(pHead);

    n->SetNext(0);
    n->SetPrev(0);
    // delete the node
    delete n;
    n=0;

    size--;
    return rtnData;
}

LinkedListNode::~LinkedListNode()
{
}

(Actually you don't even need to reset the prev and next pointers to 0 since you are going to delete the node anyway. I left those statements in because they at least put the node into a consistent state, which is a good idea in general. It may make a difference if you later e.g. change your memory management strategy and decide to store unused nodes for later reuse.)