Linked List vs Array When to Choose Which in DSA Go - Trade-offs & Analysis

Mental Model

Arrays store items in order in one block of memory, while linked lists store items scattered in memory connected by pointers.

Analogy: An array is like a row of mailboxes all in a line, easy to find by number. A linked list is like a treasure hunt where each clue points to the next location.

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

Dry Run Walkthrough

Input: Compare inserting value 5 at the start of array [1,2,3,4] vs linked list 1->2->3->4

Goal: Show how insertion at start differs in arrays and linked lists

Step 1: Shift all array elements right to make space at index 0

[_][1][2][3][4] (array size increased by 1)

Why: Array elements must move to keep order and make room for new item

Step 2: Insert 5 at index 0 in array

[5][1][2][3][4]

Why: New value placed at start after shifting

Step 3: Create new node with value 5 for linked list

5 -> null

Why: Prepare new node to insert at start

Step 4: Point new node's next to current head (1)

5 -> 1 -> 2 -> 3 -> 4 -> null

Why: Link new node to existing list

Step 5: Update head pointer to new node (5)

Head -> 5 -> 1 -> 2 -> 3 -> 4 -> null

Why: New node becomes first element in list

Result:

Array after insertion: [5][1][2][3][4]
Linked list after insertion: 5 -> 1 -> 2 -> 3 -> 4 -> null

Annotated Code

DSA Go

package main

import "fmt"

// Node for linked list
type Node struct {
	val  int
	next *Node
}

// InsertAtStartArray inserts val at start of array by shifting elements
func InsertAtStartArray(arr []int, val int) []int {
	arr = append(arr, 0) // increase size by 1
	for i := len(arr) - 2; i >= 0; i-- {
		arr[i+1] = arr[i] // shift right
	}
	arr[0] = val // insert at start
	return arr
}

// InsertAtStartLinkedList inserts val at start of linked list
func InsertAtStartLinkedList(head *Node, val int) *Node {
	newNode := &Node{val: val}
	newNode.next = head // link new node to current head
	return newNode // new node is new head
}

// PrintArray prints array elements
func PrintArray(arr []int) {
	for _, v := range arr {
		fmt.Printf("[%d]", v)
	}
	fmt.Println()
}

// PrintLinkedList prints linked list elements
func PrintLinkedList(head *Node) {
	curr := head
	for curr != nil {
		fmt.Printf("%d -> ", curr.val)
		curr = curr.next
	}
	fmt.Println("null")
}

func main() {
	arr := []int{1, 2, 3, 4}
	head := &Node{val: 1, next: &Node{val: 2, next: &Node{val: 3, next: &Node{val: 4}}}}

	arr = InsertAtStartArray(arr, 5)
	head = InsertAtStartLinkedList(head, 5)

	fmt.Print("Array after insertion: ")
	PrintArray(arr)

	fmt.Print("Linked list after insertion: ")
	PrintLinkedList(head)
}

for i := len(arr) - 2; i >= 0; i-- { arr[i+1] = arr[i] // shift right }

shift array elements right to make space at start

arr[0] = val // insert at start

place new value at index 0

newNode := &Node{val: val} newNode.next = head // link new node to current head return newNode // new node is new head

create new node and link it before current head

Output

Array after insertion: [5][1][2][3][4]

Linked list after insertion: 5 -> 1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(n) for array insertion at start because all elements must shift; O(1) for linked list insertion because only pointers change

Space: O(n) for array due to resizing; O(1) for linked list as only one new node is created

vs Alternative: Linked list insertion is faster at start than array because array needs to move all elements, but linked list just changes pointers

Edge Cases

empty array or empty linked list

Insertion works normally; array becomes single element array, linked list head points to new node

DSA Go

arr = append(arr, 0) // increase size by 1

single element array or linked list

Insertion shifts or links correctly without errors

DSA Go

newNode.next = head // link new node to current head

When to Use This Pattern

When you need fast insertions or deletions at the start or middle, linked lists are better; when you need fast random access by index, arrays are better.

Common Mistakes

Mistake: Trying to insert at start of array without shifting elements
Fix: Shift all elements right before inserting new value at index 0

Mistake: Not updating head pointer after inserting new node in linked list
Fix: Return new node as new head and update head pointer

Summary

Compares when to use linked lists or arrays based on insertion operation costs.

Use linked lists for fast insertions/deletions; use arrays for fast indexed access.

Arrays store items contiguously requiring shifts; linked lists use pointers allowing quick insertions.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Array

B. Linked List

C. Stack

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements contiguously, so accessing any index is fast and direct.

2. Step 2: Compare with linked list access

   Linked lists require traversal from the start to reach an index, which is slower.

3. Final Answer:

   Array -> Option A

4. Quick Check:

   Fast random access = Array [OK]

Hint: For fast index access, choose arrays [OK]

Common Mistakes:

• Thinking linked lists provide fast random access
• Confusing stack or queue with random access
• Ignoring array's contiguous memory advantage

2. Which of the following is the correct way to declare an array of integers with 5 elements in Go?

easy

A. var arr [5]int

B. arr := []int{5}

C. var arr int[5]

D. arr := int[5]

Solution

1. Step 1: Recall Go array declaration syntax

   In Go, arrays are declared with var name [size]type, e.g., var arr [5]int.

2. Step 2: Check other options for errors

   arr := []int{5} declares a slice with one element 5, not an array of size 5. var arr int[5] syntax is invalid. arr := int[5] syntax is invalid.

3. Final Answer:

   var arr [5]int -> Option A

4. Quick Check:

   Go array syntax = var arr [5]int [OK]

Hint: Use var name [size]type for arrays in Go [OK]

Common Mistakes:

• Confusing slices with arrays
• Using incorrect syntax like int[5]
• Assuming shorthand always creates arrays

3. Consider the following Go code using a singly linked list. What will be printed after inserting 3 nodes with values 10, 20, 30 in that order?

package main
import "fmt"
type Node struct {
    value int
    next  *Node
}
func main() {
    head := &Node{value: 10}
    head.next = &Node{value: 20}
    head.next.next = &Node{value: 30}

    current := head
    for current != nil {
        fmt.Print(current.value, " -> ")
        current = current.next
    }
    fmt.Print("null")
}

medium

A. null

B. 30 -> 20 -> 10 -> null

C. 10 -> 20 -> 30 -> null

D. 10 -> 30 -> 20 -> null

Solution

1. Step 1: Trace node insertion order

   Nodes are linked as 10 -> 20 -> 30 in order, so head points to 10, next to 20, then 30.

2. Step 2: Trace print loop

   Loop prints current.value then moves to next until nil, printing 10 -> 20 -> 30 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option C

4. Quick Check:

   Linked list traversal prints nodes in insertion order [OK]

Hint: Traverse linked list from head to print in order [OK]

Common Mistakes:

• Assuming reverse order print
• Confusing next pointers
• Forgetting to print 'null' at end

4. The following Go code tries to insert a new node with value 15 after the head in a linked list. What is the bug?

package main
type Node struct {
    value int
    next  *Node
}
func main() {
    head := &Node{value: 10}
    head.next = &Node{value: 20}

    newNode := &Node{value: 15}
    newNode.next = head.next
    head = newNode
}

medium

A. Incorrect struct definition

B. The new node is not linked correctly; head pointer is overwritten

C. Missing initialization of newNode

D. No bug; code works fine

Solution

1. Step 1: Analyze pointer changes

   newNode.next points to head.next (20), but then head is set to newNode, losing original head node (10).

2. Step 2: Identify correct insertion

   To insert after head, should set head.next = newNode, not head = newNode.

3. Final Answer:

   The new node is not linked correctly; head pointer is overwritten -> Option B

4. Quick Check:

   Head pointer overwritten = bug [OK]

Hint: To insert after head, update head.next, not head [OK]

Common Mistakes:

• Overwriting head pointer instead of next
• Confusing insertion before vs after head
• Ignoring pointer updates needed

5. You need to store a large collection of elements where insertions and deletions happen frequently at unknown positions, but random access is rarely needed. Which data structure is best and why?

hard

A. Linked List, because it supports fast random access

B. Array, because it uses contiguous memory for fast access

C. Array, because it uses less memory than linked lists

D. Linked List, because it allows efficient insertions and deletions anywhere

Solution

1. Step 1: Understand insertion/deletion needs

   Frequent insertions/deletions at unknown positions are costly in arrays due to shifting elements.

2. Step 2: Compare linked list advantages

   Linked lists allow changing pointers to insert/delete nodes efficiently without shifting.

3. Step 3: Consider random access requirement

   Random access is rare, so linked list's slower access is acceptable.

4. Final Answer:

   Linked List, because it allows efficient insertions and deletions anywhere -> Option D

5. Quick Check:

   Frequent insert/delete unknown pos = Linked List [OK]

Hint: Choose linked list for frequent insert/delete at unknown spots [OK]

Common Mistakes:

• Choosing array for frequent insert/delete
• Confusing random access speed importance
• Ignoring memory overhead of linked lists