Why use dynamic memory allocation(i.e. malloc()) when implementing linked list in c?

Question

Okay this question may sound stupid to the amateur programmers . But seriously this is bothering me and a solemn answer to this doubt of mine is welcomed. I have just started to take my first ever course in data structures. And what is bothering me is this:

Assuming C is used,

//Implementing a node

struct Node
{
     int data;
     struct *Node;
};

Now while creating a node why do we use the dynamic memory allocation technique where we use malloc(). Can't we just create a variable of type ' Struct Node '. i.e. something like:

struct Node N1;
 //First node - actually second where !st Node is assumed to be Head.

struct Node *Head = &N1;
struct Node N2;
N2.(*Node) = &N1;

Well some parts of my code may be incorrect because I am only a beginner and not well versed with C. But by know you may have understood what I basically mean. Why don't we create variables of type Node of an Array of type Node to allocate memory t new nodes why get into the complexity of dynamic memory allocation?

Answer 1

First off, you have an error in how you declare your struct. struct * by itself does not denote a type. You have to give the full type name:

struct Node
{
     int data;
     struct Node *Node;
};

You can certainly use local variables as above to make a linked list, however that limits you to a fixed number of list elements, i.e. the ones you explicitly declare. That would also mean you can't create a list in a function because those variables would go out of scope.

For example, if you did this:

struct Node *getList()
{
    struct Node head, node1, node2, node3;
    head.Node = &node1;
    node1.Node = &node2;
    node2.Node = &node3;
    node3.Node = NULL;
    return &head;
}

Your list would be restricted to 4 elements. What of you needed thousands of them? Also, by returning the address of local variables, they go out of scope when the function returns and thus accessing them results in undefined behavior.

By dynamically allocating each node, you're only limited by your available memory.

Here's an example using dynamic memory allocation:

struct Node *getList()
{
    struct Node *head, *current;
    head = NULL;
    current = NULL;

    // open file
    while (/* file has data */) {
        int data = /* read data from file */
        if (head == NULL) {      // list is empty, so create head node
            head = malloc(sizeof(struct Node *));
            current = head;
        } else {                 // create new element at end of list
            current->next = malloc(sizeof(struct Node *));
            current = current->next;
        }
        current->data = data;
        current->Node = NULL;
    }
    // close file
    return head;
}

This is psedo-code that doesn't go into the details of reading the relevant data, but you can see how you can create a list of arbitrary size that exists for the lifetime of the program.

Answer 2

If these variables are local, defined inside a function's scope (i.e. stored on the stack), you shouldn't do this, because accessing them after leaving their scope will result in undefined behavior (their contents will likely be overwritten as you call other functions). In fact, any time you return a pointer to a local, stack based variable from your function, you are doing the wrong thing. Given the nature of C, this is problematic since nothing will warn you you are doing something wrong, and it will only fail later when you try to access this area again.

On the other hand, if they are declared as global variables (outside any other function), then you are simply limited by the number of variables declared that way.

You can potentially declare many variables, but keeping track of which one is "free" for use will be painful. Sure, you can even go a step further and say you will have a global preallocated array of nodes to prevent using malloc, but as you are doing all this you are only getting closer to writing your own version of malloc, instead of sticking to the existing, dynamic one.

Additionally, all preallocated space is wasted if you don't use it, and you have no way of dynamically growing your list in runtime (hence the name dynamic allocation).