Data Structures & AlgorithmsTraversal, Insertion, and Deletion Patterns

Traversal, Insertion, and Deletion Patterns

LevelBeginner

Duration60 mins

TopicTraversal, Insertion, and Deletion Patterns

1 / 4

Traversing with a Current Pointer

The Art of Walking Through a Linked List

Imagine you're in a treasure hunt where each clue leads only to the next clue. You can't see all the clues laid out on a table—you must follow them one by one, each clue revealing the location of the next. This is precisely how traversal works in a linked list: you start at the beginning and follow the chain of pointers, visiting each node in sequence until you reach the end.

Traversal is the most fundamental operation in linked list manipulation. Every other operation—searching, inserting, deleting, reversing—depends on your ability to navigate through the list. Without mastering traversal, you cannot implement any meaningful linked list algorithm.

In this page, we'll develop a deep, intuitive understanding of linked list traversal. We'll explore the "current pointer" pattern, understand why it's necessary, examine the mechanics of pointer movement, and see how this simple concept forms the foundation for all linked list operations.

Learning Objectives

By the end of this page, you will: • Understand why linked list traversal differs fundamentally from array traversal • Master the "current pointer" pattern for visiting every node • Recognize the traversal loop structure and its invariants • Identify common traversal variations and their use cases • Develop intuition for when traversal terminates and why

Why Traversal Is Different in Linked Lists

Before diving into the mechanics, let's understand why linked list traversal is fundamentally different from array traversal—and why this difference matters.

Arrays: Random Access Paradise

In an array, all elements are stored in contiguous memory locations. This means:

You can jump directly to any element using an index: arr[5] takes you straight to the 6th element.
The memory address of any element is calculable: address = base_address + (index × element_size).
Traversal is optional: If you know the index, you don't need to visit preceding elements.

Linked Lists: Sequential Access Only

In a linked list, elements are scattered across memory, connected only by pointers:

You cannot jump to an arbitrary element: There's no index that takes you directly to the 5th node.
Each node only knows about the next node: To reach node 5, you must first visit nodes 1, 2, 3, and 4.
Traversal is mandatory: Finding any element (except the head) requires walking through the list.

Array Traversal

•Use an integer index: i = 0, 1, 2, ...
•Access element directly: arr[i]
•Increment index: i++
•Index is just a number—no pointer needed
•Can start traversal anywhere: arr[5]

Linked List Traversal

•Use a pointer variable: current
•Access element: current.data
•Move to next: current = current.next
•Pointer holds memory address of current node
•Must start from head—no shortcuts

The Sequential Nature Is Not a Bug—It's a Feature

It might seem like arrays are "better" because of random access. But remember: linked lists trade random access for O(1) insertions and deletions. The sequential nature is the price we pay for that flexibility. Understanding this trade-off is essential for choosing the right data structure.

The "Current" Pointer Concept

The current pointer (sometimes called a "traversal pointer" or "iterator pointer") is a variable that holds the reference to the node we are currently visiting. It's our "finger" pointing at a position in the list.

Why Do We Need a Separate Pointer?

You might wonder: "Why not just use the head pointer to traverse?"

The answer is critical: the head pointer must always point to the first node. If we move the head pointer during traversal, we lose our reference to the beginning of the list! Once lost, we can never access the earlier nodes again (they become unreachable and eventually garbage collected in managed languages, or leaked in unmanaged languages).

The Current Pointer as a Bookmark

Think of the current pointer as a bookmark in a physical book:

The head is like knowing which book we're reading (the list's identity).
The current is like the bookmark showing which page we're on.
Moving the bookmark doesn't change which book it is—it just tracks our position.

We create a new variable, typically called current, and initialize it to point to the same node as head. Then we move current through the list while leaving head untouched.

traversal-pointer-concept
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# The fundamental traversal setup
# head points to the first node of the list
 
# CREATE a traversal pointer
# - This is a SEPARATE variable that starts at the head
# - It will move through the list
# - head remains unchanged throughout
 
current = head  # current now points to the same node as head
 
# At this point:
# - head → Node A (first node)
# - current → Node A (same first node)
# Both variables point to the SAME memory location
 
# As we traverse, only current moves:
# current = current.next  # current → Node B
# current = current.next  # current → Node C
# ...
# head still → Node A (unchanged!)

Memory Model Insight

When you write current = head, you're not copying the node—you're copying the reference (memory address). Both head and current now point to the same node in memory. When you later write current = current.next, you're changing what current points to, but head remains pointing to the original first node.

The Traversal Loop Anatomy

Now let's examine the complete traversal loop. This is a pattern you'll use hundreds of times, so understanding every part is essential.

The Standard Traversal Pattern

The traversal loop has three components:

Initialization: Set current = head
Continuation Condition: Loop while current is not null
Advancement: Move current = current.next

Let's break this down in detail:

standard-traversal-loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def traverse(head):
    """
    Complete traversal of a linked list using the current pointer pattern.
    
    This function visits every node in the list exactly once,
    printing each node's data.
    """
    
    # STEP 1: INITIALIZATION
    # Create the traversal pointer, starting at the head
    current = head
    
    # STEP 2: CONTINUATION CONDITION
    # Continue as long as current is not None (not at the end)
    while current is not None:
        
        # PROCESS: Do something with the current node
        # This is where you put your actual work
        print(current.data)
        
        # STEP 3: ADVANCEMENT
        # Move to the next node
        # This MUST be the last thing in the loop
        current = current.next
    
    # At this point, current is None
    # We've visited every node and reached the end
 
# Visualizing the traversal:
# List: [A] -> [B] -> [C] -> None
#
# Before loop:  current = [A]
# Iteration 1:  print A, current = [B]
# Iteration 2:  print B, current = [C]
# Iteration 3:  print C, current = None
# Loop ends:   current is None

Why Check `current != null`?

This condition is essential because:

Empty List Safety: If the list is empty (head is null), the loop body never executes—which is correct behavior.
Termination Detection: The last node's next pointer is null, signaling the end of the list.
Null Dereference Prevention: If we didn't check, we'd crash trying to access null.data or null.next.

Order of Operations Matters

Note the order inside the loop:

1. Process current node (print, accumulate, check condition, etc.)
2. Advance to next node

If you reverse this order (advance first, then process), you'll skip the first node and crash on the last iteration trying to process null!

Common Mistake: Advancing Before Processing

A frequent beginner error is writing:

while current is not None:
    current = current.next  # ❌ Advancing first!
    print(current.data)     # ❌ Processes next node, not current

This skips the head and crashes when current becomes None. Always process first, then advance!

Understanding Traversal Invariants

An invariant is a condition that remains true throughout the execution of an algorithm. Understanding the invariants of linked list traversal helps you write correct code and debug errors.

The Key Traversal Invariants

At the beginning of each loop iteration:

If current is not null, then current points to a valid, unvisited node.
All nodes before current have already been visited.
All nodes from current onward have not yet been visited.

At the end of the entire traversal:

current is null, meaning we've passed the last node.
Every node in the list has been visited exactly once.
head still points to the first node (unchanged).

Traversal State at Each Step
Step	current Points To	Nodes Visited	Nodes Remaining
Before loop	Node A (head)	None	A, B, C
After iteration 1	Node B	A	B, C
After iteration 2	Node C	A, B	C
After iteration 3	null	A, B, C	None

Why Invariants Matter

These invariants help you:

Prove correctness: You can verify that every node will be visited and none will be skipped.
Debug errors: If something goes wrong, check which invariant was violated.
Modify the pattern safely: When you need a variation (e.g., stopping early), you know what conditions to adjust.

Invariant Thinking Is Professional-Grade

Professional software engineers think in terms of invariants. It's not enough to write code that "seems to work." Understanding invariants allows you to prove your code is correct and to confidently modify it without introducing bugs. This is especially critical for linked list operations where pointer manipulation can easily go wrong.

Traversal Variations

While the standard while current is not null pattern covers most cases, several variations exist for specific needs. Understanding these variations equips you for real-world linked list problems.

Variation 1: Counting Elements

A common task is determining the length of a linked list. We augment the traversal with a counter:

count-elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def count_nodes(head):
    """
    Count the number of nodes in the linked list.
    
    Time Complexity: O(n) - must visit every node
    Space Complexity: O(1) - only a counter variable
    """
    count = 0
    current = head
    
    while current is not None:
        count += 1           # Increment for each node visited
        current = current.next
    
    return count
 
# Example:
# List: [A] -> [B] -> [C] -> None
# Output: 3

Variation 2: Searching for a Value

To find a specific value, we combine traversal with early termination:

search-value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def search(head, target):
    """
    Search for a target value in the linked list.
    
    Returns: The node containing target, or None if not found.
    
    Time Complexity: O(n) worst case, O(1) best case (target at head)
    Space Complexity: O(1)
    """
    current = head
    
    while current is not None:
        if current.data == target:
            return current  # Found! Return immediately
        current = current.next
    
    return None  # Not found after checking all nodes
 
# Example:
# List: [10] -> [20] -> [30] -> None
# search(head, 20) returns the node containing 20
# search(head, 99) returns None

Variation 3: Finding the Last Node

To find the tail (last node), we stop when current.next is null:

find-last-node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def find_last_node(head):
    """
    Find the last node in the linked list.
    
    Returns: The last node, or None if the list is empty.
    
    Time Complexity: O(n) - must traverse the entire list
    Space Complexity: O(1)
    """
    # Handle empty list
    if head is None:
        return None
    
    current = head
    
    # Notice the different condition: current.next != None
    # We stop AT the last node, not AFTER it
    while current.next is not None:
        current = current.next
    
    # current now points to the last node
    return current
 
# Example:
# List: [A] -> [B] -> [C] -> None
# Returns: Node C
#
# Why current.next instead of current?
# - If we use 'while current', we end up with current = None
# - We want to STOP at the last node, not go past it

Variation 4: Finding the Node Before (Predecessor)

For deletions at arbitrary positions, we often need to find the node before a target. This requires tracking a "previous" pointer:

find-predecessor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def find_predecessor(head, target):
    """
    Find the node that comes BEFORE the node containing target.
    
    This is essential for deletion operations, where we need
    to update the previous node's 'next' pointer.
    
    Returns: The predecessor node, or None if target is at head or not found.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Can't have a predecessor of the head
    if head is None or head.data == target:
        return None
    
    current = head
    
    # We look at current.next to find the target
    while current.next is not None:
        if current.next.data == target:
            return current  # current is the predecessor
        current = current.next
    
    return None  # Target not found
 
# Example:
# List: [A] -> [B] -> [C] -> None
# find_predecessor(head, 'B') returns Node A
# find_predecessor(head, 'A') returns None (no predecessor of head)

The Previous Pointer Pattern

The "previous pointer" or "predecessor" pattern is extremely important. In a singly linked list, you can only traverse forward. If you need to modify the node before the current one (as in deletion), you must keep track of it as you go. This pattern appears in many linked list problems.

The Traversal-Process-Advance Pattern

Let's crystallize the traversal pattern into a reusable mental framework. This pattern applies to almost every linked list traversal problem:

The Pattern Structure

1. INITIALIZE: Set current = head (and any auxiliary variables)
2. LOOP while current is not null:
   a. PROCESS: Do something with current node
   b. ADVANCE: Move current to current.next
3. CLEANUP: Handle any post-traversal logic

This pattern is flexible. The "PROCESS" step can be:

Printing data
Accumulating a sum
Checking a condition
Comparing with a target
Building a new structure
Any operation on the current node

Pattern Variations Based on Stopping Condition

Goal	Loop Condition	When to Use
Visit all nodes	`while current != null`	Printing, summing, transforming
Stop at last node	`while current.next != null`	Appending to tail, modifying last
Stop before target	`while current.next.data != target`	Deletion of target node
Find first match	`while current != null` + `if found: return`	Searching
Process n nodes	`while current != null and count < n`	Partial traversal

Mental Model: Follow the Chain

Always visualize the linked list as a chain of boxes connected by arrows. Your current pointer is your "finger" on one box. At each step, you do something with that box, then slide your finger along the arrow to the next box. When there's no next box (null), you're done.

Time and Space Complexity of Traversal

Understanding the complexity of traversal is straightforward but important for building intuition about linked list operations.

Time Complexity: O(n)

Traversal visits every node exactly once. If the list has n nodes:

We perform n iterations of the loop
Each iteration does constant work (accessing data, moving pointer)
Total time: O(n)

This is unavoidable because we must touch every node. There's no way to traverse a linked list faster than O(n) in the worst case—there are no shortcuts because there's no random access.

Space Complexity: O(1)

Traversal uses only a fixed amount of extra memory:

One pointer variable (current)
Maybe a few auxiliary variables (counter, sum, etc.)
These don't grow with list size

This is auxiliary space—space beyond the input. The list itself takes O(n) space, but traversal doesn't add to that.

Traversal Operation Complexities
Operation	Time Complexity	Space Complexity	Notes
Visit all nodes	O(n)	O(1)	Must touch every node
Count nodes	O(n)	O(1)	One counter variable
Search for value	O(n) worst, O(1) best	O(1)	Early termination possible
Find last node	O(n)	O(1)	Must reach the end
Find node at index k	O(k)	O(1)	Traverse k nodes

Contrast with Arrays

In an array, accessing element at index k is O(1). In a linked list, it's O(k). This is the fundamental trade-off. Linked lists excel at insertions/deletions but pay for it with slower access. When you need frequent random access, arrays are better. When you need frequent insertions/deletions at known positions, linked lists shine.

Visualizing Traversal Step by Step

Let's walk through a complete traversal with detailed visualization. This will cement your understanding of how the current pointer moves through the list.

Initial State

head → [10] → [20] → [30] → [40] → null
         ↑
       current  (initialized to head)

Iteration 1

Process: current.data = 10 (print it, count it, etc.)
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                ↑
              current

Iteration 2

Process: current.data = 20
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                        ↑
                      current

Iteration 3

Process: current.data = 30
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                                ↑
                              current

Iteration 4

Process: current.data = 40
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                                       ↑
                                     current = null

Loop Terminates

Condition: current != null → False
Loop exits. Traversal complete.

head → [10] → [20] → [30] → [40] → null
↑
head still points to first node (unchanged!)

Key Observations

Notice that: • The head pointer never moves—it always points to the first node • The current pointer visits each node exactly once • After traversal, current is null (past the end) • The list structure is completely unchanged • We can traverse again by resetting current = head

Practical Applications of Traversal

Traversal isn't just an academic exercise—it's the foundation of countless real-world operations. Let's see some practical examples:

1. Sum All Elements

sum-all-elements
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def sum_list(head):
    """Calculate the sum of all node values."""
    total = 0
    current = head
    
    while current is not None:
        total += current.data
        current = current.next
    
    return total
 
# List: [5] -> [10] -> [15] -> None
# sum_list(head) returns 30

2. Find Maximum/Minimum

find-max-min
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def find_max(head):
    """Find the maximum value in the linked list."""
    if head is None:
        return None  # or raise an exception
    
    max_val = head.data  # Initialize with first node's value
    current = head.next  # Start from second node
    
    while current is not None:
        if current.data > max_val:
            max_val = current.data
        current = current.next
    
    return max_val
 
# List: [7] -> [2] -> [9] -> [4] -> None
# find_max(head) returns 9

3. Check If Sorted

check-sorted
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_sorted(head):
    """Check if the linked list is sorted in ascending order."""
    if head is None or head.next is None:
        return True  # Empty or single-node list is sorted
    
    current = head
    
    while current.next is not None:
        if current.data > current.next.data:
            return False  # Found an out-of-order pair
        current = current.next
    
    return True
 
# List: [1] -> [3] -> [5] -> None → returns True
# List: [1] -> [5] -> [3] -> None → returns False

4. Convert to Array

convert-to-array
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def to_array(head):
    """Convert a linked list to an array/list."""
    result = []
    current = head
    
    while current is not None:
        result.append(current.data)
        current = current.next
    
    return result
 
# List: [A] -> [B] -> [C] -> None
# to_array(head) returns ['A', 'B', 'C']

Pattern Recognition

Notice that all these examples follow the same structure: initialize current, loop while not null, process, advance. The only variation is what happens in the "process" step. Once you internalize this pattern, you can apply it to any traversal-based problem.

Summary: Mastering Traversal

Traversal is the heartbeat of linked list manipulation. Every operation you'll ever perform—searching, inserting, deleting, reversing—builds on your ability to walk through the list node by node.

Key Takeaways:

What You've Learned

•The current pointer pattern: Create a separate variable to traverse, leaving head untouched
•The traversal loop: while current is not None → process → current = current.next
•Invariants: At each step, all nodes before current have been visited; all from current onward remain
•Variations: Different stopping conditions for different goals (last node, predecessor, early exit)
•Complexity: O(n) time, O(1) space—traversal is linear in the number of nodes
•Universal applicability: Sum, search, count, convert—all built on the same traversal pattern

Looking Ahead:

With traversal mastered, we're ready to tackle the operations that modify the list structure: insertion and deletion. In the next page, we'll see how to insert new nodes at the beginning, middle, and end of a linked list—and why each position requires a slightly different approach.

Page Complete

You've mastered the fundamentals of linked list traversal. The current pointer pattern, loop structure, invariants, and variations you've learned here will serve you throughout your work with linked lists. Next, we'll build on this foundation to learn insertion techniques.

1 / 4

Loading learning content...

Data Structures & AlgorithmsTraversal, Insertion, and Deletion Patterns

Traversal, Insertion, and Deletion Patterns

LevelBeginner

Duration60 mins

TopicTraversal, Insertion, and Deletion Patterns

1 / 4

Traversing with a Current Pointer

The Art of Walking Through a Linked List

Learning Objectives

Why Traversal Is Different in Linked Lists

Before diving into the mechanics, let's understand why linked list traversal is fundamentally different from array traversal—and why this difference matters.

Arrays: Random Access Paradise

In an array, all elements are stored in contiguous memory locations. This means:

You can jump directly to any element using an index: arr[5] takes you straight to the 6th element.
The memory address of any element is calculable: address = base_address + (index × element_size).
Traversal is optional: If you know the index, you don't need to visit preceding elements.

Linked Lists: Sequential Access Only

In a linked list, elements are scattered across memory, connected only by pointers:

You cannot jump to an arbitrary element: There's no index that takes you directly to the 5th node.
Each node only knows about the next node: To reach node 5, you must first visit nodes 1, 2, 3, and 4.
Traversal is mandatory: Finding any element (except the head) requires walking through the list.

Array Traversal

•Use an integer index: i = 0, 1, 2, ...
•Access element directly: arr[i]
•Increment index: i++
•Index is just a number—no pointer needed
•Can start traversal anywhere: arr[5]

Linked List Traversal

•Use a pointer variable: current
•Access element: current.data
•Move to next: current = current.next
•Pointer holds memory address of current node
•Must start from head—no shortcuts

The Sequential Nature Is Not a Bug—It's a Feature

The "Current" Pointer Concept

Why Do We Need a Separate Pointer?

You might wonder: "Why not just use the head pointer to traverse?"

The Current Pointer as a Bookmark

Think of the current pointer as a bookmark in a physical book:

The head is like knowing which book we're reading (the list's identity).
The current is like the bookmark showing which page we're on.
Moving the bookmark doesn't change which book it is—it just tracks our position.

We create a new variable, typically called current, and initialize it to point to the same node as head. Then we move current through the list while leaving head untouched.

traversal-pointer-concept
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# The fundamental traversal setup
# head points to the first node of the list
 
# CREATE a traversal pointer
# - This is a SEPARATE variable that starts at the head
# - It will move through the list
# - head remains unchanged throughout
 
current = head  # current now points to the same node as head
 
# At this point:
# - head → Node A (first node)
# - current → Node A (same first node)
# Both variables point to the SAME memory location
 
# As we traverse, only current moves:
# current = current.next  # current → Node B
# current = current.next  # current → Node C
# ...
# head still → Node A (unchanged!)

Memory Model Insight

The Traversal Loop Anatomy

Now let's examine the complete traversal loop. This is a pattern you'll use hundreds of times, so understanding every part is essential.

The Standard Traversal Pattern

The traversal loop has three components:

Initialization: Set current = head
Continuation Condition: Loop while current is not null
Advancement: Move current = current.next

Let's break this down in detail:

standard-traversal-loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def traverse(head):
    """
    Complete traversal of a linked list using the current pointer pattern.
    
    This function visits every node in the list exactly once,
    printing each node's data.
    """
    
    # STEP 1: INITIALIZATION
    # Create the traversal pointer, starting at the head
    current = head
    
    # STEP 2: CONTINUATION CONDITION
    # Continue as long as current is not None (not at the end)
    while current is not None:
        
        # PROCESS: Do something with the current node
        # This is where you put your actual work
        print(current.data)
        
        # STEP 3: ADVANCEMENT
        # Move to the next node
        # This MUST be the last thing in the loop
        current = current.next
    
    # At this point, current is None
    # We've visited every node and reached the end
 
# Visualizing the traversal:
# List: [A] -> [B] -> [C] -> None
#
# Before loop:  current = [A]
# Iteration 1:  print A, current = [B]
# Iteration 2:  print B, current = [C]
# Iteration 3:  print C, current = None
# Loop ends:   current is None

Why Check `current != null`?

This condition is essential because:

Empty List Safety: If the list is empty (head is null), the loop body never executes—which is correct behavior.
Termination Detection: The last node's next pointer is null, signaling the end of the list.
Null Dereference Prevention: If we didn't check, we'd crash trying to access null.data or null.next.

Order of Operations Matters

Note the order inside the loop:

1. Process current node (print, accumulate, check condition, etc.)
2. Advance to next node

If you reverse this order (advance first, then process), you'll skip the first node and crash on the last iteration trying to process null!

Common Mistake: Advancing Before Processing

A frequent beginner error is writing:

while current is not None:
    current = current.next  # ❌ Advancing first!
    print(current.data)     # ❌ Processes next node, not current

This skips the head and crashes when current becomes None. Always process first, then advance!

Understanding Traversal Invariants

An invariant is a condition that remains true throughout the execution of an algorithm. Understanding the invariants of linked list traversal helps you write correct code and debug errors.

The Key Traversal Invariants

At the beginning of each loop iteration:

If current is not null, then current points to a valid, unvisited node.
All nodes before current have already been visited.
All nodes from current onward have not yet been visited.

At the end of the entire traversal:

current is null, meaning we've passed the last node.
Every node in the list has been visited exactly once.
head still points to the first node (unchanged).

Traversal State at Each Step
Step	current Points To	Nodes Visited	Nodes Remaining
Before loop	Node A (head)	None	A, B, C
After iteration 1	Node B	A	B, C
After iteration 2	Node C	A, B	C
After iteration 3	null	A, B, C	None

Why Invariants Matter

These invariants help you:

Prove correctness: You can verify that every node will be visited and none will be skipped.
Debug errors: If something goes wrong, check which invariant was violated.
Modify the pattern safely: When you need a variation (e.g., stopping early), you know what conditions to adjust.

Invariant Thinking Is Professional-Grade

Traversal Variations

While the standard while current is not null pattern covers most cases, several variations exist for specific needs. Understanding these variations equips you for real-world linked list problems.

Variation 1: Counting Elements

A common task is determining the length of a linked list. We augment the traversal with a counter:

count-elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def count_nodes(head):
    """
    Count the number of nodes in the linked list.
    
    Time Complexity: O(n) - must visit every node
    Space Complexity: O(1) - only a counter variable
    """
    count = 0
    current = head
    
    while current is not None:
        count += 1           # Increment for each node visited
        current = current.next
    
    return count
 
# Example:
# List: [A] -> [B] -> [C] -> None
# Output: 3

Variation 2: Searching for a Value

To find a specific value, we combine traversal with early termination:

search-value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def search(head, target):
    """
    Search for a target value in the linked list.
    
    Returns: The node containing target, or None if not found.
    
    Time Complexity: O(n) worst case, O(1) best case (target at head)
    Space Complexity: O(1)
    """
    current = head
    
    while current is not None:
        if current.data == target:
            return current  # Found! Return immediately
        current = current.next
    
    return None  # Not found after checking all nodes
 
# Example:
# List: [10] -> [20] -> [30] -> None
# search(head, 20) returns the node containing 20
# search(head, 99) returns None

Variation 3: Finding the Last Node

To find the tail (last node), we stop when current.next is null:

find-last-node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def find_last_node(head):
    """
    Find the last node in the linked list.
    
    Returns: The last node, or None if the list is empty.
    
    Time Complexity: O(n) - must traverse the entire list
    Space Complexity: O(1)
    """
    # Handle empty list
    if head is None:
        return None
    
    current = head
    
    # Notice the different condition: current.next != None
    # We stop AT the last node, not AFTER it
    while current.next is not None:
        current = current.next
    
    # current now points to the last node
    return current
 
# Example:
# List: [A] -> [B] -> [C] -> None
# Returns: Node C
#
# Why current.next instead of current?
# - If we use 'while current', we end up with current = None
# - We want to STOP at the last node, not go past it

Variation 4: Finding the Node Before (Predecessor)

For deletions at arbitrary positions, we often need to find the node before a target. This requires tracking a "previous" pointer:

find-predecessor
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def find_predecessor(head, target):
    """
    Find the node that comes BEFORE the node containing target.
    
    This is essential for deletion operations, where we need
    to update the previous node's 'next' pointer.
    
    Returns: The predecessor node, or None if target is at head or not found.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Can't have a predecessor of the head
    if head is None or head.data == target:
        return None
    
    current = head
    
    # We look at current.next to find the target
    while current.next is not None:
        if current.next.data == target:
            return current  # current is the predecessor
        current = current.next
    
    return None  # Target not found
 
# Example:
# List: [A] -> [B] -> [C] -> None
# find_predecessor(head, 'B') returns Node A
# find_predecessor(head, 'A') returns None (no predecessor of head)

The Previous Pointer Pattern

The Traversal-Process-Advance Pattern

Let's crystallize the traversal pattern into a reusable mental framework. This pattern applies to almost every linked list traversal problem:

The Pattern Structure

1. INITIALIZE: Set current = head (and any auxiliary variables)
2. LOOP while current is not null:
   a. PROCESS: Do something with current node
   b. ADVANCE: Move current to current.next
3. CLEANUP: Handle any post-traversal logic

This pattern is flexible. The "PROCESS" step can be:

Printing data
Accumulating a sum
Checking a condition
Comparing with a target
Building a new structure
Any operation on the current node

Pattern Variations Based on Stopping Condition

Goal	Loop Condition	When to Use
Visit all nodes	`while current != null`	Printing, summing, transforming
Stop at last node	`while current.next != null`	Appending to tail, modifying last
Stop before target	`while current.next.data != target`	Deletion of target node
Find first match	`while current != null` + `if found: return`	Searching
Process n nodes	`while current != null and count < n`	Partial traversal

Mental Model: Follow the Chain

Time and Space Complexity of Traversal

Understanding the complexity of traversal is straightforward but important for building intuition about linked list operations.

Time Complexity: O(n)

Traversal visits every node exactly once. If the list has n nodes:

We perform n iterations of the loop
Each iteration does constant work (accessing data, moving pointer)
Total time: O(n)

This is unavoidable because we must touch every node. There's no way to traverse a linked list faster than O(n) in the worst case—there are no shortcuts because there's no random access.

Space Complexity: O(1)

Traversal uses only a fixed amount of extra memory:

One pointer variable (current)
Maybe a few auxiliary variables (counter, sum, etc.)
These don't grow with list size

This is auxiliary space—space beyond the input. The list itself takes O(n) space, but traversal doesn't add to that.

Traversal Operation Complexities
Operation	Time Complexity	Space Complexity	Notes
Visit all nodes	O(n)	O(1)	Must touch every node
Count nodes	O(n)	O(1)	One counter variable
Search for value	O(n) worst, O(1) best	O(1)	Early termination possible
Find last node	O(n)	O(1)	Must reach the end
Find node at index k	O(k)	O(1)	Traverse k nodes

Contrast with Arrays

Visualizing Traversal Step by Step

Let's walk through a complete traversal with detailed visualization. This will cement your understanding of how the current pointer moves through the list.

Initial State

head → [10] → [20] → [30] → [40] → null
         ↑
       current  (initialized to head)

Iteration 1

Process: current.data = 10 (print it, count it, etc.)
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                ↑
              current

Iteration 2

Process: current.data = 20
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                        ↑
                      current

Iteration 3

Process: current.data = 30
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                                ↑
                              current

Iteration 4

Process: current.data = 40
Advance: current = current.next

head → [10] → [20] → [30] → [40] → null
                                       ↑
                                     current = null

Loop Terminates

Condition: current != null → False
Loop exits. Traversal complete.

head → [10] → [20] → [30] → [40] → null
↑
head still points to first node (unchanged!)

Key Observations

Practical Applications of Traversal

Traversal isn't just an academic exercise—it's the foundation of countless real-world operations. Let's see some practical examples:

1. Sum All Elements

sum-all-elements
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def sum_list(head):
    """Calculate the sum of all node values."""
    total = 0
    current = head
    
    while current is not None:
        total += current.data
        current = current.next
    
    return total
 
# List: [5] -> [10] -> [15] -> None
# sum_list(head) returns 30

2. Find Maximum/Minimum

find-max-min
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def find_max(head):
    """Find the maximum value in the linked list."""
    if head is None:
        return None  # or raise an exception
    
    max_val = head.data  # Initialize with first node's value
    current = head.next  # Start from second node
    
    while current is not None:
        if current.data > max_val:
            max_val = current.data
        current = current.next
    
    return max_val
 
# List: [7] -> [2] -> [9] -> [4] -> None
# find_max(head) returns 9

3. Check If Sorted

check-sorted
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def is_sorted(head):
    """Check if the linked list is sorted in ascending order."""
    if head is None or head.next is None:
        return True  # Empty or single-node list is sorted
    
    current = head
    
    while current.next is not None:
        if current.data > current.next.data:
            return False  # Found an out-of-order pair
        current = current.next
    
    return True
 
# List: [1] -> [3] -> [5] -> None → returns True
# List: [1] -> [5] -> [3] -> None → returns False

4. Convert to Array

convert-to-array
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
def to_array(head):
    """Convert a linked list to an array/list."""
    result = []
    current = head
    
    while current is not None:
        result.append(current.data)
        current = current.next
    
    return result
 
# List: [A] -> [B] -> [C] -> None
# to_array(head) returns ['A', 'B', 'C']

Pattern Recognition

Summary: Mastering Traversal

Traversal is the heartbeat of linked list manipulation. Every operation you'll ever perform—searching, inserting, deleting, reversing—builds on your ability to walk through the list node by node.

Key Takeaways:

What You've Learned

•The current pointer pattern: Create a separate variable to traverse, leaving head untouched
•The traversal loop: while current is not None → process → current = current.next
•Invariants: At each step, all nodes before current have been visited; all from current onward remain
•Variations: Different stopping conditions for different goals (last node, predecessor, early exit)
•Complexity: O(n) time, O(1) space—traversal is linear in the number of nodes
•Universal applicability: Sum, search, count, convert—all built on the same traversal pattern

Looking Ahead:

Page Complete

1 / 4

Traversal, Insertion, and Deletion Patterns

Traversing with a Current Pointer

Arrays: Random Access Paradise

Linked Lists: Sequential Access Only

Why Do We Need a Separate Pointer?

The Current Pointer as a Bookmark

The Standard Traversal Pattern

Why Check current != null?

Order of Operations Matters

The Key Traversal Invariants

Why Invariants Matter

Variation 1: Counting Elements

Variation 2: Searching for a Value

Variation 3: Finding the Last Node

Variation 4: Finding the Node Before (Predecessor)

The Pattern Structure

Pattern Variations Based on Stopping Condition

Time Complexity: O(n)

Space Complexity: O(1)

Initial State

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Loop Terminates

1. Sum All Elements

2. Find Maximum/Minimum

3. Check If Sorted

4. Convert to Array

Traversal, Insertion, and Deletion Patterns

Traversing with a Current Pointer

Arrays: Random Access Paradise

Linked Lists: Sequential Access Only

Why Do We Need a Separate Pointer?

The Current Pointer as a Bookmark

The Standard Traversal Pattern

Why Check current != null?

Order of Operations Matters

The Key Traversal Invariants

Why Invariants Matter

Variation 1: Counting Elements

Variation 2: Searching for a Value

Variation 3: Finding the Last Node

Variation 4: Finding the Node Before (Predecessor)

The Pattern Structure

Pattern Variations Based on Stopping Condition

Time Complexity: O(n)

Space Complexity: O(1)

Initial State

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Loop Terminates

1. Sum All Elements

2. Find Maximum/Minimum

3. Check If Sorted

4. Convert to Array

Why Check `current != null`?

Why Check `current != null`?