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.