Traversal and Printing a Linked List in DSA Javascript - Time & Space Complexity

Time Complexity: Traversal and Printing a Linked List

O(n)

Understanding Time Complexity

When we walk through a linked list to print its values, we want to know how long this takes as the list grows.

We ask: How does the time to print all items change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function printLinkedList(head) {
  let current = head;
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}
    

This code walks through each node in the linked list and prints its value one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: Exactly once per node, so as many times as there are nodes in the list.

How Execution Grows With Input

As the list gets longer, the number of print steps grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	10 steps to print all nodes
100	100 steps to print all nodes
1000	1000 steps to print all nodes

Pattern observation: The work grows evenly as the list grows; doubling the list doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to print all nodes grows in a straight line with the number of nodes.

Common Mistake

[X] Wrong: "Since we only print one node at a time, the time is constant O(1)."

[OK] Correct: Even though each print is quick, we do it for every node, so total time depends on how many nodes there are.

Interview Connect

Understanding how simple traversals scale helps you reason about more complex linked list operations and shows you can analyze code clearly.

Self-Check

"What if we added a nested loop inside the traversal that compares each node to every other node? How would the time complexity change?"

Practice

1. What does it mean to traverse a linked list?

easy

A. To add a new node at the end of the list

B. To delete the first node of the list

C. To visit each node in the list one by one from start to end

D. To reverse the order of nodes in the list

Solution

1. Step 1: Understand traversal meaning

   Traversal means going through each element in a data structure in order.

2. Step 2: Apply to linked list

   For a linked list, traversal means visiting each node from the first to the last.

3. Final Answer:

   To visit each node in the list one by one from start to end -> Option C

4. Quick Check:

   Traversal = Visit nodes in order [OK]

Hint: Traversal means visiting nodes one by one [OK]

Common Mistakes:

• Confusing traversal with insertion or deletion
• Thinking traversal changes the list order
• Assuming traversal skips nodes

2. Which of the following is the correct way to start traversing a singly linked list in JavaScript?

easy

A. let current = head;

B. let current = tail;

C. let current = null;

D. let current = head.next.next;

Solution

1. Step 1: Identify the start of the list

   The traversal starts from the first node, called head.

2. Step 2: Assign current pointer

   Setting current = head means we start visiting from the first node.

3. Final Answer:

   let current = head; -> Option A

4. Quick Check:

   Start traversal at head [OK]

Hint: Traversal always starts at head node [OK]

Common Mistakes:

• Starting at tail which is the last node
• Starting at null which means no node
• Skipping nodes by starting at head.next.next

3. What will be the output of the following code snippet?

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

const head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);

let current = head;
let result = '';
while (current !== null) {
  result += current.value + ' -> ';
  current = current.next;
}
result += 'null';
console.log(result);

medium

A. null -> 1 -> 2 -> 3

B. 1 -> 2 -> 3 -> null

C. 1 -> 2 -> 3

D. 3 -> 2 -> 1 -> null

Solution

1. Step 1: Trace the linked list nodes

   The list has nodes with values 1, 2, and 3 linked in order.

2. Step 2: Follow the while loop

   The loop appends each node's value followed by ' -> ' until current is null, then adds 'null'.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Print nodes in order with arrow and null [OK]

Hint: Follow each node and append value with arrow [OK]

Common Mistakes:

• Forgetting to add 'null' at the end
• Printing nodes in reverse order
• Missing arrows between nodes

4. The following code is intended to print all values in a linked list. What is the error?

let current = head;
while (current.next !== null) {
  console.log(current.value);
  current = current.next;
}

medium

A. It will print undefined values

B. It will cause an infinite loop

C. It will throw a syntax error

D. It will skip printing the last node's value

Solution

1. Step 1: Analyze the loop condition

   The loop runs while current.next is not null, so it stops before last node.

2. Step 2: Check which nodes get printed

   It prints current.value inside loop, so last node (where current.next is null) is not printed.

3. Final Answer:

   It will skip printing the last node's value -> Option D

4. Quick Check:

   Loop condition excludes last node [OK]

Hint: Use current !== null to include last node [OK]

Common Mistakes:

• Using current.next !== null instead of current !== null
• Assuming last node is printed
• Confusing loop condition with syntax error

5. You want to print a linked list in reverse order without modifying the list or using extra arrays. Which approach is best?

hard

A. Use recursion to traverse to the end, then print on return

B. Traverse normally and print values as you go

C. Reverse the list first, then print

D. Use a loop with current.next !== null condition

Solution

1. Step 1: Understand the problem constraints

   We cannot modify the list or use extra arrays, so reversing or storing values is not allowed.

2. Step 2: Use recursion to print in reverse

   Recursion goes to the end of the list, then prints values on the way back, achieving reverse order without extra storage.

3. Final Answer:

   Use recursion to traverse to the end, then print on return -> Option A

4. Quick Check:

   Recursion prints reverse without extra space [OK]

Hint: Recursion prints reverse by returning from end [OK]

Common Mistakes:

• Trying to reverse list which modifies it
• Using loops that print forward only
• Using extra arrays which is disallowed