Traversing and Printing a Linked List

In the last lesson, you successfully implemented a function to insert a new node at the head of a linked list. We used a helper function, printList, to see the result of our insertions. Now, it's time to put that helper function under the microscope. The process of visiting each node in a list to read its contents is called traversal, and it is one of the most fundamental operations you will perform on any data structure.

Today, your goal is to implement a function to traverse a linked list and print its elements. You will learn the core algorithm for walking through a list from start to finish and understand the C code that makes it happen. This will solidify your mental model of how linked lists are structured and accessed.

1. The Traversal Algorithm

Conceptually, traversing a linked list is like a train conductor walking from the engine through each car until they reach the caboose. The conductor starts at the first car, does their work, and then moves to the next car, repeating the process until there are no more cars to visit.

In our case, the "conductor" is a temporary pointer.

The algorithm for traversal is as follows:

1. Start at the beginning: Create a temporary pointer that points to the same node as the head pointer. Let's call this pointer current.
2. Check if we're done: Create a loop that continues as long as current is not NULL. A NULL pointer means we've reached the end of the list.
3. Process the node: Inside the loop, perform the desired action on the current node. For our printList function, this means printing the value of current->data.
4. Move to the next node: Update current to point to the next node in the list by assigning current = current->next.

The loop then repeats from step 2. Once current becomes NULL, the loop terminates, and the traversal is complete.

2. Implementing Traversal in C

Let's translate this algorithm into a C function. In the previous lesson, our insertAtHead function needed a pointer-to-a-pointer (struct node **) because it had to modify the original head pointer.

Traversal, however, is a read-only operation. We are only reading the data and following the next pointers. We have no need to change the head pointer itself. Therefore, we can simply pass the head pointer by value (struct node *).

The article below provides a clear, concise implementation of a function to print a list's contents.

Based on that reading and our previous work, here is the full function integrated with our existing node definition.

// We use the same node structure as before
struct node {
    int data;
    struct node *next;
};

/*
 * Traverses a linked list from the head and prints the data of each node.
 * head: A pointer to the first node of the list.
 */
void printList(struct node *head) {
    // 1. Create a temporary 'current' pointer and initialize it with the head.
    struct node *current = head;

    // 2. Loop as long as the current pointer is not NULL.
    while (current != NULL) {
        // 3. Print the data of the node pointed to by 'current'.
        printf("%d -> ", current->data);

        // 4. Move 'current' to the next node.
        current = current->next;
    }

    // Print "NULL" at the end to signify the end of the list.
    printf("NULL\n");
}

This function elegantly handles an empty list as well. If head is passed in as NULL, the while loop condition (current != NULL) will be false immediately, and the function will simply print "NULL" — the correct representation of an empty list.

3. A Nuance in Traversal Logic

When implementing traversal, you might see two different while loop conditions:

1. while (current != NULL)
2. while (current->next != NULL)

While the second version seems plausible, it has a key drawback. It stops the loop when current is pointing to the last node (since its next is NULL). This means the loop itself doesn't process the final node, forcing you to add an extra printf statement after the loop to handle it. The first approach is cleaner and more robust.

The following reading elaborates on this exact point.

4. Video Walkthrough

To see this code in action with a visual step-by-step trace, let's watch a short video that walks through the execution of a printing function.

5. Your Turn: Putting It All Together

Now, let's combine the insertAtHead function from our previous lesson with the printList function we've just analyzed.

Exercise:
Write a full main function that does the following:

1. Initializes an empty linked list by creating a struct node *head and setting it to NULL.
2. Uses insertAtHead to add the following numbers to the list, in this order: 90, 17, 3.
3. Calls printList to display the final state of the list.

Based on what you learned about insertAtHead, what do you expect the final printed output to be?

3 -> 17 -> 90 -> NULL

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

// The node structure
struct node {
    int data;
    struct node *next;
};

// The insertion function from the previous lesson
void insertAtHead(struct node **head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// The traversal and printing function for this lesson
void printList(struct node *head) {
    struct node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Main function to drive the program
int main() {
    // 1. Start with an empty list
    struct node *head = NULL;

    // 2. Insert nodes at the head
    insertAtHead(&head, 90);
    insertAtHead(&head, 17);
    insertAtHead(&head, 3);

    // 3. Print the final list
    printf("Final list: ");
    printList(head);

    return 0;
}

Conclusion

You have now mastered the fundamental algorithm for traversing a linked list. This pattern of using a temporary pointer to iterate from the head until you reach NULL is a cornerstone of nearly every other linked list operation.

Key Takeaways:

• Traversal is the process of visiting each node in a list sequentially.
• The core algorithm uses a temporary pointer, initialized to head, which is advanced (current = current->next) inside a while (current != NULL) loop.
• Traversal is a read-only operation, so the function only needs a struct node * parameter, not a struct node **.
• The while (current != NULL) condition is generally preferred because it correctly handles both empty lists and the last node without requiring extra code.

Preview of the Next Lesson:
Now that you can traverse a list, what if you wanted to find a specific item? In the next lesson, you will build directly on today's topic to implement a function to search for a value within a linked list. The logic will feel very familiar, but with an added conditional check inside the loop.