Why Linked List Exists and What Problem It Solves in DSA Go - Why This Pattern

Mental Model

A linked list stores items one after another but uses pointers to connect them, so adding or removing items is easy without moving everything.

Analogy: Imagine a treasure hunt where each clue points to the next location instead of having all clues written on one big paper. You can add or remove clues without rewriting the whole list.

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

Dry Run Walkthrough

Input: Array: [1, 2, 3], insert 4 at start

Goal: Show how inserting at the start is easy with linked list but costly with array

Step 1: Insert 4 at start in array by shifting all elements right

Array: [_, 1, 2, 3] (need to move 1,2,3 to right first)

Why: Array needs to move all elements to make space at start

Step 2: Shift 3 to index 3, 2 to index 2, 1 to index 1

Array: [_, 1, 2, 3] -> [_, 1, 2, 3] -> [_, 1, 2, 3]

Why: Each element moves one step right, costly for large arrays

Step 3: Place 4 at index 0 in array

Array: [4, 1, 2, 3]

Why: Insertion done but took many moves

Step 4: Insert 4 at start in linked list by creating new node

Linked List: 4 -> 1 -> 2 -> 3 -> null

Why: Linked list just changes head pointer, no shifting

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	value int
	next  *Node
}

type LinkedList struct {
	head *Node
}

func (ll *LinkedList) InsertAtStart(val int) {
	newNode := &Node{value: val}
	newNode.next = ll.head // connect new node to existing list start
	ll.head = newNode      // move head pointer to new node for quick insert
}

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

func main() {
	// Array insertion simulation
	arr := []int{1, 2, 3}
	// Insert 4 at start by shifting
	arr = append(arr, 0) // increase size
	for i := len(arr) - 1; i > 0; i-- {
		arr[i] = arr[i-1] // shift right
	}
	arr[0] = 4
	fmt.Println("Array after insert:", arr)

	// Linked list insertion
	ll := LinkedList{}
	ll.InsertAtStart(3)
	ll.InsertAtStart(2)
	ll.InsertAtStart(1)
	ll.InsertAtStart(4)
	fmt.Print("Linked List after insert: ")
	ll.Print()
}

newNode.next = ll.head // connect new node to existing list start

connect new node to existing list start

ll.head = newNode // move head pointer to new node for quick insert

move head pointer to new node for quick insert

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

shift array elements right to make space at start

Output

Array after insert: [4 1 2 3]

Linked List after insert: 4 -> 1 -> 2 -> 3 -> null

Complexity Analysis

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

Space: O(n) for array due to fixed size; O(n) for linked list due to nodes but no extra shifting space

vs Alternative: Linked list is faster for insertions/deletions at start or middle because it avoids shifting elements unlike arrays

Edge Cases

Empty linked list

Insertion sets head to new node without issues

DSA Go

ll.head = newNode      // move head pointer to new node for quick insert

Array with zero length

Append creates space, then insert works normally

DSA Go

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

When to Use This Pattern

When you see frequent insertions or deletions at the start or middle of a list, reach for linked list because it avoids costly shifting of elements.

Common Mistakes

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

Mistake: Not updating head pointer after inserting new node in linked list
Fix: Always set head to new node after insertion at start

Summary

Linked list stores items connected by pointers allowing easy insertions and deletions.

Use linked list when you need fast insertions or deletions without moving many elements.

The key insight is linked list changes pointers, not positions, so it avoids costly shifts.

Practice

1. Why do we use a linked list instead of an array in some cases?

easy

A. Because linked lists allow easy insertion and deletion without shifting elements

B. Because linked lists use less memory than arrays always

C. Because linked lists provide faster access to elements by index

D. Because linked lists store elements in contiguous memory locations

Solution

1. Step 1: Understand array limitations

   Arrays store elements in contiguous memory, so inserting or deleting elements requires shifting others, which is slow.

2. Step 2: Understand linked list advantages

   Linked lists store elements in nodes linked by pointers, so insertion and deletion can be done by changing pointers without shifting.

3. Final Answer:

   Because linked lists allow easy insertion and deletion without shifting elements -> Option A

4. Quick Check:

   Insertion/deletion ease = C [OK]

Hint: Linked lists excel at insert/delete without shifting [OK]

Common Mistakes:

• Thinking linked lists always use less memory
• Believing linked lists have faster index access
• Assuming linked lists store data contiguously

2. Which of the following is the correct way to declare a node struct for a singly linked list in Go?

easy

A. type Node struct { data int; next **Node }

B. type Node struct { data int; next Node }

C. type Node struct { data *int; next *Node }

D. type Node struct { data int; next *Node }

Solution

1. Step 1: Understand pointer usage in Go structs

   For linked lists, the next field must be a pointer to the next node to avoid copying the whole struct.

2. Step 2: Check each option

   type Node struct { data int; next *Node } uses *Node pointer correctly; B uses Node (value) which causes copying; C uses *int for data which is unnecessary; D uses **Node which is double pointer and unnecessary.

3. Final Answer:

   type Node struct { data int; next *Node } -> Option D

4. Quick Check:

   Next pointer = *Node [OK]

Hint: Next node must be a pointer to avoid copying [OK]

Common Mistakes:

• Using value type instead of pointer for next
• Using pointer for data unnecessarily
• Using double pointer for next

3. What will be the output of the following Go code snippet that creates a linked list and prints its elements?

type Node struct {
    data int
    next *Node
}

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    third := &Node{data: 3}
    head.next = second
    second.next = third

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

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 1 -> 2 -> null

D. Compilation error

Solution

1. Step 1: Trace linked list creation

   Nodes created with data 1, 2, 3 linked in order: head -> second -> third.

2. Step 2: Trace printing loop

   Loop prints data of current node then moves to next until nil, so prints 1, 2, 3 in order, then prints "null".

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option B

4. Quick Check:

   Print order matches linked list order [OK]

Hint: Follow next pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to print null at end
• Assuming reverse order

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

type Node struct {
    data int
    next *Node
}

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    head.next = second

    newNode := &Node{data: 4}
    newNode.next = head.next
    head = newNode
}

medium

A. No bug; code works correctly

B. The newNode.next should be nil

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

D. The second node is lost because head.next is nil

Solution

1. Step 1: Understand intended insertion

   The goal is to insert newNode after head, so newNode.next should point to head.next, then head.next should point to newNode.

2. Step 2: Identify bug in code

   The code sets newNode.next = head.next correctly but then overwrites head pointer itself with newNode, losing original head node and breaking list.

3. Final Answer:

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

4. Quick Check:

   Head pointer changed incorrectly = D [OK]

Hint: Insert by changing next pointers, not head itself [OK]

Common Mistakes:

• Overwriting head instead of head.next
• Not linking newNode.next properly
• Assuming newNode.next should be nil

5. You want to implement a playlist where songs can be added or removed anywhere efficiently. Why is a linked list a better choice than an array for this use case?

hard

A. Because linked lists allow dynamic memory allocation and efficient insertions/removals anywhere

B. Because linked lists provide faster random access to songs by index

C. Because arrays automatically resize without overhead

D. Because linked lists store all songs contiguously in memory

Solution

1. Step 1: Understand playlist operations

   Adding/removing songs anywhere means frequent insertions and deletions at arbitrary positions.

2. Step 2: Compare array and linked list

   Arrays require shifting elements on insert/delete, which is slow. Linked lists use pointers to insert/delete nodes efficiently without shifting.

3. Final Answer:

   Because linked lists allow dynamic memory allocation and efficient insertions/removals anywhere -> Option A

4. Quick Check:

   Efficient insert/delete = A [OK]

Hint: Linked lists excel at dynamic insertions/removals [OK]

Common Mistakes:

• Thinking linked lists have faster random access
• Assuming arrays resize without cost
• Believing linked lists store data contiguously