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

Question

Hi 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??

Thanks very much for any input.

Answer 1

Think of arrays. Maybe more than one, if required.

Answer 2

Without much info:

Is the recursive implementation a requirement? When you make a recursive call, you get a new stack. Maybe you could use an iterative approach.

Answer 3

Once a function is called, the stack allocation is fixed for that function.

The only way to get more stack memory allocated would be to call another function. Which could then call another function. Which could then call another function. Or maybe they could all be the same function...

Each function call has it's own fixed-size stack, but the function call graph itself is a variable-sized stack of those stacks.

Answer 4

If you know how many filenames you need to store you could use an array of struct Node and build your list from that.

Using iteration a possible alternative is to have one struct Node object in your function and passing a pointer to it in the recursive call, where you use the pointer for the next link of the Node object in that functions stack frame.

Note that in the latter case the list is only valid on the deepest recursion, the list is broken down again when the recursive calls return to their caller.

Answer 5

Hi, I've created a small sample that you may find inspiring. I creates a singly linked list of elements on the stack. Take notice how the list is created in reverse and how recursion is used to 'allocate' the number of itmes you need. Also note how the list is passed to the as the parameter. Hope this helps, good luck.

#include <cstdio>

using namespace std;

struct Node {
    Node* next_;
    int value_;
};

// Creates a linked list of nodes containing raising values.
void intList(Node* prevNode, int restValue) {
    if (rest) {
       // A node on the stack, which is linked to list created so far.
       Node node;
       node.next_ = prevNode;
       node.value_ = restValue; 
       // Create a next node or print this list if rest runs to zero.
       intList(&node, rest - 1);
    }
    else {
    // Depest recursion level, whole list is complete.
    for (Node* iter = prev; iter; iter = iter->next_)
        printf("item %d\n", iter->value_);
    }
}

int main() {
    intList(NULL, 10);
}

Answer 6

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.

Answer 7

To "create a linked list on the stack" typically you would use a function like alloca to get more stack memory. However, that doesn't sound like what you're being asked to do.

It sounds like you're supposed to keep a stack on the stack, and not an arbitrary linked list. As a hint, the general syntax for what you want to do:

void push(struct Node *oldHead, String elem) {
    struct Node newHead;
    head.fileName = elem;
    head.next = oldHead.
    struct Node *head = &newHead
    // then you need to continue what you're doing in this function, since
    // returning will effectively pop the stack.

There are (nontrivial) techniques for implementing full fledged garbage collected lists along these lines, but that's beyond the scope of what you're doing.

Answer 8

You should probably go talk to your professor and clarify the requirements, since from your description, this seems like a very odd assignment for a new c++ programmer. Requiring an implementation of a linked list with memory only on the stack is bizarre to say the least.

Answer 9

It's possible to use the C++ address-of operator (&) to retrieve a pointer to an object on the stack instead of dynamically allocating memory with new.

Since generating a linked list in such a manner is of questionable use except as a homework assignment, I'm not sure if that's what is actually required. Without a code sample, it's hard to say exactly where the problem is.

Answer 10

Use alloca() instead of malloc() function to allocate memory dynamically on the stack frame of the caller function instead of heap. You don't have to worry about freeing the memory because it automatically freed when the function is returns.

link text