Why Traversal and Printing a Linked List in DSA Javascript?

The Big Idea

What if you could see every item in a long chain without losing your place or missing any?

The Scenario

Imagine you have a long chain of paper clips linked together, and you want to count or see each paper clip one by one. Doing this by hand means picking up each clip, looking at it, then moving to the next. If the chain is very long, this becomes tiring and slow.

The Problem

Manually checking each paper clip is slow and easy to lose track. You might skip some clips or count the same clip twice. It's hard to keep your place without a clear way to move from one clip to the next.

The Solution

Traversal in a linked list is like having a finger pointing to each paper clip in order. You start at the first clip and move your finger smoothly to the next until you reach the end. This way, you can easily see or print each item without missing or repeating.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This lets you easily access and display every item in a linked list, no matter how long, without losing track or making mistakes.

Real Life Example

Think of a playlist of songs on your phone. Traversing the linked list is like playing each song one after another, making sure none are skipped or repeated.

Key Takeaways

Manual checking is slow and error-prone.

Traversal moves step-by-step through the list safely.

Printing shows all items clearly and in order.

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