Memory Layout Comparison Array vs Linked List in DSA Go - Trade-offs & Analysis

Mental Model

Arrays store items next to each other in memory, while linked lists store items scattered with pointers connecting them.

Analogy: Imagine a row of houses built side by side (array) versus houses spread out in a neighborhood connected by roads (linked list).

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Compare memory layout of array and linked list with elements 1, 2, 3

Goal: Show how elements are stored in memory and how access differs

Step 1: Visualize array elements stored contiguously

[1][2][3]

Why: Array elements are placed side by side in memory for fast access

Step 2: Visualize linked list nodes scattered with pointers

1 -> 2 -> 3 -> null

Why: Linked list nodes can be anywhere in memory, connected by pointers

Step 3: Access second element in array by index

[1][2][3]

Why: Array allows direct access using index because of contiguous layout

Step 4: Access second element in linked list by following pointer

1 -> [2] -> 3 -> null

Why: Linked list requires moving from first node to second via pointer

Result:

Array memory: [1][2][3]
Linked list memory: 1 -> 2 -> 3 -> null
Access array index 1: 2
Access linked list second node: 2

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

func printArray(arr []int) {
	for i, v := range arr {
		fmt.Printf("[%d]", v)
	}
	fmt.Println()
}

func printLinkedList(head *Node) {
	curr := head
	for curr != nil {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next
	}
	fmt.Println("null")
}

func main() {
	// Array with elements 1,2,3
	arr := []int{1, 2, 3}
	fmt.Print("Array memory: ")
	printArray(arr)

	// Linked list with elements 1->2->3->null
	head := &Node{value: 1}
	head.next = &Node{value: 2}
	head.next.next = &Node{value: 3}
	fmt.Print("Linked list memory: ")
	printLinkedList(head)

	// Access second element in array
	fmt.Printf("Access array index 1: %d\n", arr[1])

	// Access second element in linked list
	second := head.next
	fmt.Printf("Access linked list second node: %d\n", second.value)
}

for i, v := range arr {

iterate array elements to show contiguous memory

curr := head

start at linked list head to traverse nodes

for curr != nil {

traverse linked list nodes until end

second := head.next

access second node by following pointer

Output

Array memory: [1][2][3]

Linked list memory: 1 -> 2 -> 3 -> null

Access array index 1: 2

Access linked list second node: 2

Complexity Analysis

Time: O(1) for array access because elements are contiguous; O(n) for linked list access because traversal is needed

Space: O(n) for both since they store n elements; linked list uses extra space for pointers

vs Alternative: Array uses less memory overhead and faster access; linked list allows flexible memory use but slower access

Edge Cases

empty array and empty linked list

Both have no elements; array length is zero; linked list head is nil

DSA Go

for curr != nil {

single element array and linked list

Array has one element at index 0; linked list has one node with next nil

DSA Go

head.next = nil

When to Use This Pattern

When you see a problem asking about memory use or access speed differences between data structures, think about array vs linked list memory layout.

Common Mistakes

Mistake: Assuming linked list elements are stored next to each other in memory
Fix: Remember linked list nodes can be anywhere in memory connected by pointers

Mistake: Thinking array access requires traversal like linked list
Fix: Array allows direct index access due to contiguous memory

Summary

Shows how arrays store elements contiguously and linked lists store nodes scattered with pointers.

Use when you want to understand memory layout impact on access speed and flexibility.

Arrays have fast direct access because elements are side by side; linked lists use pointers to connect scattered nodes.

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