为什么这段代码不能用于删除链表中的节点?

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.

我一直在学习链接列表是如何工作的，并开始用c++构建一个实现来加强这些概念。一直进行得很顺利，直到我做了一个删除所有节点的函数。我找到了一个解决方案(注释代码)，但是我似乎不明白为什么其他代码不能工作。

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

节点对象是使用“new”创建的类的一个实例。因此，“delete”是用来删除它的。

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.

代码输出每个地址，但它似乎并没有删除对象。如果我在Windows中运行程序，程序实际上会锁定并且不会离开while循环。不是无限循环，它只是卡住了，函数永远不会结束。如果我在C4Droid上运行，程序不会锁定，但函数退出后节点仍然存在。

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

/*
 * 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

    /*
 * 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

/*
 * 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;
}

2 个解决方案

#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.

在上面的代码中，当循环时，您正在将pHead指针移动到列表中。当循环结束时，pHead指针为nullptr，这是正确的，因为列表现在是空的。

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.

对于未注释的新代码，在循环结束后没有设置pHead指针，从而使它指向垃圾。之后链接列表的任何使用都将无效。

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.

所以并不是函数没有删除所有的节点，而是当你删除了节点后，链表有一个野生的pHead指针，并且在任何后续函数中使用链表的pHead节点都变得不稳定。

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.

#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.

当您创建一个具有“new”关键字的对象时，涉及到两个主要的内存区域:“call stack”，用于跟踪本地变量和调用了哪些函数;“heap”，用于以牺牲速度保存更大量的数据。

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.

当您声明本地变量pCurrent时，在“调用堆栈”上创建一个指针，就像将一个本地整型变量与声明“int a”放在堆栈上一样。不需要删除堆栈上的局部变量。

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

但是，需要删除使用“new”创建的所有对象，因为它们是在堆上创建的。

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

正如PaulMcKenzie所写的，确保你的头部指针也设置为null。

void LinkedList::deleteAll() {

    Node *pCurrent = pHead;

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

        pCurrent = pNext;
    }

    pHead = nullptr;
}