为什么创建指向堆栈上节点的指针会导致我的链表显示函数在两次插入后进入无限循环？

Question

我正在学习链表，并试图理解为什么在链表中插入节点时使用“new”运算符。具体来说，我想知道为什么在两次或多次 insertAtEnd 调用后调用 display() 时，以下 insertAtEnd 实现会导致无限循环。

#include <iostream>
using namespace std;

class Node {
    public:
        int data;
        Node* next;
        Node() {
            data = 0;
            next = NULL;
        }
        Node(int x) {
            data = x;
            next = NULL;
        }
};

class LinkedList {
    private:
        Node* head;
    public:
        LinkedList() {
            head = NULL;
        }

        // insert a node at the end of the linked list
        void insertAtEnd(int x) {
            Node newNode = Node(x);
            Node* current = head;
            // if LL is empty
            if (head == NULL) {
                head = &newNode;
            }
            // if LL is non-empty
            else {
                while (current->next != NULL) {
                    current = current->next;
                    
                }
                current->next = &newNode;
            }
        }

        // print out the contents of the linked list
        void display() {
            Node* current = head;
            while (current != NULL) {
                cout << current->data << " ";
                current = current->next;
            }
            cout << endl;
        }


};

int main() {
    LinkedList llist;
    llist.insertAtEnd(1);
    llist.insertAtEnd(2); 
    llist.insertAtEnd(3); 
    llist.display();

    return 0;
}
// output shows 3 3 3 3 3 3 3 3 3 3 3 3 3 3 .....

我知道使用新的运算符可以解决这个问题，

        // insert a node at the end of the linked list
        void insertAtEnd(int x) {
            Node* newNode = new Node(x);
            Node* current = head;
            // if LL is empty
            if (head == NULL) {
                head = newNode;
            }
            // if LL is non-empty
            else {
                while (current->next != NULL) {
                    current = current->next;
                    
                }
                current->next = newNode;
            }
        }

但我很难理解为什么这里使用 new 有效，以及为什么之前不使用 new 的 insertAtEnd 不起作用。

我的理解是，如果使用 new，每次调用 insertAtEnd 时，都会在堆（不同的内存位置）上动态分配额外的内存。如果不使用 new，则 insertAtEnd 每次调用时都会在堆栈上创建一个节点对象，该对象位于同一内存位置，导致插入的值覆盖先前插入的值。但我不确定为什么输出是 3 3 3 3 3...而不是 1 2 3 或如果使用不带 new 的 insertAtEnd 实现则只是 3。

Answer 1

请注意，离开函数后（例如，

llist.insertAtEnd

），堆栈区域将被以后的函数调用（例如，

llist.display

）重用，因此可能会覆盖以前使用的值。此外，不同的编译器可能在堆栈上使用不同的值顺序。因此，行为将取决于您使用的编译器等因素，因此它是 UB（未定义行为）。

尽管如此，您的情况基本上发生了这种情况。在每次调用

insertAtEnd

期间，都会为堆栈上的

newNode

对象调用构造函数，因此

data

设置为

x

（即 1、2 或 3），并且

next

设置为

 NULL

。函数结束后，由于您尚未创建

Node

析构函数，因此会调用默认析构函数，在您的情况下它不会执行 anything，因此

data

和

next

的值保持不变。

此外，在第一次调用期间，

head

的值为NULL，因此

head

被分配指向堆栈上的

newNode

对象。对于第二次和第三次调用，由于

head

不是

NULL

，因此它将检查

current

，即

head

，它指向

newNode

。由于构造函数将其设置为

NULL

，因此

current->next = &newNode;

行将其设置为指向

newNode

。换句话说，此时，

newNode.next

指向其自身。

由于退出时 this 没有改变，所以这就是剩下的被使用的，即

next

指针指向它自己的对象。另外，在第三次调用时，

newNode.data

的值为3。因此，

llist.display();

进入无限循环（因为

current->next

始终指向自身，因此永远不会为NULL），重复输出3的值.