Struct pointers in Go - Time & Space Complexity

Time Complexity: Struct pointers

O(n)

Understanding Time Complexity

When working with struct pointers in Go, it's important to understand how the program's running time changes as we use these pointers.

We want to know how the number of steps grows when accessing or modifying data through struct pointers.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

package main

type Node struct {
    value int
    next  *Node
}

func sumList(head *Node) int {
    sum := 0
    for current := head; current != nil; current = current.next {
        sum += current.value
    }
    return sum
}

This code sums all values in a linked list by following struct pointers from one node to the next.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each node by following the next pointer.
• How many times: Once for each node in the list, until the end is reached.

How Execution Grows With Input

As the list gets longer, the loop runs more times, once per node.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The number of steps grows directly with the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to sum the list grows in a straight line with the number of nodes.

Common Mistake

[X] Wrong: "Using pointers makes the code run instantly or in constant time."

[OK] Correct: Even with pointers, you still need to visit each node one by one, so time grows with list size.

Interview Connect

Understanding how following struct pointers affects time helps you explain linked list operations clearly and confidently.

Self-Check

"What if we changed the linked list to a tree structure? How would the time complexity change when summing all values?"