Is it possible to create a linked list on the stack in C++?

Question

I just started learning C++ couple of weeks ago. So now I have this school assignment problem that asks me to implement a linked-list without using "new" or anything to do with dynamically allocating memory (and cannot use any ADT from STL). The prof says that everything can be done on the stack, but how? I have been working on this since Friday and still stuck on this with absolutely no luck.

It says: Keep a stack of the file names being read. Use the following data structure for the stack:

struct Node { 
string fileName; 
Node *link; 
}; 

I tried to avoid using new but it always give me "segmentation fault" or "BUS error" when I pass the head of the list into a recursive method call. Any ideas about how I can work around this??

Answer 1

The difference between heap and stack are mainly (not only, but for the sake of this question mainly) where the memory is allocated and how it is freed. When you want to allocate a node on the heap, you say new Node and the system will provide you with the memory, keeps track of which chunks are used and which ones are free, and provides you with the means to free a chunk once you don't need it any longer.

But you can just as well have a pool of nodes in an array on the stack. (Automatic variables are stack variables.) You can "allocate" from that pool, keep track of which nodes in the array are used and which are free, and mark unused ones as free ones you don't need them any longer. However, since the array's size is fixed at compile-time, this means that you have a maximum length for your list.