Insert at Beginning of Circular Linked List in DSA Python - Execution Trace

Concept Flow - Insert at Beginning of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

|No↓

Traverse to last node

↓

last_node.next = new_node

↓

new_node.next = head

↓

Update head = new_node

↓

Done

Start by creating a new node. If the list is empty, point new node to itself. Otherwise, find the last node, link it to new node, link new node to old head, then update head.

Execution Sample

DSA Python

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

def insert_at_beginning(head, data):
    new_node = Node(data)
    if head is None:
        new_node.next = new_node
        head = new_node
        return head
    current = head
    while current.next != head:
        current = current.next
    current.next = new_node
    new_node.next = head
    head = new_node
    return head

This code creates a new node and inserts it at the beginning of a circular linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	∅	head = None	List is empty
2	Create new node with data=10	Node(10)	new_node.next = None	new_node: [10 | next: ∅]
3	Check if list is empty	Node(10)	head is None → True	No links yet
4	Point new_node.next to itself (single node circular)	Node(10)	new_node.next = new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → new_node
5	Update head to new_node	Node(10)	head = new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → new_node
6	Insert new node with data=20 at beginning	Node(10) → Node(20)	Create new_node(20)	new_node: [20 | next: ∅]
7	Traverse to last node (node with data=10)	Node(10) → Node(20)	current = head (10) current.next != head? No (points to 10 itself)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next: ∅│ └────────┘ └────────┘ head
8	Set last_node.next to new_node	Node(10) → Node(20)	last_node(10).next = new_node(20)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next: ∅│ └────────┘ └────────┘ head
9	Set new_node.next to old head	Node(10) → Node(20)	new_node(20).next = head(10)	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head new_node
10	Update head to new_node	Node(20) → Node(10)	head = new_node(20)	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head last_node (new head)
11	Insert new node with data=30 at beginning	Node(20) → Node(10) → Node(30)	Create new_node(30)	new_node: [30 | next: ∅]
12	Traverse to last node (node with data=10)	Node(20) → Node(10) → Node(30)	current = head(20) current.next != head? Yes (10) Move to 10 current.next != head? No (20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next: ∅│ └────────┘ └────────┘ └────────┘ head
13	Set last_node.next to new_node	Node(20) → Node(10) → Node(30)	last_node(10).next = new_node(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next: ∅│ └────────┘ └────────┘ └────────┘ head
14	Set new_node.next to old head	Node(20) → Node(10) → Node(30)	new_node(30).next = head(20)	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head last_node
15	Update head to new_node	Node(30) → Node(20) → Node(10)	head = new_node(30)	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head second last_node
16	Stop	Node(30) → Node(20) → Node(10)	Insertion complete	Circular linked list updated with new head

💡 Insertion stops after updating head to new node and linking last node to new head.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 6	After Step 9	After Step 10	After Step 11	After Step 14	After Step 15	Final
head	None	None	None	Node(10)	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(30)	Node(30)
new_node	None	Node(10)	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)	Node(30)
last_node	None	None	None	None	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
current	None	None	None	None	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(20)	Node(20)

Key Moments - 3 Insights

Why do we need to traverse to the last node before inserting at the beginning?

Because in a circular linked list, the last node points back to the head. To insert a new node at the beginning, we must update the last node's next pointer to the new node. This is shown in steps 7-9 in the execution_table.

What happens if the list is empty when inserting the first node?

If the list is empty (head is None), the new node points to itself, making a single-node circular list. This is shown in steps 3-5 in the execution_table.

Why do we update the head pointer after insertion?

Because the new node becomes the first node in the list, so head must point to it. This update is shown in steps 5, 10, and 15.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does new_node.next point to?

A It points to None

B It points to itself (new_node)

C It points to the old head

D It points to the last node

💡 Hint

Check the Pointer Changes and Visual State columns at step 4.

At which step does the head pointer update to the new node for the second insertion?

A Step 15

B Step 14

C Step 10

D Step 9

💡 Hint

Look at the Pointer Changes column for head updates after inserting data=20.

If the list was empty, what would be the visual state after insertion?

A Two nodes linked circularly

B A single node pointing to None

C A single node pointing to itself

D No nodes

💡 Hint

Refer to step 4 and 5 visual states for empty list insertion.

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If empty, point new_node.next to itself
- Else, find last node
- last_node.next = new_node
- new_node.next = old head
- Update head = new_node
- List remains circular

Full Transcript

To insert a node at the beginning of a circular linked list, first create the new node. If the list is empty, make the new node point to itself and update head to it. If not empty, traverse the list to find the last node, update last node's next pointer to the new node, then set new node's next to the old head. Finally, update head to the new node. This keeps the list circular and updates the start correctly.

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