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?"

Practice

1. What does a struct pointer in Go hold?
type Person struct { Name string }

easy

A. Only the struct's first field value

B. A copy of the struct data

C. The memory address of a struct instance

D. A string representation of the struct

Solution

1. Step 1: Understand what a pointer stores

   A pointer stores the memory address of a variable, not the variable's value itself.

2. Step 2: Apply to struct pointers

   A struct pointer holds the address of the struct instance, allowing access or modification of the original struct.

3. Final Answer:

   The memory address of a struct instance -> Option C

4. Quick Check:

   Struct pointer = memory address [OK]

Hint: Pointers hold addresses, not copies. Remember & for address [OK]

Common Mistakes:

• Thinking pointer holds a copy of the struct
• Confusing pointer with struct value
• Assuming pointer holds only first field

2. Which of the following is the correct way to declare a pointer to a struct Person in Go?

easy

A. var *p Person

B. var p Person*

C. var p &Person

D. var p *Person

Solution

1. Step 1: Recall Go pointer syntax

   In Go, a pointer type is declared by placing * before the type name, e.g., *Person.

2. Step 2: Match correct declaration

   var p *Person uses var p *Person, which is the correct syntax for a pointer variable.

3. Final Answer:

   var p *Person -> Option D

4. Quick Check:

   Pointer declaration = *Type [OK]

Hint: Pointer type syntax: *TypeName, not after variable [OK]

Common Mistakes:

• Placing * after variable name
• Using & in declaration instead of *
• Incorrect order of * and type

3. What is the output of this Go program?

package main
import "fmt"
type Point struct { X, Y int }
func main() {
 p := Point{1, 2}
 ptr := &p
 ptr.X = 10
 fmt.Println(p.X)
}

medium

A. 1

B. 10

C. 0

D. Compilation error

Solution

1. Step 1: Understand pointer modification

   ptr points to p. Changing ptr.X modifies p.X because ptr references p's memory.

2. Step 2: Check printed value

   After setting ptr.X = 10, p.X becomes 10. So, printing p.X outputs 10.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Pointer changes original struct field [OK]

Hint: Changing pointer field changes original struct field [OK]

Common Mistakes:

• Thinking ptr.X is separate copy
• Expecting original p.X to remain 1
• Confusing pointer dereference syntax

4. Identify the error in this Go code snippet:

package main
import "fmt"
type User struct { Name string }
func updateName(u User) {
 u.Name = "Alice"
}
func main() {
 user := User{"Bob"}
 updateName(&user)
 fmt.Println(user.Name)
}

medium

A. Passing pointer to function expecting value

B. Missing import for fmt package

C. Cannot assign string to Name field

D. Function parameter should be a pointer to User

Solution

1. Step 1: Check function parameter type

   Function updateName expects a User value, but main passes &user (a *User pointer).

2. Step 2: Identify the type mismatch

   This causes a compilation error because the argument type (*User) does not match the parameter type (User).

3. Final Answer:

   Passing pointer to function expecting value -> Option A

4. Quick Check:

   Function param must match argument type [OK]

Hint: Match function param type with argument (& for pointer) [OK]

Common Mistakes:

• Passing pointer to value parameter without pointer receiver
• Ignoring need to modify original struct
• Assuming string assignment causes error

5. Given this struct and function:

package main
import "fmt"
type Counter struct { Count int }
func increment(c *Counter) {
 c.Count++
}
func main() {
 c := Counter{Count: 5}
 increment(&c)
 increment(c)
 fmt.Println(c.Count)
}

What will happen when running this program?

hard

A. Compilation error at increment(c)

B. Output is 7

C. Output is 6

D. Runtime panic due to invalid pointer

Solution

1. Step 1: Analyze function calls

   increment expects a *Counter pointer. The first call increment(&c) is correct.

2. Step 2: Check second call increment(c)

   Passing c (a value) instead of *Counter causes a compilation error because types don't match.

3. Final Answer:

   Compilation error at increment(c) -> Option A

4. Quick Check:

   Pointer param requires pointer argument [OK]

Hint: Pointer params need pointer args; value won't auto-convert [OK]

Common Mistakes:

• Assuming Go auto-converts value to pointer
• Expecting output 7 without error
• Ignoring type mismatch in function call