C - Pointers and prepending in a Singly Linked List

Question

I am trying to understand the pointer logic behind prepending.

I declared a struct as follows:

typedef struct myList{
    int info;
    struct myList *link; //self referential structure;
} Node;

For memory allocation in the heap memory segment, I use the following function:

Node *getNode(){
    return ((Node *)malloc(sizeof(Node)));
}

In the main function, I allocate memory for the first node, I assign its link to NULL and its value to 2.

Node *head = getNode();
head -> link = NULL;
head -> info = 2;

Then comes the prepend function:

void prepend(Node **headPointer, int value) {
    Node *new_node;
    new_node         = getNode();
    new_node -> info = value;
    new_node -> link = *headPointer;
    *headPointer     = new_node;
}

I am using the following function call:

prepend(&head, 5)

As you can see, I'm using a pointer to a pointer. I store the address of head in headPointer. I create new_node and allocate memory to it. I assign its info field, then the link field gets the dereferenced headPointer, which is the value stored in head, which is in turn the address for the chunk of memory in the Heap segment.

So, I basically link new_node to head, right? Now comes the confusing part, for me. The dereferenced headPointer, which is head's pointed chunk of memory in the Heap segment, gets the value stored in new_node which is another address from the Heap segment, I guess. Then, both new_node and headPointer go out of scope. (?)

How does this all add up? Is there a simpler way to describe the situation or implement prepending?

When pointers that point to heap-allocated memory go out of scope, nothing happens to the heap-allocated memory. It is not de-allocated. Consider how malloc() could work if that were the case. — unwind
This is always confusing for beginners. The standard advice is: get a whiteboard and start drawing boxes and arrows. Each storage location is a box. A storage location which stores an integer gets an integer in it. A storage location which stores a pointer contains an arrow which points to another box. A storage location which stores NULL contains an X. Start drawing the boxes and arrows and see how they evolve over the course of your program and it will come to make sense. — Eric Lippert
an aside, you should always check the return value of malloc and handle appropriately if it returns NULL,, and there's no need to/shouldn't cast the result of malloc. Are you only trying to understand what's happening? The code looks good to me, are you segfaulting somewhere? — yano
@yano The code runs perfectly. I'm just trying to understand the pointer logic. — NeVada

Gaurav Sehgal Gaurav Sehgal · Accepted Answer · 2017-07-21T20:42:19

Then, both new_node and headPointer go out of scope. (?)

At the end of the prepend() newnode goes out of scope but not the memory allocated since it is allocated on heap.If it were something like int a, then at the end of prepend(), a is gone out of scope and referencing a after that would be undefined behavior.Please read this and this to know about heap.

Also since you pass head of the list as pointer to pointer, when you change what the headPointer points to inside prepend(), it is reflected outside the function so you still have a pointer to the head of the list.

|2|-->NULL
 ^ 
 |
head

After call to prepend()

1)  |5|-->  |2|-->NULL
             ^ 
             |
           head  

2)  |5|---->   |2|--->NULL
     ^
     |
    head

Also remeber to have some way of accessing the heap allocated memory in order to deallocate it.If you don't have any means of pointing to a memory allocating on a heap, then you are left with a memory leak.

C - Pointers and prepending in a Singly Linked List

1 Answers