Inserting Nodes in a Linked List

Inserting at the Head of the List

Inserting a node at the head, or front, of the list is the fastest and most fundamental insertion operation. The logic is straightforward:

1. Create a new node.
2. Set the new node's next pointer to point to the current head of the list.
3. Update the list's head pointer to point to our newly created node.

It's crucial to perform these steps in the correct order. If you change the head pointer first, you lose the only link to the rest of the list! The following video provides an excellent, detailed walkthrough of this process.

This diagram shows the steps for inserting a node at the front. A new node is created. Its next pointer is linked to the old head. Finally, the list's head pointer is updated to point to the new node, making it the new first element.

The Challenge: Modifying the Head Pointer

Now, let's consider how to write a function, say insertAtFront(), to do this. This function needs to be able to change the head pointer that exists back in our main() function. Given your experience with C from CS50, you might recall that function arguments are passed by value. If we pass head (which is a node_t *) to our function, we're only passing a copy of the pointer. Changing this copy inside the function will have no effect on the original head in main.

This is a classic C problem with a standard, elegant solution: passing a pointer to the pointer. Instead of passing node_t *head, we pass node_t **head_ptr. This gives our function the memory address of the original head pointer, allowing us to dereference it and modify it directly.

This is a significant concept. While we have a later lesson dedicated to double pointers, its most common use case is right here, and using it is the professional way to implement this function.

Here is a complete C function that correctly implements insertion at the front using a double pointer.

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

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

// Note the use of node_t **head_ref
void insertAtFront(node_t **head_ref, int new_data) {
    // 1. Allocate the new node
    node_t *new_node = malloc(sizeof(node_t));
    if (new_node == NULL) {
        // In a real game, you'd handle this more gracefully
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(EXIT_FAILURE);
    }
    
    // 2. Put in the data
    new_node->data = new_data;

    // 3. Make next of new node as the old head
    //    We dereference head_ref to get the actual head pointer
    new_node->next = *head_ref;

    // 4. Move the head to point to the new node
    //    We change the value at the address of the head pointer
    *head_ref = new_node;
}

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

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

    insertAtFront(&head, 10); // Pass the address of head
    insertAtFront(&head, 20);
    insertAtFront(&head, 30);

    printList(head); // Output: 30 -> 20 -> 10 -> NULL

    // Remember to free the list later! (We'll cover this in a future lesson)
    return 0;
}

Inserting at the Tail of the List

What if we want to add an item to the end of our inventory? This operation, insertAtEnd(), requires a different approach. Since we only have a head pointer, we can't jump directly to the end. We must traverse the list.

The algorithm is:

1. Create the new node and set its next pointer to NULL, as it will be the new last node.
2. Special Case: If the list is empty (head == NULL), the new node is both the first and last node. Simply set head to the new node.
3. If the list is not empty, start a temporary pointer (current) at the head.
4. Loop through the list, advancing the pointer (current = current->next) until you find the last node. The last node is the one whose next pointer is NULL.
5. Once at the last node, update its next pointer to point to your new node.

The video from Jenny's Lectures also covers this case very well. Pay special attention to the loop condition she uses for traversal.

Here is the corresponding C function. Notice that for this function, we don't necessarily need a double pointer. We only modify the head in the special case of an empty list, a change that we can handle by returning the new head pointer if we wanted, but the double-pointer approach remains consistent and robust.

void insertAtEnd(node_t **head_ref, int new_data) {
    // 1. Allocate and initialize the new node
    node_t *new_node = malloc(sizeof(node_t));
    if (new_node == NULL) { exit(EXIT_FAILURE); }
    new_node->data = new_data;
    new_node->next = NULL; // This will be the last node

    // 2. If the list is empty, make the new node the head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    // 3. Else, traverse till the last node
    node_t *last = *head_ref;
    while (last->next != NULL) {
        last = last->next;
    }

    // 4. Change the next of the current last node
    last->next = new_node;
}

Inserting into a Sorted List

For many game applications, like a high-score table or an inventory sorted by item value, we need to insert new elements while preserving the list's order. This is the most complex of the three insertion types because it involves finding the correct position before performing the insertion.

In a sorted list, inserting a new element (e.g., 12) requires finding the correct spot (between 9 and 19) to maintain the ascending order.

The algorithm for insertInOrder() has several cases:

1. The list is empty, or the new node's value is smaller than the head's value. In this case, the new node becomes the new head. We can simply reuse our insertAtFront() logic.
2. The new node's value belongs somewhere in the middle of the list or at the end. We must traverse the list to find the correct insertion point. We need to stop at the node before the insertion point.

The traversal logic is key: we need a current pointer and we loop as long as current->next is not NULL and current->next->data is less than our new data. This "look-ahead" technique lets us stop at the perfect spot to insert our new node.

To solidify your understanding with a textual reference that covers all edge cases in detail, review the following reading.

Here is a complete function that combines these cases:

void insertInOrder(node_t **head_ref, int new_data) {
    node_t *current = *head_ref;
    
    // Special case: list is empty or new node goes at the front
    if (current == NULL || current->data >= new_data) {
        insertAtFront(head_ref, new_data);
        return;
    }

    // Locate the node before the point of insertion
    while (current->next != NULL && current->next->data < new_data) {
        current = current->next;
    }

    // Now, 'current' is the node after which we need to insert.
    // Let's create the new node.
    node_t *new_node = malloc(sizeof(node_t));
    if (new_node == NULL) { exit(EXIT_FAILURE); }
    new_node->data = new_data;

    // Perform the insertion
    new_node->next = current->next;
    current->next = new_node;
}

Conclusion

In this lesson, you've built the essential toolkit for populating a linked list. You now have functions to add nodes in the three most critical ways, moving far beyond the manual pointer manipulation of our last session.

Key Takeaways:

• Insertion at the Head: The fastest method. It requires updating the head pointer itself, making the use of a double pointer (node_t **) the most robust C implementation.
• Insertion at the Tail: Requires traversing the entire list to find the last node. You must handle the special case of an empty list. The correct traversal condition is while (current->next != NULL).
• Sorted Insertion: The most complex case. It involves a "look-ahead" traversal (current->next->data < value) to find the node before the insertion point, and requires special handling for insertion at the very beginning of the list.

With the ability to add nodes, our list is no longer static. In the upcoming lesson, we will complete the core functionality by learning how to search for and delete nodes. This will give us a fully functional dynamic data structure, ready to be integrated into our game inventory system.