Insert at Beginning of Circular Linked List in DSA Python

Mental Model

A circular linked list connects the last node back to the first, forming a loop. Inserting at the beginning means adding a new node before the current head and updating the last node to point to this new node.

Analogy: Imagine people sitting in a circle holding hands. To add a new person at the start, you place them before the first person and make sure the last person now holds hands with the new person, keeping the circle unbroken.

head -> 1 -> 2 -> 3 -> back to head (1)

Before insertion:
head -> [1] -> 2 -> 3 -> back to [1]

After insertion of 0:
head -> [0] -> 1 -> 2 -> 3 -> back to [0]

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 0 at beginning

Goal: Add a new node with value 0 at the start and keep the list circular

Step 1: Create new node with value 0

new_node(0) isolated, list: head -> [1] -> 2 -> 3 -> back to [1]

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

Step 2: Find last node (node with value 3) to update its next pointer

head -> 1 -> 2 -> [3] -> back to [1], new_node(0) isolated

Why: Last node must point to new first node to keep circular

Step 3: Set new_node.next to current head (node 1)

new_node(0) -> 1 -> 2 -> 3 -> back to [1]

Why: New node points to old first node, becoming new head

Step 4: Update last node's next pointer to new_node

head -> 1 -> 2 -> 3 -> back to [0], new_node(0) -> 1

Why: Last node now points to new first node to maintain circle

Step 5: Update head pointer to new_node

head -> [0] -> 1 -> 2 -> 3 -> back to [0]

Why: Head must point to new first node after insertion

Result:

head -> 0 -> 1 -> 2 -> 3 -> back to head (0)

Annotated Code

DSA Python

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

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

    def insert_at_beginning(self, data):
        new_node = Node(data)  # create new node
        if not self.head:
            new_node.next = new_node  # points to itself if list empty
            self.head = new_node
            return
        # find last node
        curr = self.head
        while curr.next != self.head:
            curr = curr.next
        new_node.next = self.head  # new node points to old head
        curr.next = new_node      # last node points to new node
        self.head = new_node      # update head to new node

    def __str__(self):
        if not self.head:
            return "empty"
        result = []
        curr = self.head
        while True:
            result.append(str(curr.data))
            curr = curr.next
            if curr == self.head:
                break
        return " -> ".join(result) + " -> back to head (" + str(self.head.data) + ")"

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

new_node = Node(data) # create new node

create new node to insert

if not self.head:

handle empty list by pointing new node to itself

curr = self.head while curr.next != self.head: curr = curr.next

find last node to update its next pointer

new_node.next = self.head

new node points to old head

curr.next = new_node

last node points to new node to maintain circular link

self.head = new_node

update head to new node

Output

Before insertion: 1 -> 2 -> 3 -> back to head (1)

After insertion: 0 -> 1 -> 2 -> 3 -> back to head (0)

Complexity Analysis

Time: O(n) because we must traverse the list to find the last node before insertion

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to a singly linked list insertion at beginning which is O(1), circular list insertion requires O(n) to update the last node's pointer

Edge Cases

empty list

new node points to itself and becomes head

DSA Python

if not self.head:

single node list

last node is the head itself; new node inserted before it and last node updated

DSA Python

while curr.next != self.head:

When to Use This Pattern

When you see a linked list where the last node points back to the first, and you need to add a node at the start, use the insert at beginning pattern for circular linked lists to maintain the loop.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new head, breaking the circular link
Fix: Always find the last node and set its next pointer to the new node before updating head

Mistake: Forgetting to handle the empty list case where head is None
Fix: Check if head is None and make new node point to itself and set head to new node

Summary

Adds a new node at the start of a circular linked list and updates pointers to keep the circle intact.

Use when you need to insert at the beginning of a circular linked list while preserving its circular nature.

Remember to update the last node's next pointer to the new node and then update the head pointer.

Practice

1. What happens when you insert a new node at the beginning of a circular linked list?

easy

A. The new node replaces the last node in the list.

B. The new node becomes the head and points to the old head, maintaining the circular link.

C. The list breaks and becomes a linear linked list.

D. The new node is added at the end and does not affect the head.

Solution

1. Step 1: Understand the circular linked list structure

   A circular linked list has its last node pointing back to the head node, forming a circle.

2. Step 2: Insert new node at beginning

   The new node is linked to the current head, and the last node's next pointer is updated to this new node, making it the new head.

3. Final Answer:

   The new node becomes the head and points to the old head, maintaining the circular link. -> Option B

4. Quick Check:

   New head points to old head, last node points to new head [OK]

Hint: New head points to old head, last node points to new head [OK]

Common Mistakes:

• Forgetting to update last node's next pointer
• Breaking the circular link by not linking last node
• Replacing the last node instead of adding new head

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

easy

A. new_node = Node(data); new_node.next = head; head = new_node

B. new_node = Node(data); last.next = head; head = new_node

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

D. new_node = Node(data); new_node.next = head; last.next = new_node; head = new_node

Solution

1. Step 1: Create new node and link to current head

   We create a new node and set its next pointer to the current head.

2. Step 2: Update last node's next pointer and head

   Since it's circular, last node's next must point to new node, then update head to new node.

3. Final Answer:

   new_node = Node(data); new_node.next = head; last.next = new_node; head = new_node -> Option D

4. Quick Check:

   New node points to old head, last points to new node, head updated [OK]

Hint: Update last.next to new node before changing head [OK]

Common Mistakes:

• Not updating last.next to new node
• Changing head before updating last.next
• Linking new node incorrectly

3. What will be the output of the following code snippet after inserting 10 at the beginning of the circular linked list?

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

def print_list(head):
    temp = head
    if head is not None:
        while True:
            print(temp.data, end=' -> ')
            temp = temp.next
            if temp == head:
                break
    print('null')

# Initial circular linked list: 20 -> 30 -> 40 -> null
head = Node(20)
second = Node(30)
third = Node(40)
head.next = second
second.next = third
third.next = head

# Insert 10 at beginning
new_node = Node(10)
new_node.next = head
third.next = new_node
head = new_node

print_list(head)

medium

A. 10 -> 30 -> 40 -> 20 -> null

B. 20 -> 30 -> 40 -> 10 -> null

C. 10 -> 20 -> 30 -> 40 -> null

D. 30 -> 40 -> 20 -> 10 -> null

Solution

1. Step 1: Understand the initial list and insertion

   The list is 20 -> 30 -> 40 -> back to 20. Inserting 10 at beginning means new_node points to old head (20), and last node (40) points to new_node.

2. Step 2: Trace the print_list function

   Starting from new head (10), it prints 10, then 20, then 30, then 40, then stops when it reaches head again.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> null -> Option C

4. Quick Check:

   New head 10 followed by old nodes in order [OK]

Hint: New head prints first, then old nodes in order [OK]

Common Mistakes:

• Not updating last node's next pointer
• Printing from old head instead of new head
• Confusing order of nodes after insertion

4. Identify the error in the following code that inserts a new node at the beginning of a circular linked list:

def insert_begin(head, data):
    new_node = Node(data)
    new_node.next = head
    head = new_node
    return head

medium

A. The last node's next pointer is not updated to new_node, breaking the circular link.

B. The new_node.next should point to null instead of head.

C. The head should not be updated to new_node.

D. The function should not return head.

Solution

1. Step 1: Check pointer updates for circular list

   In a circular linked list, the last node's next pointer must point to the head node to maintain the circle.

2. Step 2: Identify missing update

   The code updates new_node.next and head but does not update the last node's next pointer to new_node, breaking the circle.

3. Final Answer:

   The last node's next pointer is not updated to new_node, breaking the circular link. -> Option A

4. Quick Check:

   Last node must point to new head to keep circle [OK]

Hint: Always update last.next to new head in circular list [OK]

Common Mistakes:

• Ignoring last node pointer update
• Setting new_node.next to null
• Not returning updated head

5. Given a circular linked list with nodes 5 -> 15 -> 25 -> back to 5, write the steps to insert a new node with value 1 at the beginning and then print the list. What will be the printed output?

hard

A. 1 -> 5 -> 15 -> 25 -> null

B. 5 -> 15 -> 25 -> 1 -> null

C. 1 -> 15 -> 25 -> 5 -> null

D. 25 -> 5 -> 15 -> 1 -> null

Solution

1. Step 1: Insert new node at beginning

   Create new node with value 1, set its next to current head (5), update last node (25) next to new node, then update head to new node.

2. Step 2: Print the circular linked list

   Start from new head (1), print nodes in order: 1, 5, 15, 25, then stop when back to head.

3. Final Answer:

   1 -> 5 -> 15 -> 25 -> null -> Option A

4. Quick Check:

   New head 1 followed by old nodes in order [OK]

Hint: Update last.next before changing head to new node [OK]

Common Mistakes:

• Not updating last node's next pointer
• Printing from old head instead of new head
• Confusing node order after insertion