Linked List vs Array When to Choose Which in DSA Go - Why the Distinction Matters

The Big Idea

Discover why choosing the right list can save you from slow, frustrating code!

The Scenario

Imagine you have a list of your favorite songs written on paper. You want to add a new song in the middle or remove one quickly. If you wrote them all in a row on a single sheet (like an array), adding or removing songs means rewriting many names. This is tiring and slow.

The Problem

Using a simple list on paper (array) means every time you add or remove a song in the middle, you must shift all the following songs up or down. This takes time and can cause mistakes, especially with long lists.

The Solution

A linked list is like having each song on a separate card, connected by strings. To add or remove a song, you just change the strings between cards without moving all cards. This makes changes faster and easier.

Before vs After

✗ Before

songs := []string{"Song1", "Song2", "Song3"}
// Insert "NewSong" at position 1
songs = append(songs[:1], append([]string{"NewSong"}, songs[1:]...)...)
// This shifts all songs after position 1

✓ After

type Node struct {
    song string
    next *Node
}

// Insert "NewSong" after first node
newNode := &Node{song: "NewSong"}
newNode.next = head.next
head.next = newNode
// Only links change, no shifting

What It Enables

This choice lets you pick the best way to store and change your list, making your program faster and easier to manage.

Real Life Example

Think of a music playlist app: if you often add or remove songs anywhere, a linked list helps. If you mostly play songs in order and rarely change the list, an array is simpler and faster.

Key Takeaways

Arrays store items in order and are fast to access by position.

Linked lists connect items with links, making insertions and deletions easier.

Choosing depends on how you use the list: frequent changes favor linked lists; fixed lists favor arrays.

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