为何栈上创建Node对象会导致链表多次插入后display函数无限循环？

问题背景 #

你在学习链表时发现，未使用new的insertAtEnd实现会导致调用display()时无限输出3，而使用new就能解决问题，想理解背后的原因。

错误实现的问题分析 #

先看你写的错误版本insertAtEnd：

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

核心问题出在栈内存的局部变量特性：

• Node newNode = Node(x);是在函数的栈内存中创建局部对象。栈内存的特点是：函数执行完毕后，这块内存会被标记为可复用，且每次调用该函数时，这个局部变量的内存地址完全相同（因为函数栈帧的位置固定）。

一步步拆解调用过程：

1. 第一次调用insertAtEnd(1)：此时链表为空，head被赋值为newNode的地址。函数执行结束后，newNode的栈内存被释放，但head仍保留着这个无效地址（野指针）。
2. 第二次调用insertAtEnd(2)：在同一个栈地址创建新的newNode（data=2）。此时head指向的地址恰好就是这个新newNode的地址（因为地址重复），进入else分支后，遍历到链表末尾（此时current->next是NULL），将current->next指向newNode的地址——也就是指向自身。函数结束后，这块内存再次被释放，但链表的指针已经形成了自引用。
3. 第三次调用insertAtEnd(3)：还是在同一个栈地址创建newNode（data=3），覆盖了之前的内容。此时head指向的地址依然是这个栈地址，遍历链表时，current->next指向的是自身（上一次调用设置的），最终退出循环后，把current->next再次指向自身（其实没变化）。

当调用display()时，current从head开始，每次current = current->next都指向同一个节点（因为该节点的next指向自己），而节点的data最后被第三次调用的3覆盖，所以会无限输出3。

另外，这里还有一个严重问题：所有指针都指向已经被释放的栈内存，属于野指针访问，行为是未定义的，无限输出3只是其中一种可能的表现。

正确实现的原理 #

使用new的版本：

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 Node(x)是在堆内存中动态分配节点空间，堆内存不会随函数执行结束而自动释放，且每次new都会分配一个全新的、唯一的内存地址。
• 每个节点都拥有独立的内存空间，next指针指向的是另一个节点的有效地址，不会出现自引用或地址重复覆盖的问题。遍历到最后一个节点时，其next为NULL，display()能正常结束循环。

总结 #

• 栈内存的局部变量生命周期仅限于函数执行期间，且地址重复，用它来存储链表节点会导致野指针、自引用和数据覆盖问题。
• 堆内存的动态分配（new）能为每个节点提供独立的、持久的内存空间，保证链表结构的有效性。

内容的提问来源于stack exchange，提问作者user17055428