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

Time Complexity: Linked List vs Array When to Choose Which

O(1) for array access, O(n) for linked list access; O(n) for array insert at start, O(1) for linked list insert at start

Understanding Time Complexity

Choosing between a linked list and an array depends on how fast you want certain operations to run.

We want to understand how the time to do common tasks changes with the size of the data.

Scenario Under Consideration

Analyze the time complexity of basic operations on arrays and linked lists.

# Array operations
arr = [1, 2, 3, 4, 5]
arr.append(6)          # Add at end
arr.insert(0, 0)      # Add at start
value = arr[3]        # Access by index

# Linked List operations
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

head = Node(1)
head.next = Node(2)
# Add at start: new_node.next = head; head = new_node
# Access by index: traverse nodes one by one

This code shows how arrays and linked lists perform adding and accessing elements.

Identify Repeating Operations

Look at what repeats when we do operations:

• Primary operation: Accessing elements by index in linked list requires walking through nodes one by one.
• How many times: Up to n times for linked list; arrays access directly in one step.

How Execution Grows With Input

As the list or array grows, the time to access or insert changes differently.

Input Size (n)	Array Access	Linked List Access	Array Insert at Start	Linked List Insert at Start
10	1 op (1 step)	10 ops (up to 10 steps)	10 ops (shift elements)	1 op (change head)
100	1 op (1 step)	100 ops (up to 100 steps)	100 ops (shift elements)	1 op (change head)
1000	1 op (1 step)	1000 ops (up to 1000 steps)	1000 ops (shift elements)	1 op (change head)

Pattern observation: Array access stays fast; linked list access grows linearly. Inserting at start is slow for arrays but fast for linked lists.

Final Time Complexity

Time Complexity: O(1) for array access, O(n) for linked list access; O(n) for array insert at start, O(1) for linked list insert at start

This means arrays are best for quick access, while linked lists are better for fast insertions at the start.

Common Mistake

[X] Wrong: "Linked lists are always slower than arrays because they use pointers."

[OK] Correct: Linked lists can be faster for some operations like adding or removing at the start because they don't need to move other elements.

Interview Connect

Understanding these differences helps you choose the right data structure for the task, a skill interviewers value highly.

Self-Check

"What if we needed to insert elements only at the end? How would the time complexity for arrays and linked lists compare then?"

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Linked List

B. Array

C. Stack

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing by index is fast and direct.

2. Step 2: Compare with linked list access

   Linked lists require traversal from the head to reach an index, which is slower.

3. Final Answer:

   Array -> Option B

4. Quick Check:

   Random access = Array [OK]

Hint: Arrays allow direct index access; linked lists do not [OK]

Common Mistakes:

• Thinking linked lists provide fast index access
• Confusing stack or queue with random access
• Assuming all data structures have same access speed

2. Which of the following is the correct way to declare an empty linked list node in Python?

easy

A. node = LinkedList()

B. node = []

C. node = None

D. node = Node()

Solution

1. Step 1: Understand linked list node creation

   A linked list node is usually an instance of a Node class, so Node() creates an empty node.

2. Step 2: Compare other options

   Empty list [] is for arrays, None is absence of value, LinkedList() is the whole list, not a node.

3. Final Answer:

   node = Node() -> Option D

4. Quick Check:

   Node creation = Node() [OK]

Hint: Use Node() to create linked list nodes, not list or None [OK]

Common Mistakes:

• Using [] which is for arrays, not nodes
• Assigning None instead of a node object
• Confusing linked list with whole list object

3. What will be the output of the following Python code?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

arr = [10, 20, 30]
linked_list = Node(10)
linked_list.next = Node(20)
linked_list.next.next = Node(30)
print(arr[1], linked_list.next.data)

medium

A. 20 20

B. 10 20

C. 20 10

D. 30 30

Solution

1. Step 1: Access array element at index 1

   arr[1] is 20 because arrays allow direct index access.

2. Step 2: Access linked list second node data

   linked_list.next points to node with data 20, so linked_list.next.data is 20.

3. Final Answer:

   20 20 -> Option A

4. Quick Check:

   arr[1] and linked_list.next.data both 20 [OK]

Hint: Array index 1 and linked list next node data match [OK]

Common Mistakes:

• Confusing linked list node data with array index
• Mixing up indices or next pointers
• Assuming linked list nodes are accessed by index

4. Find the error in this linked list insertion code snippet:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(1)
head.next = Node(2)
new_node = Node(3)
new_node.next = head
head = new_node
print(head.next.next.data)

medium

A. Error: new_node.next should be None

B. Error: head.next.next is None, so accessing data causes AttributeError

C. No error, output is 2

D. Error: head should not be reassigned

Solution

1. Step 1: Trace linked list after insertion

   new_node points to old head (1), so list is 3 -> 1 -> 2.

2. Step 2: Check head.next.next

   head.next is node with data 1, head.next.next is node with data 2, so head.next.next.data is 2, no error.

3. Step 3: Re-examine code print statement

   Actually, print(head.next.next.data) should print 2 without error.

4. Final Answer:

   No error, output is 2 -> Option C

5. Quick Check:

   Linked list traversal works, output 2 [OK]

Hint: Trace pointers carefully to find if None is accessed [OK]

Common Mistakes:

• Assuming head.next.next is None incorrectly
• Thinking reassignment of head is wrong
• Confusing next pointer assignments

5. You have a large dataset where you frequently insert and delete elements in the middle. Which data structure is more efficient and why?

hard

A. Linked List, because insertion and deletion in middle are faster

B. Array, because it uses less memory

C. Array, because it supports random access

D. Linked List, because it uses contiguous memory

Solution

1. Step 1: Analyze insertion and deletion in arrays

   Arrays require shifting elements after insertion/deletion, which is slow for large data.

2. Step 2: Analyze linked list operations

   Linked lists adjust pointers for insertion/deletion without shifting, making these operations faster in the middle.

3. Step 3: Compare memory usage and access

   Linked lists use more memory due to pointers and have slower random access, but faster middle updates.

4. Final Answer:

   Linked List, because insertion and deletion in middle are faster -> Option A

5. Quick Check:

   Middle insert/delete fast = Linked List [OK]

Hint: For frequent middle changes, linked list is faster [OK]

Common Mistakes:

• Choosing array for fast middle insert/delete
• Confusing memory use with operation speed
• Assuming linked list uses contiguous memory