Linked List vs Array When to Choose Which in DSA Go - Key Differences

Recall & Review

beginner

What is a key advantage of using an array over a linked list?

Arrays provide fast access to elements by index because they store elements in contiguous memory locations.

beginner

Why might you choose a linked list instead of an array when you expect many insertions and deletions?

Linked lists allow easy insertion and deletion without shifting elements, making these operations faster than in arrays.

beginner

What is a disadvantage of linked lists compared to arrays?

Linked lists use extra memory for storing pointers and have slower access time because elements are not stored contiguously.

intermediate

In which scenario is an array a better choice than a linked list?

When you need fast random access to elements and the size of the data is fixed or changes rarely.

intermediate

How does memory allocation differ between arrays and linked lists?

Arrays allocate memory in a single contiguous block, while linked lists allocate memory for each element separately and link them with pointers.

Which data structure allows faster insertion at the beginning?

A Array

B Neither

C Both are equal

D Linked List

Linked lists can insert at the beginning by changing pointers, while arrays require shifting elements.

What is the time complexity to access the 5th element in an array?

A O(n^2)

B O(n)

C O(1)

D O(log n)

Arrays provide constant time access to elements by index.

Which data structure uses extra memory for pointers?

A Array

B Linked List

C Both

D None

Linked lists store pointers to the next element, using extra memory.

When is an array NOT a good choice?

A When the size changes frequently

B When you need fast random access

C When data is fixed size

D When memory is contiguous

Arrays have fixed size or resizing costs; frequent size changes make linked lists better.

Which data structure requires shifting elements during insertion in the middle?

A Array

B Both

C Linked List

D Neither

Arrays require shifting elements to insert in the middle; linked lists just change pointers.

Explain when you would choose a linked list over an array and why.

Think about operations that involve changing the list size often.

Describe the main differences in memory layout between arrays and linked lists.

Consider how elements are stored and accessed.

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