Imagine you're on a scavenger hunt. You start with a single slip of paper in your hand. That paper has two things on it: a secret message and a set of directions to where the next slip of paper is hidden. You go to that location, find the second slip, read its message, and get the directions to the third. This continues until you find a slip that says "The End" and provides no further directions.

That's exactly how a singly linked list works. Unlike an array, where every element sits right next to its neighbor in a neat row of memory, linked list elements (which we call "nodes") can be scattered anywhere in your RAM. They stay connected because each node holds a pointer to the next one.

Defining the Node Blueprint

In C, we can't just "make" a node; we have to define what one looks like using a struct. Each node needs to hold the actual data you care about and a pointer to another struct of the same type. This is called a self-referential structure.

typedef struct Node {
    int data;           // The "secret message"
    struct Node* next;  // The "directions to the next slip"
} Node;

I prefer using a typedef here. It saves us from writing struct Node every single time we declare a variable, which makes the code much cleaner as the logic gets more complex.

Stitching Nodes Together

To get the list started, you only need to keep track of one thing: the head. The head is just a pointer to the first node. If the head is NULL, your list is empty.

Adding a new element to the front of the list is the most efficient way to grow it. You create a new node, point its next pointer to the current head, and then tell the head to point to this new node. It's a quick swap that doesn't require shifting any other elements around.

void push(Node** head_ref, int new_data) {
    // 1. Allocate memory for the new node
    Node* new_node = (Node*)malloc(sizeof(Node));
    
    // 2. Put in the data
    new_node->data = new_data;
    
    // 3. Make the new node point to the old head
    new_node->next = (*head_ref);
    
    // 4. Move the head to point to the new node
    (*head_ref) = new_node;
}

Notice I used Node** head_ref. I'm passing a pointer to the head pointer because we need to actually change the head's address in the calling function. If I just passed Node* head, I'd be changing a local copy, and the original head back in main() would still be pointing to the old starting position.

Walking the Chain

To see what's inside your list, you "traverse" it. You start at the head and follow the next pointers in a loop until you hit NULL. This is the "The End" slip of paper from our analogy.

void printList(Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

Tearing it All Down

Here is where I see most people mess up. You can't just free(head) and call it a day. If you do that, you've deleted the first node, but you've also deleted the only pointer you had to the second node. You've just created a massive memory leak.

You have to be careful: save the pointer to the next node before you kill the current one.

void deleteList(Node** head_ref) {
    Node* current = *head_ref;
    Node* next;

    while (current != NULL) {
        next = current->next; // Save the next node
        free(current);        // Now it's safe to delete the current one
        current = next;       // Move to the saved next node
    }
    *head_ref = NULL;
}

📋 Practical Task

Implementing a "Pop" Function to Remove the Head

Now that you know how to push nodes onto a linked list, I want you to write the opposite. Create a function called pop that removes the first node (the head) from the list and returns the data that was stored inside it.

Requirements:

• The function signature should be: int pop(Node** head_ref).
• You must handle the case where the list is already empty (perhaps by printing an error or returning a sentinel value like -1).
• Crucially, you must free() the memory of the removed node to avoid leaks.
• The head_ref must be updated so the second node in the list becomes the new head.

Test your function by pushing three numbers (10, 20, 30) onto a list, then calling pop and printing the returned value to ensure you get 30 back first.