Insert at Beginning Head Insert in DSA Python

Mental Model

Add a new item right at the start so it becomes the first thing in the list.

Analogy: Imagine putting a new book on the front of a line of books on a shelf, pushing the others back.

head -> 1 -> 2 -> 3 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null, insert value 0 at beginning

Goal: Add 0 at the start so the list becomes 0 -> 1 -> 2 -> 3 -> null

Step 1: Create new node with value 0

new_node(0) -> null, head -> 1 -> 2 -> 3 -> null

Why: We need a new node to insert at the beginning

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

new_node(0) -> 1 -> 2 -> 3 -> null, head -> 1 -> 2 -> 3 -> null

Why: Link new node to the existing list so it connects properly

Step 3: Update head to new node (0)

head -> 0 -> 1 -> 2 -> 3 -> null

Why: New node becomes the first node in the list

Result:

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_beginning(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):
        result = []
        curr = self.head
        while curr:
            result.append(str(curr.val))
            curr = curr.next
        return ' -> '.join(result) + ' -> null'

# Driver code
ll = LinkedList()
ll.insert_at_beginning(3)
ll.insert_at_beginning(2)
ll.insert_at_beginning(1)
print("Before insertion:", ll)
ll.insert_at_beginning(0)
print("After insertion:", ll)

new_node = Node(val) # create new node

create a new node with the given value

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

point new node's next to current head to connect list

self.head = new_node # update head to new node

make new node the new head of the list

Output

Before insertion: 1 -> 2 -> 3 -> null

After insertion: 0 -> 1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(1) because we only change a few pointers without traversing the list

Space: O(1) because we create only one new node regardless of list size

vs Alternative: Compared to inserting at the end which requires O(n) time to find the last node, inserting at the beginning is faster and simpler

Edge Cases

empty list

new node becomes the head and points to null

DSA Python

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

single element list

new node points to the existing single node, becomes new head

DSA Python

self.head = new_node  # update head to new node

When to Use This Pattern

When you need to add an item quickly at the start of a list, use head insert because it avoids traversing the list.

Common Mistakes

Mistake: Forgetting to update the head pointer to the new node
Fix: Always assign the new node to head after linking it to the old head

Mistake: Not linking the new node's next to the old head, causing list loss
Fix: Set new_node.next to current head before updating head

Summary

Adds a new node at the start of a linked list.

Use when you want to quickly add elements to the front without traversing.

The new node points to the old head, then becomes the new head.

Practice

1. What does the operation insert at beginning do in a linked list?

easy

A. Deletes the first node of the list

B. Adds a new node at the start of the list

C. Adds a new node at the end of the list

D. Deletes the last node of the list

Solution

1. Step 1: Understand the meaning of 'insert at beginning'

   Inserting at the beginning means adding a new element before the current first element.

2. Step 2: Identify the effect on the linked list

   The new node becomes the new head, pushing the old head to second position.

3. Final Answer:

   Adds a new node at the start of the list -> Option B

4. Quick Check:

   Insert at beginning = Add new head [OK]

Hint: Insert at beginning means new head node [OK]

Common Mistakes:

• Confusing insert at beginning with insert at end
• Thinking it deletes nodes instead of adding
• Assuming it changes the last node

2. Which of the following is the correct syntax to insert a new node at the beginning of a singly linked list in Python?

easy

A. new_node = head.next; head = new_node

B. head.next = new_node; new_node = head

C. head = head.next; new_node = head

D. new_node.next = head; head = new_node

Solution

1. Step 1: Understand pointer assignment for head insert

   To insert at beginning, new_node's next points to current head.

2. Step 2: Update head to new_node

   Then head is updated to new_node to make it the first node.

3. Final Answer:

   new_node.next = head; head = new_node -> Option D

4. Quick Check:

   Set new_node.next to head, then head = new_node [OK]

Hint: Link new node to head, then update head [OK]

Common Mistakes:

• Assigning head.next instead of new_node.next
• Not updating head to new_node
• Swapping assignment order incorrectly

3. What will be the linked list after executing the following code?

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

head = Node(10)
new_node = Node(20)
new_node.next = head
head = new_node

medium

A. 20 -> 10 -> null

B. 10 -> 20 -> null

C. 20 -> null

D. 10 -> null

Solution

1. Step 1: Create initial list with head node 10

   Initially, head points to node with data 10 and next is None.

2. Step 2: Insert new_node with data 20 at beginning

   new_node.next points to head (node 10), then head updated to new_node.

3. Final Answer:

   20 -> 10 -> null -> Option A

4. Quick Check:

   New node 20 becomes head, points to 10 [OK]

Hint: New node points to old head, then becomes head [OK]

Common Mistakes:

• Thinking new_node is added at end
• Not updating head to new_node
• Confusing node data order

4. Identify the error in this code snippet that tries to insert a node at the beginning of a linked list:

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

head = Node(5)
new_node = Node(15)
head = new_node
new_node.next = head

medium

A. The order of assignments is wrong; new_node.next should be set before head update

B. Node class is missing a data attribute

C. head should be None initially

D. new_node should not be created before head

Solution

1. Step 1: Analyze assignment order

   head is set to new_node first, then new_node.next is set to head (which is now new_node itself).

2. Step 2: Identify logical error

   This causes new_node.next to point to itself, losing original list starting at old head.

3. Final Answer:

   The order of assignments is wrong; new_node.next should be set before head update -> Option A

4. Quick Check:

   Set new_node.next before head = new_node [OK]

Hint: Set new_node.next before updating head [OK]

Common Mistakes:

• Updating head before linking new_node.next
• Confusing attribute initialization
• Assuming head must be None initially

5. Given a linked list with nodes containing values [30, 20, 10] (30 is head), which sequence of operations correctly inserts a new node with value 40 at the beginning and results in the list 40 -> 30 -> 20 -> 10 -> null?

hard

A. new_node = Node(40); new_node.next = None; head = new_node

B. new_node = Node(40); head.next = new_node; head = new_node

C. new_node = Node(40); new_node.next = head; head = new_node

D. new_node = Node(40); head = new_node; new_node.next = head

Solution

1. Step 1: Create new node with value 40

   new_node is created with data 40 and next initially None.

2. Step 2: Link new_node to current head

   Set new_node.next to current head (node 30) to keep existing list after new node.

3. Step 3: Update head to new_node

   Head pointer is updated to new_node, making it the first node.

4. Final Answer:

   new_node = Node(40); new_node.next = head; head = new_node -> Option C

5. Quick Check:

   Link new node to old head, then update head [OK]

Hint: Link new node to head, then update head pointer [OK]

Common Mistakes:

• Linking head.next instead of new_node.next
• Updating head before linking new_node.next
• Setting new_node.next to None losing list