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.