Linked List vs Array When to Choose Which in DSA Go - Build Both Approaches

Linked List vs Array: When to Choose Which

📖 Scenario: Imagine you are building a simple contact list app. You want to store contacts and decide whether to use an array or a linked list based on how you will use the data.

🎯 Goal: Learn how to create and use an array and a linked list in Go, and understand when to choose each based on operations like adding, removing, and accessing contacts.

📋 What You'll Learn

Create an array of contacts with exact names

Create a linked list node struct for contacts

Add contacts to the linked list

Print both data structures to compare

💡 Why This Matters

🌍 Real World

Contact lists, music playlists, and task queues often use arrays or linked lists depending on how data changes.

💼 Career

Understanding when to use arrays or linked lists helps in writing efficient code for software development and system design.

1

Create an array of contacts

Create an array called contactsArray with these exact names: "Alice", "Bob", "Charlie".

DSA Go

# Create an array called contactsArray with "Alice", "Bob", "Charlie"
// Your code here

Hint

Use Go's array syntax with fixed size and initialize with the exact names.

2

Define a linked list node for contacts

Define a struct called ContactNode with a field name of type string and a pointer next to ContactNode.

DSA Go

package main

import "fmt"

type ContactNode struct {
    // Your code here
}

func main() {
    contactsArray := [3]string{"Alice", "Bob", "Charlie"}
}

Hint

Use type ContactNode struct with name string and next *ContactNode.

3

Create a linked list with contacts

In main, create three ContactNode variables named node1, node2, and node3 with names "Alice", "Bob", and "Charlie" respectively. Link them so node1.next points to node2 and node2.next points to node3. Set node3.next to nil. Create a variable head pointing to node1.

DSA Go

package main

import "fmt"

type ContactNode struct {
    name string
    next *ContactNode
}

func main() {
    contactsArray := [3]string{"Alice", "Bob", "Charlie"}
    // Create node1, node2, node3 with names and link them
    // Your code here
}

Hint

Create each node with the exact name, link them by setting next pointers, and assign head to &node1.

4

Print both array and linked list contacts

Print the contacts in contactsArray using a for loop with index i. Then print the linked list starting from head by traversing nodes using a variable current until nil. Print each contact name on its own line prefixed by "Array: " or "List: " respectively.

DSA Go

Hint

Use a for loop with index i for the array, and a for loop with current != nil for the linked list.

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