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

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

This code doesn't work. If I use allocation, it works. I try searching on Google but no one ask about this.

My code based on my understand about linked list. So feel free to roast me.

`Node *head; head->data = 999;` This exhibits undefined behavior, by way of accessing an uninitialized variable `head`. — Igor Tandetnik, Nov 09 '20 at 02:27
You can make it stack based - it's just not useful: `Node head; head.data = 999; Node new_node; new_node.data = 1; head.next = &new_node; cout << (head.next).data;` Basically if it is stack based then you don't need the pointers at all — Jerry Jeremiah, Nov 09 '20 at 02:41
It's not standard, but you can call an allocation function called alloca instead of malloc that allocates the memory on the stack: https://en.wikipedia.org/wiki/Stack-based_memory_allocation#:~:text=Many%20Unix%2Dlike%20systems%20as,variable%2Dlength%20arrays%20are%20handled. (just don't free it because it wasn't allocated with malloc) But read this: https://stackoverflow.com/questions/1018853/why-is-the-use-of-alloca-not-considered-good-practice — Jerry Jeremiah, Nov 09 '20 at 02:44
Extending the idea from @JerryJeremiah above you could create a local array of perhaps a thousand nodes like `Node myNodes[1000];` then point your head to &Node[0] `Node* head=&Node[0];` and head->next to perhaps &Node[1] `head->next = &Node[1];` ... — drescherjm, Nov 09 '20 at 02:59
@drescherjm That's a good idea. Then the code is the same whether you put it on the stack or in the heap. — Jerry Jeremiah, Nov 09 '20 at 03:05
@JerryJeremiah Well, "stack" doesn't mean "not dynamic". In particular, threading a linked list up through the stack frames of a recursive function is a quick and dirty (if inefficient) way to pass information down to the recursive calls. Of course, if stack overflows are an issue, you'd need to make some drastic changes, but sometimes simplest is best. — HTNW, Nov 09 '20 at 03:57

score 1 · Accepted Answer · answered Nov 09 '20 at 02:37

When you create Node* You are creating a node pointer not a node. This is just a variable that will hold a memory address, and that memory address will hold a node. Since you aren't allocating any memory there isn't actually a node to use when you use the -> operator. Basically its not going to work in your code because you're trying to dereference an uninitialized pointer and then modify memory that you haven't allocated yet.

As far as the overall question of why you can't make a linked list with static memory, that is because of scope rules and automatic memory management on the stack. The idea of the linked list is that you are linking nodes together based on their memory address. If you create each node on the stack those nodes will be deleted after they go out of scope, so even if you keep pointers to their memory address it is not safe to assume they wont be overwritten by something else. This of course would only be the case if you don't keep the entire thing within the same scope and would likely not be what you want.

score 1 · Answer 2 · answered Nov 09 '20 at 03:29

As @drescherjm suggested in the comments, you could make a static array of Node and index into that. The advantage of that is that the code only differs in the allocation function. For dynamic allocation, you would make a node with new Node and with a static array you would use &heap[++size];

Note that if the array is global it isn't actually on the stack - it needs to be a local variable to be on the stack.

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

Try it at https://onlinegdb.com/r1g-w4LKw

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

2 Answers2

Linked