Why create heap when creating a linked list when we can simply do this?

Question

I'm studying linked lists from this lesson.

The writer (and all other coders on every single tutorial) goes through creating node type pointer variables, then allocates memory to them using typecasting and malloc. It seems kinda unnecessary to me (Offourse I know I'm missing something), why can't we implement the same using this?

struct node 
{
  int data;
  struct node *next;
};

int main()
{
  struct node head;
  struct node second;
  struct node third;

  head.data = 1;
  head.next = &second;

  second.data = 2;
  second.next = &third;

  third.data = 3;
  third.next = NULL;

  getchar();
  return 0;
}

I've created nodes and the next pointers points towards the addresses of the next nodes...

Answer 1

But what if you had a file containing an unknown number of entries, and you needed to iterate over them, adding each one to the linked list? Think about how you might do that without malloc.

You would have a loop, and in each iteration you need to create a completely new "instance" of a node, different to all the other nodes. If you just had a bunch of locals, each loop iteration they would still be the same locals.

Answer 2

Let's say you create a variable of type node called my_node:

struct node my_node;

You can access its members as my_node.data and my_node.next because it is not a pointer. Your code, however, will only be able to create 3 nodes. Let's say you have a loop that asks the user for a number and stores that number in the linked list, stopping only when the user types in 0. You don't know when the user will type in 0, so you have to have a way of creating variables while the program is running. "Creating a variable" at runtime is called dynamic memory allocation and is done by calling malloc, which always returns a pointer. Don't forget to free the dynamically allocated data after it is no longer needed, to do so call the free function with the pointer returned by malloc. The tutorial you mentioned is just explaining the fundamental concepts of linked lists, in an actual program you're not going to limit yourself to a fixed number of nodes but will instead make the linked list resizable depending on information you only have at runtime (unless a fixed-sized linked list is all you need).

Edit:

"Creating a variable at runtime" was just a highly simplified way of explaining the need for pointers. When you call malloc, it allocates memory on the heap and gives you an address, which you must store in a pointer.

int var = 5;
int * ptr = &var;

In this case, ptr is a variable (it was declared in all its glory) that holds the address of another variable, and so it is called a pointer. Now consider an excerpt from the tutorial you mentioned:

struct node* head = NULL;
head = (struct node*)malloc(sizeof(struct node));

In this case, the variable head will point to data allocated on the heap at runtime.

If you keep allocating nodes on the heap and assigning the returned address to the next member of the last node in the linked list, you will be able to iterate over the linked list simply by writing pointer_to_node = pointer_to_node->next. Example:

struct node * my_node = head; // my_node points to the first node in the linked list
while (true)
{
    printf("%d\n", my_node->data); // print the data of the node we're iterating over
    my_node = my_node->next; // advance the my_node pointer to the next node
    if (my_node->next == NULL) // let's assume that the 'next' member of the last node is always set to NULL
    {
        printf("%d\n", my_node->data);
        break;
    }
}

You can, of course, insert an element into any position of the linked list, not just at the end as I mentioned above. Note though that the only node you ever have a name for is head, all the others are accessed through pointers because you can't possibly name all nodes your program will ever have a hold of.