Create a Circular Singly Linked List in DSA C - Execution Trace

Concept Flow - Create a Circular Singly Linked List

Create new node with data

↓

Is list empty?

Yes→Set head = new node

↓

new node.next = head

↓

Traverse to last node

↓

Set last node.next = new node

↓

Set new node.next = head

↓

Done

This flow shows how to add a new node to a circular singly linked list by either initializing the list or inserting at the end and linking back to head.

Execution Sample

DSA C

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

void insertEnd(struct Node** head, int data) {
  // Insert node at end of circular list
}

This code inserts a new node with given data at the end of a circular singly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	empty	new_node created	null
2	Check if list empty	empty	head == NULL	null
3	Set head = new_node	10	head -> new_node	10 -> ...
4	Set new_node.next = head	10	new_node.next -> head	10 -> points to 10 (self)
5	Done	10	head and new_node.next set	10 -> 10 (circular)
6	Create new node with data=20	10	new_node created	10 -> 10 (circular)
7	Check if list empty	10	head != NULL	10 -> 10 (circular)
8	Traverse to last node	10	current points to 10	10 -> 10 (circular)
9	Set last node.next = new_node	10,20	10.next -> new_node	10 -> 20 -> ...
10	Set new_node.next = head	10,20	new_node.next -> head	10 -> 20 -> 10 (circular)
11	Done	10,20	pointers updated	10 -> 20 -> 10 (circular)

💡 Insertion complete; list is circular with last node pointing to head

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 9	After Step 10	Final
head	NULL	points to node(10)	points to node(10)	points to node(10)	points to node(10)	points to node(10)
new_node	NULL	node(10)	node(10)	node(20)	node(20)	node(20)
current	NULL	NULL	NULL	node(10)	node(10)	node(10)
new_node.next	NULL	NULL	node(10)	NULL	node(10)	node(10)
last_node.next	NULL	NULL	NULL	node(20)	node(20)	node(20)

Key Moments - 3 Insights

Why do we set new_node.next = head after inserting at the end?

Because the list is circular, the last node must point back to the head to maintain the circle. This is shown in execution_table step 10.

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

We set head to the new node and point new_node.next to head itself, making a single-node circular list. See steps 3 and 4 in execution_table.

How do we find the last node in the circular list?

We traverse nodes until current.next equals head, meaning current is the last node. This traversal is shown in step 8.

Visual Quiz - 3 Questions

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

A head node

B NULL

C new_node itself

D last node

💡 Hint

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

At which step does the list change from empty to having one node?

A Step 1

B Step 5

C Step 3

D Step 7

💡 Hint

Look at when head is assigned a node in variable_tracker and execution_table.

If we insert a third node, what will the last node's next pointer point to?

A NULL

B The head node

C The new third node

D The second node

💡 Hint

Refer to the concept_flow and execution_table steps for pointer updates after insertion.

Concept Snapshot

Create Circular Singly Linked List:
- If empty: head = new_node; new_node.next = head
- Else: traverse to last node
- last_node.next = new_node
- new_node.next = head
- List is circular: last node points to head
- Maintains continuous loop through nodes

Full Transcript

To create a circular singly linked list, start by creating a new node with the given data. If the list is empty, set the head pointer to this new node and point the new node's next to itself, making a single-node circle. If the list is not empty, traverse from head until you find the last node, which is identified when its next pointer points back to head. Then set the last node's next pointer to the new node, and set the new node's next pointer back to head. This keeps the list circular. The execution table shows each step, including pointer changes and the visual state of the list. The variable tracker follows how pointers like head, new_node, and current change during the process. Key moments clarify why new_node.next must point to head and how the last node is found. The visual quiz tests understanding of pointer assignments and list state changes. This method ensures the circular singly linked list maintains a continuous loop through all nodes.

Practice

1. What is a key characteristic of a circular singly linked list compared to a regular singly linked list?

easy

A. The last node points back to the first node, forming a circle.

B. Each node has two pointers, one to the next and one to the previous node.

C. It uses an array internally to store nodes.

D. The list ends with a null pointer indicating the end.

Solution

1. Step 1: Understand the pointer structure in circular singly linked list

   In a circular singly linked list, the last node's next pointer points back to the first node, creating a loop.

2. Step 2: Compare with regular singly linked list

   Regular singly linked lists end with a null pointer, while circular ones loop back to the start.

3. Final Answer:

   The last node points back to the first node, forming a circle. -> Option A

4. Quick Check:

   Circular list last node points to head = C [OK]

Hint: Remember: circular means last node links back to first [OK]

Common Mistakes:

• Thinking circular list ends with null pointer
• Confusing circular singly linked list with doubly linked list
• Assuming nodes have two pointers in singly linked list

2. Which of the following is the correct way to initialize a circular singly linked list with one node in C?

easy

A. node->next = head->next;

B. node->next = NULL;

C. node->next = node;

D. node->next = 0;

Solution

1. Step 1: Understand initialization of single node circular list

   For a circular singly linked list with one node, the node's next pointer must point to itself to form a circle.

2. Step 2: Check each option

   node->next = node; sets node->next = node, correctly creating a self-loop. Others either set null or incorrect pointers.

3. Final Answer:

   node->next = node; -> Option C

4. Quick Check:

   Single node points to itself = A [OK]

Hint: Single node circular list points to itself [OK]

Common Mistakes:

• Setting next pointer to NULL instead of self
• Using uninitialized pointers
• Confusing NULL with 0 in pointer context

3. Consider the following C code snippet that creates a circular singly linked list with three nodes. What will be the output of the print loop?

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

int main() {
  Node n1 = {1, NULL};
  Node n2 = {2, NULL};
  Node n3 = {3, NULL};

  n1.next = &n2;
  n2.next = &n3;
  n3.next = &n1;  // circular link

  Node* temp = &n1;
  int count = 0;
  while (count < 5) {
    printf("%d ", temp->data);
    temp = temp->next;
    count++;
  }
  return 0;
}

medium

A. 1 2 3 3 3

B. 1 2 3 2 3

C. 1 2 3 1 1

D. 1 2 3 1 2

Solution

1. Step 1: Trace the linked list nodes and their next pointers

   n1 points to n2, n2 points to n3, n3 points back to n1, forming a circle: 1 -> 2 -> 3 -> 1 ...

2. Step 2: Follow the print loop for 5 iterations

   Print order: 1 (n1), 2 (n2), 3 (n3), 1 (n1 again), 2 (n2 again).

3. Final Answer:

   1 2 3 1 2 -> Option D

4. Quick Check:

   Loop prints nodes in circle: 1 2 3 1 2 [OK]

Hint: Follow next pointers in circle for given count [OK]

Common Mistakes:

• Stopping after 3 nodes instead of 5
• Not following circular link back to first node
• Confusing node data values

4. The following code attempts to create a circular singly linked list with two nodes. What is the error?

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

int main() {
  Node* n1 = malloc(sizeof(Node));
  Node* n2 = malloc(sizeof(Node));
  n1->data = 10;
  n2->data = 20;
  n1->next = n2;
  n2->next = NULL;  // mistake here
  return 0;
}

medium

A. Memory allocation is missing for nodes.

B. n2->next should point to n1 to make the list circular.

C. Data values are not initialized correctly.

D. n1->next should be NULL instead of n2.

Solution

1. Step 1: Identify the circular link requirement

   In a circular singly linked list, the last node's next pointer must point back to the first node.

2. Step 2: Check the code's next pointers

   n1->next points to n2, but n2->next is NULL, breaking the circle. It should point to n1.

3. Final Answer:

   n2->next should point to n1 to make the list circular. -> Option B

4. Quick Check:

   Last node next points to head = D [OK]

Hint: Last node's next must link to first node [OK]

Common Mistakes:

• Setting last node next to NULL instead of head
• Forgetting to allocate memory for nodes
• Mixing up which node points where

5. You want to insert a new node with data 5 at the end of an existing circular singly linked list. The list currently has nodes 1 -> 2 -> 3 -> (back to 1). Which steps correctly insert the new node to maintain the circular structure?

hard

A. Create new node; set new_node->next = head; find last node; set last_node->next = new_node;

B. Create new node; set new_node->next = NULL; find last node; set last_node->next = new_node;

C. Create new node; set new_node->next = last_node; set head = new_node;

D. Create new node; set new_node->next = head->next; set head->next = new_node;

Solution

1. Step 1: Create new node and link it to head

   The new node's next pointer must point to the head to keep the circle intact.

2. Step 2: Find the last node and update its next pointer

   Traverse the list to find the last node (which points to head), then set last_node->next to new_node.

3. Final Answer:

   Create new node; set new_node->next = head; find last node; set last_node->next = new_node; -> Option A

4. Quick Check:

   New node next = head, last node next = new node = A [OK]

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

Common Mistakes:

• Setting new node next to NULL breaks circularity
• Not updating last node's next pointer
• Confusing head and last node pointers