Linked List vs Array When to Choose Which in DSA Go - Complexity Comparison

Time Complexity: Linked List vs Array When to Choose Which

O(1) for array access, O(n) for linked list access and adding at end without tail pointer

Understanding Time Complexity

Choosing between a linked list and an array depends on how fast operations run as data grows.

We want to know which data structure handles adding, removing, and accessing items better as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of adding and accessing elements in arrays and linked lists.

// Adding element at end in array
func addToArray(arr []int, val int) []int {
    return append(arr, val)
}

// Adding element at end in linked list
func addToLinkedList(head *Node, val int) *Node {
    newNode := &Node{val, nil}
    if head == nil {
        return newNode
    }
    current := head
    for current.next != nil {
        current = current.next
    }
    current.next = newNode
    return head
}

// Access element at index in array
func accessArray(arr []int, index int) int {
    return arr[index]
}

// Access element at index in linked list
func accessLinkedList(head *Node, index int) int {
    current := head
    for i := 0; i < index; i++ {
        current = current.next
    }
    return current.val
}

This code shows how to add elements at the end and access elements by index in arrays and linked lists.

Identify Repeating Operations

Look at loops and repeated steps in the code.

• Primary operation for adding to array: append operation, usually fast without loop.
• Primary operation for adding to linked list: loop through nodes to find the end (repeats for each element).
• Primary operation for accessing array: direct access by index, no loop.
• Primary operation for accessing linked list: loop through nodes up to the index.

How Execution Grows With Input

As the list size grows, how do these operations change?

Input Size (n)	Array Add End	Linked List Add End	Array Access	Linked List Access
10	~1 operation	~10 operations	1 operation	10 operations
100	~1 operation	~100 operations	1 operation	100 operations
1000	~1 operation	~1000 operations	1 operation	1000 operations

Adding to array is usually fast but can slow if resizing happens. Adding to linked list always needs to walk to the end, so it grows with size. Accessing array is always quick, but linked list access grows with index.

Final Time Complexity

Time Complexity: O(1) for array access, O(n) for linked list access and adding at end without tail pointer

This means arrays let you quickly get any item, while linked lists take longer as they grow when you add or get items by position.

Common Mistake

[X] Wrong: "Linked lists are always faster for adding elements than arrays."

[OK] Correct: Without a pointer to the end, linked lists must walk through all nodes to add at the end, making it slower than arrays that add at the end quickly most times.

Interview Connect

Understanding these differences helps you pick the right data structure for your problem and explain your choice clearly in interviews.

Self-Check

"What if the linked list kept a pointer to the last node? How would adding at the end change time complexity?"

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