Inserting a Node at the Head of a Linked List

Welcome back! In our previous lesson, we established the fundamental building block of a linked list: the struct node. You learned how to define this self-referential structure in C, which contains both data and a pointer to the next node in the chain.

Now that we have our building block, it's time to start assembling a list. Today, we'll focus on one of the most common and efficient operations for a linked list: adding a new element to the very front. Your goal is to implement a function to insert a new node at the head of a linked list. This is a key operation that highlights a major advantage of linked lists over static arrays.

1. The Logic of Inserting at the Head

The process of inserting a node at the beginning of a list, often called "pushing" or "prepending," involves just three logical steps. Let's assume we have an existing list (which might be empty) and we want to add a new node.

The steps are:

1. Create a new node: Dynamically allocate memory for a struct node and store the desired data in it.
2. Link the new node to the list: Set the next pointer of your new node to point to the current head of the list. If the list was empty, head would be NULL, so the new node's next pointer correctly becomes NULL.
3. Update the head: Change the head pointer of the list so that it now points to your newly created node. This new node is now the official start of the list.

This sequence is crucial. If you update the head pointer before you link the new node, you will lose the connection to the rest of the list!

2. The Challenge: Modifying head from a Function

This logic seems straightforward, but implementing it in a C function reveals a classic C programming challenge. The head pointer is the single entry point to our entire list. To add a new node at the beginning, we must change the value of the head pointer itself.

Recall from Module 4 that C passes function arguments by value. If we pass the head pointer to our insertion function, we are only passing a copy of its address. Modifying this copy inside the function will have no effect on the original head pointer in our main function.

Let's examine an article that explains this problem clearly.

As the article demonstrates, we need a way for our insertion function to modify a variable that lives outside of it—specifically, the head pointer in main.

3. The C Solution: A Pointer to a Pointer

How do we modify a variable in a calling function? We pass its address.

The variable we want to modify is head, which has the type struct node *. Therefore, its address has the type struct node **—a pointer to a pointer to a node. By passing this "double pointer" to our function, we give it the ability to reach back into main and change where the original head pointer is pointing.

This concept can be tricky, so let's watch a video that walks through this exact transition.

4. Implementing the insertAtHead Function

Let's synthesize what we've learned into a complete, robust function. Here is how you would write an insertAtHead function using a double pointer.

#include <stdio.h>
#include <stdlib.h>

// The node structure we defined in the previous lesson
struct node {
    int data;
    struct node *next;
};

/*
 * Inserts a new node at the front of the list.
 * head_ref: A pointer to the head pointer of the list.
 * new_data: The integer data for the new node.
 */
void insertAtHead(struct node **head_ref, int new_data) {
    // 1. Allocate memory for the new node
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return; // Or handle the error appropriately
    }

    // 2. Assign data to the new node
    new_node->data = new_data;

    // 3. Set the 'next' of the new node to the current head
    // We dereference head_ref once (*) to get the actual head pointer
    new_node->next = (*head_ref);

    // 4. Move the head to point to the new node
    // We dereference head_ref once to change the actual head pointer
    (*head_ref) = new_node;
}

// A utility function to print the linked list
void printList(struct node *node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

Let's break down the key lines involving the double pointer head_ref:

• void insertAtHead(struct node **head_ref, ...): The function signature accepts a pointer-to-a-pointer.
• new_node->next = (*head_ref);: We use *head_ref to access the value that head_ref points to. This value is the original head pointer from main. We are setting the new node's next field to point where the old head pointed.
• (*head_ref) = new_node;: This is the most important step. We are changing the value of the original head pointer in main to be the address of our new_node.

Your Turn: Putting It All Together

Now it's your turn to use this function. Create a main function that demonstrates inserting nodes at the head.

Exercise:

1. In your main function, declare a head pointer and initialize it to NULL to represent an empty list.
2. Call insertAtHead three times to add the values 30, 20, and then 10 to the list. Remember to pass the address of the head pointer using the & operator.
3. After all insertions, call printList to display the final state of your linked list.

If you do this correctly, what output do you expect from printList? Think about the order of insertions.

10 -> 20 -> 30 -> NULL

int main() {
    // Start with an empty list
    struct node *head = NULL;

    printf("Initial list: ");
    printList(head);

    printf("Inserting 30...\n");
    insertAtHead(&head, 30);
    printList(head);

    printf("Inserting 20...\n");
    insertAtHead(&head, 20);
    printList(head);
    
    printf("Inserting 10...\n");
    insertAtHead(&head, 10);
    printList(head);

    return 0;
}

Conclusion

In this lesson, you've implemented your first function to manipulate a linked list. You have not only learned the simple logic behind inserting a node at the head but also tackled the important C-specific challenge of modifying a pointer via a function call.

Key Takeaways:

• Inserting at the head of a linked list is a three-step process: create a new node, link it to the current head, and update the head to be the new node.
• This operation is very efficient, with a time complexity of O(1), as it doesn't depend on the number of elements in the list.
• To modify the head pointer from within a function in C, you must pass a pointer to it (struct node **).
• You use the dereference operator (*) to access and modify the original head pointer from within the function.

Preview of the Next Lesson:
We used a printList function today to verify our work. In the next lesson, we will formally focus on this operation. You will learn how to implement a function to traverse a linked list from head to tail and print its elements, which is another fundamental linked list operation.