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

Concept Flow - Insert at Beginning of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

↓

head = new_node

↓

Find last node (tail)

↓

new_node.next = head

↓

tail.next = new_node

↓

head = new_node

↓

Done

Insert at beginning means creating a new node, linking it to the current head, updating the last node's next to new node, and moving head pointer to new node.

Execution Sample

DSA C

void insertAtBeginning(Node** head, int data) {
  Node* new_node = malloc(sizeof(Node));
  new_node->data = data;
  if (*head == NULL) {
    new_node->next = new_node;
    *head = new_node;
  } else {
    Node* tail = *head;
    while (tail->next != *head) tail = tail->next;
    new_node->next = *head;
    tail->next = new_node;
    *head = new_node;
  }
}

This code inserts a new node at the beginning of a circular linked list, updating pointers accordingly.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	empty	new_node created	∅
2	Check if list is empty	empty	head == NULL	∅
3	List empty: new_node.next = new_node	10	new_node.next → new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head
4	head = new_node	10	head → new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head
5	Insert 20 at beginning: create new node	10	new_node created	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
6	Find tail (node with next == head)	10	tail → node with data 10	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ head
7	new_node.next = head (20.next → 10)	10, 20	20.next → 10	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head new_node
8	tail.next = new_node (10.next → 20)	10, 20	10.next → 20	┌────────┐ ┌────────┐ │ data:10│──→ │ data:20│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head new_node
9	head = new_node (head → 20)	20, 10	head → 20	┌────────┐ ┌────────┐ │ data:20│──→ │ data:10│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head tail
10	Insert 30 at beginning: create new node	20, 10	new_node created	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
11	Find tail (node with next == head)	20, 10	tail → node with data 10	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ head tail
12	new_node.next = head (30.next → 20)	20, 10, 30	30.next → 20	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head tail new_node
13	tail.next = new_node (10.next → 30)	20, 10, 30	10.next → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│──→ │ data:10│──→ │ data:30│──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head tail new_node
14	head = new_node (head → 30)	30, 20, 10	head → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│──→ │ data:20│──→ │ data:10│──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head middle tail
15	End of insertions	30, 20, 10	Pointers stable	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│──→ │ data:20│──→ │ data:10│──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head middle tail

💡 Insertion complete; head updated to new node; last node points to head maintaining circular link.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 10	After Step 12	After Step 14	Final
head	NULL	Node(10)	Node(10)	Node(10)	Node(20)	Node(20)	Node(20)	Node(30)	Node(30)
new_node	NULL	Node(10)	Node(20)	Node(20)	Node(20)	Node(30)	Node(30)	Node(30)	Node(30)
tail	NULL	NULL	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)

Key Moments - 3 Insights

Why do we need to find the tail node before inserting at the beginning?

Because in a circular linked list, the last node's next must point to the new head to maintain the circle. This is shown in execution_table steps 6, 11, and 13 where tail is found and its next pointer updated.

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

The new node points to itself, making a single-node circular list. This is shown in steps 3 and 4 where new_node.next points to itself and head is updated.

Why do we update head pointer last after adjusting tail's next?

Because we must first link the last node to the new node to keep the circle intact before moving head. If head changes first, the tail's next would still point to old head, breaking the circle. This is shown in steps 8 and 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what does the head pointer point to?

A Node with data 20

B Node with data 10

C NULL

D Node with data 30

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 9 in execution_table.

At which step does the list first become circular with a single node?

A Step 2

B Step 5

C Step 3

D Step 7

💡 Hint

Look for when new_node.next points to itself in execution_table.

If we skip updating tail.next to new_node, what would happen to the list?

A List remains circular and correct

B List becomes linear and breaks circularity

C Head pointer becomes NULL

D New node is lost and not linked

💡 Hint

Refer to steps 8 and 13 where tail.next is updated to maintain circular link.

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If list empty: new_node.next = new_node, head = new_node
- Else: find tail (last node)
- new_node.next = head
- tail.next = new_node
- head = new_node
Maintains circular link with updated head and tail pointers.

Full Transcript

To insert at the beginning of a circular linked list, first create a new node with the given data. If the list is empty, point the new node's next to itself and update head to this new node. If the list is not empty, find the last node (tail) by traversing until tail.next points back to head. Then set new_node.next to current head, update tail.next to new_node, and finally update head to new_node. This keeps the circular structure intact with the new node at the beginning. The execution table shows step-by-step pointer changes and the evolving visual state of the list. Key moments clarify why tail must be found and updated before moving head, and how the list behaves when empty. The visual quiz tests understanding of pointer positions and circularity maintenance.