Traversal and Printing a Linked List in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of traversing a linked list?

To visit each node in the linked list one by one, usually to read or print the data stored in each node.

beginner

In a singly linked list, how do you move from one node to the next?

By following the 'next' pointer/reference in the current node to reach the next node.

beginner

What condition tells you that you have reached the end of a linked list during traversal?

When the 'next' pointer/reference of the current node is null, it means there are no more nodes to visit.

intermediate

Why can't you access elements by index directly in a linked list like in an array?

Because linked lists do not store elements in contiguous memory locations, so you must traverse nodes one by one to reach a specific position.

beginner

What is the output format when printing a linked list as '1 -> 2 -> 3 -> null'?

It shows the sequence of node values connected by arrows, ending with 'null' to indicate the list's end.

What does the 'next' pointer in a linked list node represent?

A The address of the next node in the list

B The value stored in the node

C The total number of nodes

D The previous node in the list

The 'next' pointer holds the reference to the next node, allowing traversal through the list.

How do you know when to stop traversing a singly linked list?

A When the current node's value is zero

B After visiting 10 nodes

C When the current node's next pointer is null

D When the current node points to itself

Traversal stops when the next pointer is null, indicating the end of the list.

Which of these is a correct way to print all elements of a linked list?

A Print nodes in reverse order without traversal

B Print the head node only

C Use an index to access nodes directly

D Start at head and follow next pointers until null, printing each node's value

You must start at the head and follow each next pointer until you reach null, printing values along the way.

What will happen if you forget to move to the next node during traversal?

A You will skip nodes

B The traversal will loop infinitely on the same node

C The traversal will end immediately

D The list will be reversed

Not moving to the next node causes an infinite loop because you keep visiting the same node.

What is the time complexity of traversing a linked list with n nodes?

A O(n)

B O(1)

C O(n^2)

D O(log n)

You visit each node once, so traversal takes linear time proportional to the number of nodes.

Explain step-by-step how to traverse and print all elements of a singly linked list.

Think about visiting each node one by one until you reach the end.

Describe why linked lists require traversal to access elements, unlike arrays.

Compare how arrays and linked lists store data.

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