Linked List vs Array When to Choose Which in DSA Go - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is a linked list better than an array?

Choose the best scenario where using a linked list is more suitable than an array.

A When you want to minimize memory usage by storing elements contiguously.

B When you need to sort elements quickly using built-in array methods.

C When you frequently insert or delete elements in the middle of the collection.

D When you need fast random access to elements by index.

💡 Hint

Think about which data structure allows easy insertion and deletion without shifting elements.

Linked lists allow fast insertion and deletion anywhere because they use pointers, unlike arrays which require shifting elements.

🧠 Conceptual

intermediate

Why might arrays be preferred over linked lists?

Pick the main advantage of arrays compared to linked lists.

A Arrays provide faster access to elements by index.

B Arrays use more memory due to storing pointers for each element.

C Arrays allow easier insertion and deletion anywhere in the list.

D Arrays can grow dynamically without any overhead.

💡 Hint

Consider which data structure supports direct access to any element quickly.

Arrays store elements contiguously, so accessing any element by index is very fast, unlike linked lists which require traversal.

❓ Predict Output

advanced

Output of linked list insertion vs array insertion

What is the output after inserting element 99 at index 2 in both an array and a linked list?

DSA Go

package main

import "fmt"

type Node struct {
    val  int
    next *Node
}

func insertArray(arr []int, index int, val int) []int {
    arr = append(arr, 0)
    copy(arr[index+1:], arr[index:])
    arr[index] = val
    return arr
}

func insertLinkedList(head *Node, index int, val int) *Node {
    newNode := &Node{val: val}
    if index == 0 {
        newNode.next = head
        return newNode
    }
    curr := head
    for i := 0; i < index-1 && curr != nil; i++ {
        curr = curr.next
    }
    if curr == nil {
        return head
    }
    newNode.next = curr.next
    curr.next = newNode
    return head
}

func printLinkedList(head *Node) {
    for curr := head; curr != nil; curr = curr.next {
        fmt.Print(curr.val)
        if curr.next != nil {
            fmt.Print(" -> ")
        }
    }
    fmt.Println(" -> null")
}

func main() {
    arr := []int{10, 20, 30, 40}
    arr = insertArray(arr, 2, 99)
    fmt.Println(arr)

    head := &Node{val: 10}
    head.next = &Node{val: 20}
    head.next.next = &Node{val: 30}
    head.next.next.next = &Node{val: 40}
    head = insertLinkedList(head, 2, 99)
    printLinkedList(head)
}

A

[10 20 99 30 40]
10 -> 20 -> 99 -> 30 -> 40 -> null

B

[10 20 30 99 40]
10 -> 20 -> 30 -> 99 -> 40 -> null

C

[10 20 99 30 40]
10 -> 20 -> 30 -> 99 -> 40 -> null

D

[10 20 30 40 99]
10 -> 20 -> 99 -> 30 -> 40 -> null

💡 Hint

Remember that insertion at index 2 means the new element goes before the old element at index 2.

Inserting 99 at index 2 shifts elements in the array and inserts the node at the correct position in the linked list.

❓ Predict Output

advanced

What error occurs when accessing an invalid index in array vs linked list?

What happens when you try to access index 5 in an array of length 4 and traverse 5 nodes in a linked list of length 4?

DSA Go

package main

import "fmt"

func main() {
    arr := []int{1, 2, 3, 4}
    fmt.Println(arr[5])

    type Node struct {
        val  int
        next *Node
    }

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

    curr := head
    for i := 0; i < 5; i++ {
        if curr == nil {
            fmt.Println("Reached end of linked list")
            break
        }
        fmt.Println(curr.val)
        curr = curr.next
    }
}

A Prints 1 2 3 4 5 for both array and linked list without error

B Runtime panic for linked list traversal; array prints 1 2 3 4

C Compile error due to invalid array access; linked list prints 1 2 3 4 5

D Runtime panic: index out of range for array; prints 1 2 3 4 then 'Reached end of linked list'

💡 Hint

Think about how Go handles out-of-bounds array access and linked list traversal.

Accessing arr[5] causes a runtime panic because the index is out of range. Linked list traversal stops safely when reaching nil.

🚀 Application

expert

Choosing data structure for a text editor buffer

You are designing a text editor. The buffer needs to support fast insertions and deletions anywhere, and also fast sequential access for rendering. Which data structure is best?

A Hash map, because it provides fast key-based access to characters.

B Linked list, because it allows fast insertions and deletions anywhere without shifting elements.

C Array, because it provides fast random access and is simple to implement.

D Stack, because it supports fast push and pop operations.

💡 Hint

Consider which data structure balances fast insertions/deletions and sequential access.

Linked lists allow fast insertions and deletions anywhere without shifting elements, which is important for text editing. Arrays have slow insertions/deletions in the middle.

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