为什么我不能在堆栈内存而不是堆上实现链表？

Question

struct node{
  int data;
  node* next;
}

int main(){
  Node *head; head->data = 999;
  Node *new_node; new_node->data = 1; head->next = new_node;
  cout << (head->next)->data;
}

此代码无效。如果我使用分配，它会起作用。我尝试在 Google 上搜索，但没有人问这个问题。

我的代码基于我对链表的理解。所以尽管烤我。

Answer 1

当你创建 Node* 您正在创建节点指针而不是节点。这只是一个保存内存地址的变量，该内存地址将保存一个节点。由于您没有分配任何内存，因此在使用 -> 运算符时实际上没有要使用的节点。基本上它不会在你的代码中工作，因为你试图取消引用一个未初始化的指针，然后修改你尚未分配的内存。

至于为什么不能使用静态内存创建链表的整体问题，那是因为作用域规则和堆栈上的自动内存管理。链表的想法是，您根据节点的内存地址将节点链接在一起。如果您在堆栈上创建每个节点，这些节点在超出范围后将被删除，因此即使您保留指向它们内存地址的指针，假设它们不会被其他东西覆盖也是不安全的。当然，只有在您不将整个事物都放在同一范围内并且可能不是您想要的情况下才会出现这种情况。

Answer 2

正如@drescherjm 在评论中所建议的那样，您可以创建一个 Node 的静态数组并对其进行索引。这样做的好处是代码仅在分配函数上有所不同。对于动态分配，您将使用 new Node 创建一个节点，并使用静态数组使用 &heap[++size];

请注意，如果数组是全局数组，它实际上并不在堆栈上 - 它需要是一个局部变量才能在堆栈上。

#include <iostream>

struct Node
{
    long data;
    Node *next;
};

Node heap[1000];
int capacity = 1000;
int size = 0;

Node *alloc()
{
    // For dynamic allocation you would:
    // return new Node;
    
    // For stack allocation you would:
    // return &heap[++size];

    if (size >= capacity)
        throw std::bad_alloc();
    return &heap[size++];
}

int main()
{
    Node *head = alloc();
    head->data = 999;
    std::cout << "head: " << head << " (value: " << head->data << ")\n";

    Node *new_node = alloc();
    new_node->data = 1;
    head->next = new_node;
    std::cout << "node: " << new_node << " (value: " << (head->next)->data << ")\n";

    std::cout << "heap: " << heap << " (used/capacity: " << size << "/" << capacity << ")\n";

    return 0;
}

在 https://onlinegdb.com/r1g-w4LKw

试试

为什么我不能在堆栈内存而不是堆上实现链表？

Why I can't implement linked list on stack memory instead of heap?

c++

singly-linked-list