Traversal and Printing a Linked List in DSA C

Mental Model

We start at the first item and move step-by-step to the next until we reach the end.

Analogy: Like reading a chain of paper clips one by one from the first to the last without skipping any.

head -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, print all values

Goal: Print all values in the list from start to end in order

Step 1: Start at the first node with value 1

head -> [1 ↑] -> [2] -> [3] -> null

Why: We begin printing from the first node

Step 2: Print value 1 and move to next node

head -> [1] -> [2 ↑] -> [3] -> null

Why: After printing current, move to next to continue

Step 3: Print value 2 and move to next node

head -> [1] -> [2] -> [3 ↑] -> null

Why: Continue printing each node in order

Step 4: Print value 3 and move to next node

head -> [1] -> [2] -> [3] -> null ↑

Why: Print last node and reach end (null)

Result:

head -> [1] -> [2] -> [3] -> null
Printed output: 1 2 3 

Annotated Code

DSA C

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

// Define node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Function to print the linked list
void printList(Node* head) {
    Node* current = head; // Start at head
    while (current != NULL) { // Traverse until end
        printf("%d ", current->data); // Print current node's data
        current = current->next; // Move to next node
    }
    printf("\n");
}

int main() {
    // Create linked list 1 -> 2 -> 3 -> null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);

    // Print the list
    printList(head);

    // Free memory
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Node* current = head; // Start at head

Initialize pointer to start traversal from first node

while (current != NULL) { // Traverse until end

Continue until we reach the end of the list

printf("%d ", current->data); // Print current node's data

Output the value stored in current node

current = current->next; // Move to next node

Advance pointer to next node to continue traversal

Output

1 2 3 

Complexity Analysis

Time: O(n) because we visit each of the n nodes exactly once

Space: O(1) because we only use a single pointer variable regardless of list size

vs Alternative: Compared to recursive printing which uses O(n) space on call stack, this iterative approach is more space efficient

Edge Cases

Empty list (head is NULL)

No output is printed, function exits immediately

DSA C

while (current != NULL) {

Single node list

Prints the single node's value and stops

DSA C

while (current != NULL) {

When to Use This Pattern

When you need to visit every item in a linked list in order, use traversal with a pointer moving from head to null.

Common Mistakes

Mistake: Not checking for NULL before accessing node data causing crashes
Fix: Always check current != NULL in the loop condition before accessing current->data

Mistake: Advancing pointer before printing causing skipped nodes
Fix: Print current node's data before moving pointer to next

Summary

It visits each node from start to end and prints its value.

Use it when you want to see or process all elements in a linked list.

Remember to move step-by-step from one node to the next until you reach the end.

Practice

1. What is the main purpose of traversing a linked list in C?

easy

A. To delete the entire linked list

B. To visit each node and access its data

C. To create a new linked list

D. To reverse the linked list

Solution

1. Step 1: Understand traversal meaning

   Traversal means visiting each node one by one in the linked list.

2. Step 2: Identify traversal purpose

   The main goal is to access or print the data stored in each node.

3. Final Answer:

   To visit each node and access its data -> Option B

4. Quick Check:

   Traversal = Visit nodes [OK]

Hint: Traversal means visiting nodes to read data [OK]

Common Mistakes:

• Confusing traversal with deletion
• Thinking traversal creates new nodes
• Assuming traversal reverses the list

2. Which of the following is the correct syntax to start traversing a linked list named head in C?

easy

A. Node* temp = &head;

B. struct Node temp = head;

C. struct Node* temp = head;

D. Node temp = head;

Solution

1. Step 1: Understand pointer usage

   In C, linked list nodes are accessed via pointers, so temp must be a pointer to Node.

2. Step 2: Check syntax correctness

   struct Node* temp = head; correctly declares temp as a pointer and assigns it to head.

3. Final Answer:

   struct Node* temp = head; -> Option C

4. Quick Check:

   Pointer assignment = struct Node* temp = head [OK]

Hint: Use pointer variable to traverse linked list [OK]

Common Mistakes:

• Using struct Node instead of pointer
• Taking address of head incorrectly
• Missing struct keyword if needed

3. What will be the output of the following C code snippet that traverses and prints a linked list?

struct Node {
  int data;
  struct Node* next;
};

int main() {
  struct Node n3 = {30, NULL};
  struct Node n2 = {20, &n3};
  struct Node n1 = {10, &n2};
  struct Node* head = &n1;

  struct Node* temp = head;
  while (temp != NULL) {
    printf("%d -> ", temp->data);
    temp = temp->next;
  }
  printf("NULL\n");
  return 0;
}

medium

A. 10 -> 20 -> 30 -> NULL

B. 30 -> 20 -> 10 -> NULL

C. 10 20 30 NULL

D. Compilation error

Solution

1. Step 1: Trace linked list nodes

   The list nodes are n1(10) -> n2(20) -> n3(30) -> NULL.

2. Step 2: Follow traversal and print

   The loop prints each node's data followed by ' -> ', then prints 'NULL' at the end.

3. Final Answer:

   10 -> 20 -> 30 -> NULL -> Option A

4. Quick Check:

   Print nodes in order = 10 -> 20 -> 30 -> NULL [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Printing nodes in reverse order
• Missing '->' arrows in output
• Forgetting to print NULL at end

4. Identify the error in the following code snippet that attempts to print a linked list:

struct Node {
  int data;
  struct Node* next;
};

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

medium

A. head should be a double pointer

B. Missing semicolon after printf

C. printf format specifier is incorrect

D. The loop condition should be head != NULL

Solution

1. Step 1: Analyze loop condition

   The loop stops when head->next is NULL, so it skips printing the last node.

2. Step 2: Correct loop condition

   Changing condition to head != NULL ensures all nodes, including last, are printed.

3. Final Answer:

   The loop condition should be head != NULL -> Option D

4. Quick Check:

   Loop until head is NULL to print all nodes [OK]

Hint: Loop until pointer is NULL, not next pointer [OK]

Common Mistakes:

• Stopping loop too early
• Using wrong pointer type
• Ignoring last node in print

5. Given a linked list where some nodes may have data value 0, which of the following code snippets correctly prints all nodes including those with 0?

struct Node* temp = head;
while (temp) {
  if (temp->data) {
    printf("%d -> ", temp->data);
  }
  temp = temp->next;
}
printf("NULL\n");

hard

A. Change 'if (temp->data)' to always print without condition

B. Add 'temp = temp->next;' inside the if block only

C. Use 'while (temp != NULL)' and keep the if condition

D. Replace 'printf' with 'puts' to print zeros

Solution

1. Step 1: Understand the if condition effect

   The condition 'if (temp->data)' skips printing nodes with data 0 because 0 is false.

2. Step 2: Fix to print all nodes

   Removing the if condition prints all nodes including those with 0.

3. Final Answer:

   Change 'if (temp->data)' to always print without condition -> Option A

4. Quick Check:

   Print all nodes regardless of data value [OK]

Hint: Do not skip nodes with zero data when printing [OK]

Common Mistakes:

• Skipping zero values due to if condition
• Moving pointer only inside if block causing infinite loop
• Using wrong print function for integers