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.

Practice

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

easy

A. The new node is added at the end of the list, breaking the circular link.

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

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

D. The list becomes a linear linked list instead of circular.

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, circle intact [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 connecting 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 C?

easy

A. head = new_node; new_node->next = head; last->next = head;

B. head = new_node; new_node->next = last; last = head;

C. last->next = new_node; new_node->next = head; head = new_node;

D. new_node->next = NULL; head = new_node; last->next = NULL;

Solution

1. Step 1: Link new node to current head

   Set new_node->next to head so new node points to old first node.

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

   Set last->next to new_node to maintain circular link, then update head to new_node.

3. Final Answer:

   last->next = new_node; new_node->next = head; head = new_node; -> Option C

4. Quick Check:

   New node links head and last points to new node [OK]

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

Common Mistakes:

• Setting new_node->next to NULL breaks circular link
• Updating head before linking last node
• Confusing order of pointer assignments

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

struct Node {
  int data;
  struct Node* next;
};

// Existing list: 20 -> 30 -> 40 -> back to 20
struct Node* head = node20;
struct Node* last = node40;

// Insert 10 at beginning
struct Node* new_node = malloc(sizeof(struct Node));
new_node->data = 10;
new_node->next = head;
last->next = new_node;
head = new_node;

// Print list starting from head (print 4 nodes)

medium

A. 10 -> 20 -> 30 -> 40 -> back to 10

B. 20 -> 30 -> 40 -> 10 -> back to 20

C. 10 -> 30 -> 40 -> 20 -> back to 10

D. 30 -> 40 -> 20 -> 10 -> back to 30

Solution

1. Step 1: Insert new node at beginning

   New node with data 10 points to old head (20), last node (40) points to new node, head updated to new node.

2. Step 2: Print nodes starting from new head

   Printing 4 nodes from head: 10, 20, 30, 40, then back to 10.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> back to 10 -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Not updating last->next to new node
• Printing old head as start
• Mixing node order after insertion

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

void insertAtBeginning(struct Node** head, int data) {
  struct Node* new_node = malloc(sizeof(struct Node));
  new_node->data = data;
  new_node->next = *head;
  *head = new_node;
}

medium

A. The head pointer is not updated to new node.

B. The new node's data is not assigned correctly.

C. Memory allocation is missing for new node.

D. The last node's next pointer is not updated to new head, breaking circular link.

Solution

1. Step 1: Check pointer updates

   The code updates head to new node and new node points to old head, but does not update last node's next pointer.

2. Step 2: Understand circular link maintenance

   In circular linked list, last node must point to new head to keep circle intact; missing here causes broken link.

3. Final Answer:

   The last node's next pointer is not updated to new head, breaking circular link. -> Option D

4. Quick Check:

   Last node must point to new head [OK]

Hint: Always update last node's next to new head [OK]

Common Mistakes:

• Ignoring last node pointer update
• Assuming head update is enough
• Not handling empty list case

5. You have a circular linked list with nodes: 5 -> 15 -> 25 -> back to 5. You want to insert 1 at the beginning. Which sequence of pointer updates correctly maintains the circular linked list?

hard

A. Create new node with 1, set last->next = new_node, new_node->next = head, head = new_node.

B. Create new node with 1, set head = new_node, new_node->next = head, update last->next = new_node.

C. Create new node with 1, set new_node->next = NULL, head = new_node, last->next = head.

D. Create new node with 1, set head = new_node, new_node->next = last, last->next = head.

Solution

1. Step 1: Link new node between last and head

   Set last->next to new node, then new_node->next to old head to maintain circle.

2. Step 2: Update head pointer

   Set head to new node so it becomes the first node in the list.

3. Final Answer:

   Create new node with 1, set last->next = new_node, new_node->next = head, head = new_node. -> Option A

4. Quick Check:

   Last points new node, new node points old head, head updated [OK]

Hint: Last points new node, new node points old head, update head last [OK]

Common Mistakes:

• Setting new_node->next to NULL breaks circle
• Updating head before linking last node
• Confusing pointer order causing broken links