Memory Layout Comparison Array vs Linked List in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of memory addresses in array vs linked list nodes

Consider the following Go code that creates an array and a linked list with the same integer values. What will be printed regarding the memory addresses?

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	value int
	next  *Node
}

func main() {
	arr := [3]int{10, 20, 30}

	head := &Node{value: 10}
	head.next = &Node{value: 20}
	head.next.next = &Node{value: 30}

	fmt.Println("Array addresses:")
	for i := 0; i < len(arr); i++ {
		fmt.Printf("%p ", &arr[i])
	}
	fmt.Println()

	fmt.Println("Linked list node addresses:")
	current := head
	for current != nil {
		fmt.Printf("%p ", current)
		current = current.next
	}
	fmt.Println()
}

A Array addresses are contiguous in memory; linked list node addresses are scattered.

B Array addresses are scattered; linked list node addresses are contiguous.

C Both array and linked list node addresses are contiguous in memory.

D Both array and linked list node addresses are scattered randomly.

💡 Hint

Think about how arrays and linked lists store their elements in memory.

Arrays store elements in contiguous memory locations, so their addresses are next to each other. Linked list nodes are allocated separately on the heap, so their addresses are scattered.

🧠 Conceptual

intermediate

Memory usage difference between array and linked list

Which statement correctly describes the memory usage difference between an array and a linked list storing the same number of integer elements?

A Array uses more memory because it stores elements non-contiguously.

B Linked list uses less memory because it allocates nodes dynamically; array wastes memory by reserving extra space.

C Both use the same amount of memory because they store the same number of elements.

D Array uses less memory overall because it stores only elements; linked list uses extra memory for pointers.

💡 Hint

Consider what extra information each linked list node must store.

Each linked list node stores the element plus a pointer to the next node, which adds extra memory overhead. Arrays store elements contiguously without extra pointers, so they use less memory overall.

❓ Predict Output

advanced

Effect of resizing on array memory layout

What happens to the memory layout of a Go slice when it grows beyond its capacity?

Consider this code snippet:

DSA Go

package main

import (
	"fmt"
)

func main() {
	slice := make([]int, 3, 3)
	slice[0], slice[1], slice[2] = 1, 2, 3

	fmt.Printf("Initial slice address: %p\n", &slice[0])

	slice = append(slice, 4)

	fmt.Printf("After append slice address: %p\n", &slice[0])
}

A The slice's underlying array is copied but stays at the same address.

B The slice's underlying array remains at the same memory location; address does not change.

C The slice's underlying array is reallocated at a new memory location; address changes.

D The slice's underlying array is resized in place without moving.

💡 Hint

Think about what happens when a slice exceeds its capacity.

When a slice exceeds its capacity, Go allocates a new larger array and copies the elements over. This new array is at a different memory location, so the address changes.

🧠 Conceptual

advanced

Why linked lists have non-contiguous memory layout

Why do linked lists have nodes stored at non-contiguous memory locations?

A Because linked lists store elements in a contiguous array internally.

B Because each node is allocated separately on the heap as needed, not in a block.

C Because linked lists use stack memory which is fragmented.

D Because linked lists pre-allocate all nodes in a contiguous block.

💡 Hint

Think about how nodes are created and linked in memory.

Linked list nodes are allocated individually on the heap when needed, so their memory locations are scattered and not contiguous.

🚀 Application

expert

Predict memory layout after mixed operations on array and linked list

Given the following Go code, what will be the printed memory layout pattern?

DSA Go

package main

import (
	"fmt"
)

type Node struct {
	val  int
	next *Node
}

func main() {
	arr := []int{1, 2, 3}

	head := &Node{val: 1}
	head.next = &Node{val: 2}
	head.next.next = &Node{val: 3}

	fmt.Println("Array addresses before append:")
	for i := range arr {
		fmt.Printf("%p ", &arr[i])
	}
	fmt.Println()

	arr = append(arr, 4)

	fmt.Println("Array addresses after append:")
	for i := range arr {
		fmt.Printf("%p ", &arr[i])
	}
	fmt.Println()

	fmt.Println("Linked list node addresses:")
	current := head
	for current != nil {
		fmt.Printf("%p ", current)
		current = current.next
	}
	fmt.Println()
}

A Array addresses change after append due to reallocation; linked list node addresses remain scattered and unchanged.

B Array addresses remain the same; linked list node addresses remain scattered.

C Array addresses change after append; linked list node addresses become contiguous.

D Array addresses remain the same after append; linked list node addresses become contiguous.

💡 Hint

Recall how Go slices grow and how linked list nodes are allocated.

Appending beyond capacity causes the slice to allocate a new underlying array at a new memory location, changing addresses. Linked list nodes remain individually allocated and scattered.

Practice

1. Which of the following best describes the memory layout of an array compared to a linked list?

easy

A. Both array and linked list elements are scattered randomly in memory.

B. Both array and linked list elements are stored contiguously in memory.

C. Linked list elements are stored contiguously, but array elements are scattered in memory.

D. Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory.

Solution

1. Step 1: Understand array memory layout

   Arrays store elements in a continuous block of memory, one after another.

2. Step 2: Understand linked list memory layout

   Linked list nodes are allocated separately and linked via pointers, so they are scattered.

3. Final Answer:

   Array elements are stored in contiguous memory locations, while linked list nodes are scattered in memory. -> Option D

4. Quick Check:

   Array = contiguous, Linked list = scattered [OK]

Hint: Arrays are continuous; linked lists use pointers to scattered nodes [OK]

Common Mistakes:

• Thinking linked list nodes are stored contiguously
• Confusing array and linked list memory layouts
• Assuming both have same memory layout

2. Which Go syntax correctly declares an array of 5 integers?

easy

A. var arr []int = [5]

B. arr := []int{5}

C. var arr [5]int

D. arr := [5]int

Solution

1. Step 1: Recall Go array declaration syntax

   Arrays are declared with fixed size inside square brackets before the type, e.g., [5]int.

2. Step 2: Check each option

   A: var arr [5]int uses correct syntax. B: arr := []int{5} creates a slice with one element. C: var arr []int = [5] is invalid syntax. D: arr := [5]int is invalid syntax - missing composite literal {}.

3. Final Answer:

   var arr [5]int -> Option C

4. Quick Check:

   Array declaration = var arr [5]int [OK]

Hint: Array size goes inside brackets before type in Go [OK]

Common Mistakes:

• Using slice syntax instead of array syntax
• Placing size after type
• Incorrect initialization syntax

3. Consider this Go code snippet:

package main

import "fmt"

type Node struct {
    value int
    next  *Node
}

func main() {
    var head *Node
    head = &Node{value: 1}
    head.next = &Node{value: 2}
    head.next.next = &Node{value: 3}
    
    arr := [3]int{1, 2, 3}
    
    fmt.Println(arr)
    fmt.Println(head.value, head.next.value, head.next.next.value)
}

What will be the output?

medium

A. [1 2 3]
3 2 1

B. [1 2 3]
1 2 3

C. [1 2 3]
1 3 2

D. Compilation error

Solution

1. Step 1: Understand array print output

   Array arr contains [1, 2, 3], so fmt.Println(arr) prints [1 2 3].

2. Step 2: Understand linked list traversal print

   head.value = 1, head.next.value = 2, head.next.next.value = 3, so printing them in order prints '1 2 3'.

3. Final Answer:

   [1 2 3] 1 2 3 -> Option B

4. Quick Check:

   Array and linked list values match printed order [OK]

Hint: Print array and linked list values in order to verify [OK]

Common Mistakes:

• Confusing linked list node order
• Expecting commas in array print
• Assuming compilation error due to pointers

4. The following Go code attempts to create a linked list but has an error:

type Node struct {
    value int
    next  *Node
}

func main() {
    var head *Node
    head.value = 10
    head.next = nil
}

What is the error and how to fix it?

medium

A. head is nil pointer; initialize head before assigning fields

B. next field should be value, not pointer

C. value field must be a pointer type

D. No error; code runs fine

Solution

1. Step 1: Identify pointer initialization issue

   head is declared as *Node but not initialized, so it is nil (no memory allocated).

2. Step 2: Fix by allocating memory for head

   Use head = &Node{} before assigning head.value and head.next to avoid nil pointer dereference.

3. Final Answer:

   head is nil pointer; initialize head before assigning fields -> Option A

4. Quick Check:

   Nil pointer must be initialized before use [OK]

Hint: Always allocate memory for pointer before field access [OK]

Common Mistakes:

• Assigning fields on nil pointer
• Changing field types unnecessarily
• Ignoring runtime panic from nil dereference

5. You want to store 1 million integers and frequently insert and delete elements in the middle. Considering memory layout and performance, which data structure is better and why?

1. Array
2. Linked List

hard

A. Linked List, because scattered nodes make insertions and deletions faster despite poor cache usage

B. Linked List, because arrays cannot store large data

C. Array, because insertions and deletions are always faster in arrays

D. Array, because contiguous memory improves cache performance despite costly insertions

Solution

1. Step 1: Analyze insertion/deletion cost in arrays

   Arrays store data contiguously, so inserting or deleting in the middle requires shifting many elements, which is slow.

2. Step 2: Analyze linked list insertion/deletion

   Linked lists store nodes scattered but allow fast insert/delete by changing pointers without shifting elements.

3. Step 3: Consider memory and cache trade-offs

   Arrays have better cache performance due to contiguous memory, but linked lists are better for frequent middle insertions/deletions.

4. Final Answer:

   Linked List, because scattered nodes make insertions and deletions faster despite poor cache usage -> Option A

5. Quick Check:

   Frequent middle insert/delete favors linked list [OK]

Hint: Frequent middle insert/delete? Choose linked list despite cache cost [OK]

Common Mistakes:

• Assuming arrays always faster for insert/delete
• Ignoring shifting cost in arrays
• Thinking arrays can't store large data