Traversal and Printing a Linked List in DSA Python - Execution Trace

Concept Flow - Traversal and Printing a Linked List

Start at head node

↓

Is current node None?

Yes→Stop traversal

No↓

Print current node data

↓

Move to next node

↩Back to check current node

Start from the first node, print its data, move to the next node, repeat until no nodes left.

Execution Sample

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

current = head
while current:
    print(current.data)
    current = current.next

This code prints all data values in the linked list by moving from head to the end.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start at head	1 -> 2 -> 3 -> None	current = head (Node 1)	current -> 1 -> 2 -> 3 -> None
2	Print current.data	1 -> 2 -> 3 -> None	No change	Print: 1 current -> 1 -> 2 -> 3 -> None
3	Move to next node	1 -> 2 -> 3 -> None	current = current.next (Node 2)	current -> 2 -> 3 -> None
4	Print current.data	1 -> 2 -> 3 -> None	No change	Print: 2 current -> 2 -> 3 -> None
5	Move to next node	1 -> 2 -> 3 -> None	current = current.next (Node 3)	current -> 3 -> None
6	Print current.data	1 -> 2 -> 3 -> None	No change	Print: 3 current -> 3 -> None
7	Move to next node	1 -> 2 -> 3 -> None	current = current.next (None)	current -> None
8	Check current is None	1 -> 2 -> 3 -> None	No change	Traversal ends

💡 current becomes None, traversal stops

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
current	head (Node 1)	Node 1	Node 2	Node 3	None	None

Key Moments - 3 Insights

Why do we check if current is None before printing?

Because when current is None, it means we reached the end of the list and there is no data to print. See step 8 in execution_table where traversal stops.

Why do we move current to current.next after printing?

To go to the next node in the list. If we don't move, we would print the same node repeatedly. See steps 3, 5, and 7 where current moves forward.

What happens if the list is empty (head is None)?

The loop never runs because current starts as None. So nothing is printed and traversal ends immediately, like step 8 but from the start.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 5?

A None

B Node 2

C Node 3

D Node 1

💡 Hint

Check the 'Pointer Changes' column at step 5 in execution_table.

At which step does the traversal stop because current becomes None?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table for when current is None.

If the linked list had only one node, how many times would the print operation run?

A 1 time

B 0 times

C 2 times

D 3 times

💡 Hint

Refer to variable_tracker and execution_table to see how many nodes are printed.

Concept Snapshot

Traversal and Printing a Linked List:
- Start at head node
- While current node is not None:
  - Print current node's data
  - Move to next node
- Stop when current is None
This prints all nodes in order.

Full Transcript

Traversal and printing a linked list means starting at the first node called head. We check if the current node exists. If yes, we print its data and move to the next node. We repeat this until we reach the end where current is None. If the list is empty, nothing prints. This process ensures all nodes are visited and their data shown in order.

Practice

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

easy

A. To reverse the order of nodes in the list

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

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

D. To delete the first node of the list

Solution

1. Step 1: Understand traversal meaning

   Traversal means visiting each element in order to read or process it.

2. Step 2: Apply to linked list context

   In a linked list, traversal means starting at the head and moving through each node until the end.

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 sequentially [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 syntax to start traversing a linked list in Python if the head node is named head?

easy

A. current = head
while current != head:
print(current.data)
current = current.next

B. current = head
while current.next is not None:
print(current.data)
current = current.next

C. current = head
for i in range(len(head)):
print(current.data)
current = current.next

D. current = head
while current is not None:
print(current.data)
current = current.next

Solution

1. Step 1: Understand traversal loop condition

   We must continue while current node exists (not None) to visit all nodes.

2. Step 2: Check each option's loop condition

   current = head while current is not None: print(current.data) current = current.next uses while current is not None, which correctly visits all nodes including the last one.

3. Final Answer:

   current = head while current is not None: print(current.data) current = current.next -> Option D

4. Quick Check:

   Loop until current is None [OK]

Hint: Traverse while current is not None [OK]

Common Mistakes:

• Stopping before last node by checking current.next
• Using for loop with range on linked list
• Loop condition that never ends or skips nodes

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

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

current = head
while current is not None:
    print(current.data, end=' -> ')
    current = current.next
print('None')

medium

A. 10 -> 20 -> 30 -> None

B. 10 20 30 None

C. None -> 10 -> 20 -> 30

D. 10 -> 20 -> None

Solution

1. Step 1: Trace the linked list nodes

   Nodes contain 10, 20, 30 linked in order: 10 -> 20 -> 30 -> None.

2. Step 2: Follow the print loop

   Loop prints each node's data followed by ' -> ', then prints 'None' after loop ends.

3. Final Answer:

   10 -> 20 -> 30 -> None -> Option A

4. Quick Check:

   Print nodes with arrows ending with None [OK]

Hint: Print each node data with arrow until None [OK]

Common Mistakes:

• Missing 'None' at the end
• Printing nodes without arrows
• Stopping before last node

4. The following code is intended to print all elements of a linked list, but it causes an error. What is the error?

current = head
while current.next is not None:
    print(current.data)
    current = current.next
print(current.data)

medium

A. It causes an infinite loop

B. It misses printing the last node inside the loop

C. It raises an AttributeError

D. It prints nodes in reverse order

Solution

1. Step 1: Analyze loop condition

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

2. Step 2: Check printing after loop

   After loop, it prints the last node's data separately, so all nodes are printed but last node outside loop.

3. Final Answer:

   It misses printing the last node inside the loop -> Option B

4. Quick Check:

   Loop condition skips last node printing [OK]

Hint: Use while current is not None to include last node [OK]

Common Mistakes:

• Using current.next in loop condition
• Expecting all nodes printed inside loop
• Confusing infinite loop with this error

5. You want to print a linked list in reverse order without modifying the list or using extra space like a stack. Which approach below correctly achieves this using recursion?

def print_reverse(node):
    if node is None:
        return
    # What goes here?
    print(node.data, end=' -> ')

hard

A. print_reverse(node.next)

B. print(node.data)
print_reverse(node.next)

C. print_reverse(node)
print(node.data)

D. print_reverse(node.next)
print_reverse(node)

Solution

1. Step 1: Understand recursion for reverse print

   Recursively call function on next node first to reach end before printing.

2. Step 2: Place recursive call before print

   Calling print_reverse(node.next) before printing current node prints in reverse order.

3. Final Answer:

   print_reverse(node.next) -> Option A

4. Quick Check:

   Recursive call before print reverses order [OK]

Hint: Call recursion on next node before printing current [OK]

Common Mistakes:

• Printing before recursive call (prints forward)
• Calling recursion on same node (infinite recursion)
• Calling recursion twice causing errors