每次我们在链表中创建一个新节点时，是否都会在堆栈中创建一个新指针？

Question

我今天刚开始学习链表，我无法理解以下概念：

class Node {
public:
    int data;
    node* next;
    Node(int d){
    data = d;
    next = NULL;
    }
};
void insertAfter(Node* prev_node, int new_data)  
{  
    if (prev_node == NULL)  
    {  
        cout << "the given previous node cannot be NULL";  
        return;  
    } 
    Node* new_node = new Node(new_data);   
    new_node->next = prev_node->next;  
    prev_node->next = new_node;  
}

这通常是我们编写的用于在链表中插入元素的代码

因此，根据我对

Node* new_node = new Node(new_data);

的理解，我们创建了一个能够存储节点类型地址的指针n。 new 关键字在自由存储中初始化/为对象创建内存，然后返回其地址，因此每次我们不断插入节点时，都会在堆栈中创建一个指向该特定节点的指针。

那么如果是这样的话，我们有一大堆节点，那么指向我们创建的新节点的指针岂不是会消耗大量的堆栈空间，最终证明它的内存使用率很高吗？我只是想了解一下我的理解是否有错误。非常感谢任何帮助。

Answer 1

不一定。您可以分配一个新节点，而无需将指针存储在任何地方。

就您而言，您将其存储在

new_node

中。

Node* new_node = new Node(new_data);

我们不确定

new_node

是否在堆栈上。它可能在其他地方，包括简单地存储在寄存器中。

通常，如果分配很多节点，则只会将节点指针存储在链接的节点中。如果您像上面的代码那样存储它，则相同的变量将用于存储下一个节点的节点指针。

所以你没有在堆栈上分配一堆内存。