Insert at Beginning of Circular Linked List in DSA Go - 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 to new_node

↓

Done

Create a new node, if list is empty point it to itself. Otherwise, find last node, link it to new node, link new node to head, then update head.

Execution Sample

DSA Go

func insertAtBeginning(head *Node, data int) *Node {
    newNode := &Node{data: data}
    if head == nil {
        newNode.next = newNode
        return newNode
    }
    current := head
    for current.next != head {
        current = current.next
    }
    current.next = newNode
    newNode.next = head
    return newNode
}

This code inserts a new node at the start of a circular linked list, updating pointers to keep the circle intact.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=5	None	newNode created, next=null	No nodes yet
2	Check if list is empty (head == nil)	None	head is nil, so newNode.next = newNode	┌────────┐ │ data:5 │ │ next:─┐│ └───────┘│ └─→ (points to itself)
3	Return newNode as head	1 node	head = newNode	┌────────┐ │ data:5 │ │ next:─┐│ └───────┘│ └─→ (points to itself) head
4	Insert 10 at beginning when list has 1 node	1 node	Create newNode with data=10	┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ next:─┐│ │ next: ∅│ └───────┘│ └────────┘ └─→ (points to itself) head
5	Traverse to last node (current.next != head)	1 node	current = head (data=5), current.next = head, stop	Current at node with data=5
6	Set last_node.next = newNode	2 nodes	node 5.next → node 10	┌────────┐ ┌────────┐ │ data:5 │───→│ data:10│ │ next:─┼ │ next: ∅│ └───────┘ └────────┘ head
7	Set newNode.next = head	2 nodes	node 10.next → node 5	┌────────┐ ┌────────┐ │ data:5 │───→│ data:10│ │ next:─┼←───│ next:─┐│ └───────┘ └───────┘ head
8	Update head to newNode	2 nodes	head → node 10	┌────────┐ ┌────────┐ │ data:10│───→│ data:5 │ │ next:─┼←───│ next:─┐│ └───────┘ └───────┘ head
9	Done	2 nodes	Pointers updated, circular list intact	Final circular list: 10 → 5 → back to 10

💡 Insertion complete, head updated to new node, list remains circular

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 6	After Step 7	After Step 8	Final
head	nil	nil	node 5	node 5	node 5	node 10	node 10
newNode	nil	node 5	node 10	node 10	node 10	node 10	node 10
current	nil	nil	nil	node 5	node 5	node 5	node 5

Key Moments - 3 Insights

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

Because in a circular linked list, the last node points back to head. To insert at beginning, we must update last node's next to new node. This is shown in execution_table step 5 and 6.

What happens if the list is empty when inserting?

If empty, new node points to itself to form a circular list. No traversal needed. See execution_table steps 2 and 3.

Why update head to newNode after insertion?

Because we insert at beginning, the new node becomes the first node. Updating head points to newNode as shown in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which pointer changes?

A head points to node 5

B node 5.next points to node 10

C node 10.next points to node 5

D head points to node 10

💡 Hint

Check the 'Pointer Changes' column at step 6 in execution_table

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

A Step 8

B Step 3

C Step 6

D Step 9

💡 Hint

Look at the 'Pointer Changes' column for head updates in execution_table

If the list was empty, what would newNode.next point to after insertion?

A nil

B head

C newNode itself

D last node

💡 Hint

See execution_table step 2 where newNode.next points to itself when list is empty

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If list empty: newNode.next = newNode (points to itself)
- Else: traverse to last node
- last_node.next = newNode
- newNode.next = head
- Update head = newNode
- List remains circular with new head

Full Transcript

To insert a node at the beginning of a circular linked list, first create the new node. If the list is empty, point the new node's next to itself and return it as the head. If not empty, traverse the list to find the last node, which points back to the head. Update the last node's next pointer to the new node. Then set the new node's next pointer to the current head. Finally, update the head pointer to the new node. This keeps the list circular and places the new node at the start.

Practice

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

easy

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

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

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

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

Solution

1. Step 1: Understand the circular linked list structure

   A circular linked list has its last node pointing back to the head, 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 A

4. Quick Check:

   New head points to old head, circle intact = A [OK]

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

Common Mistakes:

• Not updating last node's next pointer
• Breaking the circular link
• Adding node at end instead of beginning

2. Which of the following Go code snippets correctly inserts a new node at the beginning of a circular linked list?

easy

A. newNode.next = nil
head = newNode

B. head.next = newNode
newNode.next = head

C. newNode.next = head
last.next = newNode
head = newNode

D. last.next = head
head = newNode
newNode.next = last

Solution

1. Step 1: Link new node to current head

   Assign newNode.next = head to point new node to the current head.

2. Step 2: Update last node to point to new node and update head

   Set last.next = newNode to maintain circular link, then update head = newNode.

3. Final Answer:

   newNode.next = head last.next = newNode head = newNode -> Option C

4. Quick Check:

   Correct pointer updates = B [OK]

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

Common Mistakes:

• Setting newNode.next to nil breaks circular link
• Not updating last.next to new node
• Incorrect order of pointer assignments

3. What will be the printed output of the circular linked list after inserting node with value 10 at the beginning, given the list initially contains 20 -> 30 -> 40 -> (back to 20)?

func printList(head *Node) {
    if head == nil {
        fmt.Println("List is empty")
        return
    }
    temp := head
    for {
        fmt.Printf("%d -> ", temp.data)
        temp = temp.next
        if temp == head {
            break
        }
    }
    fmt.Println("null")
}

// Insert 10 at beginning
newNode := &Node{data: 10}
// Assume last points to node with 40
newNode.next = head
last.next = newNode
head = newNode

printList(head)

medium

A. List is empty

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

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

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

Solution

1. Step 1: Insert new node 10 at beginning

   New node 10 points to old head 20, last node 40 points to new node 10, head updated to 10.

2. Step 2: Print list starting from new head

   Traverse from 10: 10 -> 20 -> 30 -> 40, then stop at head again.

3. Final Answer:

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

4. Quick Check:

   New head 10 followed by old nodes = A [OK]

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

Common Mistakes:

• Printing extra node causing repeated values
• Not updating last.next causing infinite loop
• Confusing order of nodes after insertion

4. Given the following Go code to insert at beginning of a circular linked list, what is the error?

func insertAtBeginning(head *Node, data int) *Node {
    newNode := &Node{data: data}
    if head == nil {
        newNode.next = newNode
        return newNode
    }
    temp := head
    for temp.next != nil {
        temp = temp.next
    }
    newNode.next = head
    temp.next = newNode
    head = newNode
    return head
}

medium

A. The function should not return head.

B. The loop condition should check for temp.next != head, not nil.

C. head should not be updated inside the function.

D. newNode.next should be nil when list is empty.

Solution

1. Step 1: Analyze loop condition for circular list

   In circular linked list, last node's next points to head, so loop should check temp.next != head, not nil.

2. Step 2: Identify impact of wrong condition

   Checking temp.next != nil causes infinite loop or crash because next is never nil in circular list.

3. Final Answer:

   The loop condition should check for temp.next != head, not nil. -> Option B

4. Quick Check:

   Loop must stop at head, not nil [OK]

Hint: In circular list, last.next points to head, not nil [OK]

Common Mistakes:

• Using nil instead of head in loop condition
• Not updating head after insertion
• Returning wrong pointer from function

5. You have a circular linked list with nodes 5 -> 15 -> 25 -> (back to 5). You want to insert a new node with value 1 at the beginning. After insertion, you want to print the list starting from the new head. Which sequence of pointer updates correctly achieves this without breaking the circular structure?

hard

A. Set newNode.next = head; find last node and set last.next = newNode; update head = newNode

B. Set newNode.next = nil; update head = newNode; last.next = head

C. Update head = newNode; set newNode.next = head; last.next = newNode

D. Set last.next = newNode; newNode.next = head; head = newNode.next

Solution

1. Step 1: Link new node to current head

   Assign newNode.next = head so new node points to old head.

2. Step 2: Update last node to point to new node and update head

   Find last node (with value 25) and set last.next = newNode to maintain circular link, then update head = newNode.

3. Final Answer:

   Set newNode.next = head; find last node and set last.next = newNode; update head = newNode -> Option A

4. Quick Check:

   New head points to old head; last points to new head [OK]

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

Common Mistakes:

• Setting newNode.next to nil breaks circle
• Updating head before linking nodes
• Not updating last.next to new node