Linked List vs Array When to Choose Which in DSA Python - Trade-offs & Analysis

Mental Model

Arrays store items in order in one block of memory, while linked lists chain items with pointers. This affects how fast you can add, remove, or find items.

Analogy: Think of an array like a row of mailboxes all in one building, easy to find by number but hard to add new mailboxes in the middle. A linked list is like a treasure hunt where each clue points to the next spot, so adding new clues is easy but finding a specific one takes time.

Array: [1][2][3][4][5]
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Dry Run Walkthrough

Input: Array: [1, 2, 3], Insert 4 at start; Linked List: 1 -> 2 -> 3, Insert 4 at start

Goal: Show how insertion at the start differs in arrays and linked lists

Step 1: Shift all array elements right to make space at start

[_][1][2][3]

Why: Array needs to move elements to keep order and make room

Step 2: Insert 4 at array index 0

[4][1][2][3]

Why: Now 4 is at the start, but shifting took time

Step 3: Create new linked list node with value 4

4 -> null

Why: Prepare new node to add at start

Step 4: Point new node's next to current head (1)

4 -> 1 -> 2 -> 3 -> null

Why: Link new node to existing list to keep order

Step 5: Update head pointer to new node (4)

4 -> 1 -> 2 -> 3 -> null

Why: New node becomes the first element in the list

Result:

Array after insertion: [4][1][2][3]
Linked List after insertion: 4 -> 1 -> 2 -> 3 -> null

Annotated Code

DSA Python

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

class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_start(self, val):
        new_node = Node(val)  # create new node
        new_node.next = self.head  # link new node to current head
        self.head = new_node  # update head to new node

    def __str__(self):
        curr = self.head
        result = []
        while curr:
            result.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(result) + ' -> null'

def insert_at_start_array(arr, val):
    arr.insert(0, val)  # insert val at index 0, shifts elements right

# Driver code
array = [1, 2, 3]
insert_at_start_array(array, 4)

linked_list = LinkedList()
linked_list.insert_at_start(1)
linked_list.insert_at_start(2)
linked_list.insert_at_start(3)
linked_list.insert_at_start(4)  # insert 4 at start

print('Array after insertion:', array)
print('Linked List after insertion:', linked_list)

new_node = Node(val) # create new node

create new node to insert at start

new_node.next = self.head # link new node to current head

link new node to current first node

self.head = new_node # update head to new node

update head pointer to new node

arr.insert(0, val) # insert val at index 0, shifts elements right

insert at start of array, shifts all elements right

Output

Array after insertion: [4, 1, 2, 3]

Linked List after insertion: 4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) for array insertion at start because all elements must shift; O(1) for linked list insertion at start because only pointers change

Space: O(n) for array storing all elements contiguously; O(n) for linked list storing nodes separately with extra pointer space

vs Alternative: Linked lists are faster for insertions/deletions at start or middle but slower for random access; arrays are faster for random access but slower for insertions/deletions except at the end

Edge Cases

Empty array or linked list

Insertion simply adds the first element without shifting or linking

DSA Python

new_node.next = self.head  # link new node to current head

Single element array or linked list

Insertion at start shifts one element in array or links one node in list

DSA Python

arr.insert(0, val)  # insert val at index 0, shifts elements right

When to Use This Pattern

When you need fast insertions or deletions at the start or middle of a collection, think linked list; when you need fast random access by index, think array.

Common Mistakes

Mistake: Trying to insert at start of array without shifting elements
Fix: Use array.insert(0, val) to shift elements automatically

Mistake: Not updating the head pointer after inserting new node in linked list
Fix: Always set head to new node after insertion at start

Summary

Compares when to use linked lists versus arrays based on insertion and access needs.

Use linked lists for fast insertions/deletions at start or middle; use arrays for fast random access.

Arrays store items contiguously needing shifts on insertions; linked lists use pointers allowing quick insertions but slower access.

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