Why Linked List Exists and What Problem It Solves in DSA Python - Why This Pattern

Mental Model

A linked list is a way to store items so you can add or remove them easily without moving everything around.

Analogy: Imagine a treasure hunt where each clue tells you where the next clue is hidden. You only need to follow the clues one by one, not carry all clues at once.

Head -> [1] -> [2] -> [3] -> null

Dry Run Walkthrough

Input: array: [1, 2, 3], insert 0 at start

Goal: Show how adding an item at the start is easy in a linked list but hard in an array

Step 1: Try to insert 0 at start of array

[1, 2, 3]

Why: In an array, we must move all items to make space for 0

Step 2: Shift all elements right by one position

[_, 1, 2, 3]

Why: We move each element to the right to free the first spot

Step 3: Place 0 at index 0

[0, 1, 2, 3]

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

Step 4: Insert 0 at start of linked list

Head -> [0] -> [1] -> [2] -> [3] -> null

Why: In linked list, just create new node and point it to old head

Result:

Array after insert: [0, 1, 2, 3]
Linked list after insert: Head -> [0] -> [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  # point new node to current head
        self.head = new_node  # update head to new node

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

# Array insert simulation
arr = [1, 2, 3]
# Insert 0 at start by shifting
arr = [0] + arr  # shifting all elements right
print('Array after insert:', arr)

# Linked list insert
ll = LinkedList()
for v in reversed([1, 2, 3]):
    ll.insert_at_start(v)
ll.insert_at_start(0)  # insert 0 at start
print('Linked list after insert:')
ll.print_list()

new_node = Node(val) # create new node

create a new node to hold the value

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

link new node to the current first node

self.head = new_node # update head to new node

make new node the first node in the list

arr = [0] + arr # shifting all elements right

simulate array insert by creating new array with 0 at front

Output

Array after insert: [0, 1, 2, 3]

Linked list after insert:

Head -> 0 -> 1 -> 2 -> 3 -> null

Complexity Analysis

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

Space: O(n) for array insert due to creating new array; O(1) for linked list insert as no extra space except one node

vs Alternative: Linked list insert is faster and simpler for adding at start compared to array which needs shifting all elements

Edge Cases

empty linked list

inserting at start just sets head to new node

DSA Python

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

array insert with empty array

inserting 0 results in array [0]

DSA Python

arr = [0] + arr  # shifting all elements right

When to Use This Pattern

When you see a problem where adding or removing items at the start or middle is slow because everything shifts, think of linked lists to speed it up by changing pointers.

Common Mistakes

Mistake: Trying to insert at start of array without shifting elements
Fix: Remember arrays need shifting; linked lists do not

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

Summary

Linked lists let you add or remove items easily without moving everything.

Use linked lists when you need fast insertions or deletions at the start or middle.

The key is that each item points to the next, so you just change pointers instead of moving data.