Insert at End of Circular Linked List in DSA C

Mental Model

A circular linked list connects the last node back to the first, forming a loop. Inserting at the end means adding a new node just before the first node and updating the last node to point to this new node.

Analogy: Imagine people sitting in a circle holding hands. Adding a new person at the end means placing them just before the first person and making sure the last person now holds the new person's hand.

head -> 1 -> 2 -> 3 -> back to 1 (circular)
Insert new node 4 at end:
head -> 1 -> 2 -> 3 -> 4 -> back to 1

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 4 at end

Goal: Add node with value 4 at the end so the list becomes 1 -> 2 -> 3 -> 4 (circular)

Step 1: Create new node with value 4

1 -> 2 -> 3 -> back to 1, new node 4 (isolated)

Why: We need a new node to insert at the end

Step 2: Traverse from head to find last node (node with value 3)

1 -> 2 -> [3] -> back to 1, new node 4 (isolated)

Why: We must find the last node to link it to the new node

Step 3: Set last node's next pointer to new node 4

1 -> 2 -> 3 -> [4] (next=NULL), circle temporarily broken

Why: Link new node after last node to insert at end

Step 4: Set new node's next pointer to head (node 1)

1 -> 2 -> 3 -> 4 -> back to 1 (circular)

Why: Maintain circular link by pointing new node back to head

Result:

1 -> 2 -> 3 -> 4 -> back to 1 (circular)

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for circular linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insert at end of circular linked list
void insertAtEnd(Node** head, int value) {
    Node* newNode = createNode(value); // create new node
    if (*head == NULL) {
        newNode->next = newNode; // points to itself
        *head = newNode; // head points to new node
        return;
    }
    Node* temp = *head;
    // traverse to last node
    while (temp->next != *head) {
        temp = temp->next; // advance temp
    }
    temp->next = newNode; // last node points to new node
    newNode->next = *head; // new node points to head
}

// Print circular linked list
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("back to %d\n", head->data);
}

int main() {
    Node* head = NULL;
    // Create initial list 1 -> 2 -> 3 (circular)
    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printf("Original list:\n");
    printList(head);

    // Insert 4 at end
    insertAtEnd(&head, 4);

    printf("After inserting 4 at end:\n");
    printList(head);

    return 0;
}

Node* newNode = createNode(value); // create new node

create new node to insert

if (*head == NULL) { newNode->next = newNode; *head = newNode; return; }

handle empty list by pointing new node to itself and updating head

while (temp->next != *head) { temp = temp->next; }

traverse to last node which points back to head

temp->next = newNode;

link last node to new node

newNode->next = *head;

link new node back to head to maintain circularity

Output

Original list:

1 -> 2 -> 3 -> back to 1

After inserting 4 at end:

1 -> 2 -> 3 -> 4 -> back to 1

Complexity Analysis

Time: O(n) because we traverse all nodes once to find the last node

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: In a singly circular linked list without a tail pointer, inserting at the beginning also requires O(n) traversal to update the last node's next pointer.

Edge Cases

empty list

new node points to itself and becomes head

DSA C

if (*head == NULL) { newNode->next = newNode; *head = newNode; return; }

single node list

new node inserted after the single node and points back to head

DSA C

while (temp->next != *head) { temp = temp->next; }

When to Use This Pattern

When you see a circular linked list and need to add a node at the end, use traversal to find the last node and update pointers to maintain the circle.

Common Mistakes

Mistake: Not updating the new node's next pointer to head, breaking the circular link
Fix: Always set newNode->next = head after inserting at end

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is NULL and handle by pointing new node to itself and updating head

Summary

Adds a new node at the end of a circular linked list, maintaining the circular link.

Use when you want to append data to the end of a circular linked list.

Remember to link the new node back to the head to keep the list circular.

Practice

1. What happens when you insert a new node at the end of a circular linked list that currently has 3 nodes?

easy

A. The new node becomes the head node and points to the second node.

B. The new node becomes the last node and points back to the head node.

C. The new node is inserted in the middle of the list.

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

Solution

1. Step 1: Understand circular linked list structure

   In a circular linked list, the last node points back to the head node, forming a circle.

2. Step 2: Insert new node at end

   The new node is linked after the current last node, and its next pointer points to the head node, maintaining the circle.

3. Final Answer:

   The new node becomes the last node and points back to the head node. -> Option B

4. Quick Check:

   New node points to head, preserving circular link [OK]

Hint: New end node always points to head in circular list [OK]

Common Mistakes:

• Forgetting to link new node back to head
• Inserting node at wrong position
• Breaking the circular link

2. Which of the following is the correct syntax to create a new node in C for a circular linked list?

easy

A. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

B. newNode = malloc(sizeof(Node));

C. struct Node newNode = malloc(sizeof(struct Node));

D. Node* newNode = new Node();

Solution

1. Step 1: Allocate memory for new node

   In C, use malloc with sizeof(struct Node) and cast to (struct Node*).

2. Step 2: Correct pointer declaration

   Declare newNode as a pointer to struct Node to hold the allocated memory address.

3. Final Answer:

   struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); -> Option A

4. Quick Check:

   Proper malloc and pointer cast in C [OK]

Hint: Use malloc with sizeof(struct Node) and cast to struct Node* [OK]

Common Mistakes:

• Missing (struct Node*) cast
• Declaring newNode as struct Node instead of pointer
• Using C++ style new operator in C

3. Given the following code snippet for inserting at the end of a circular linked list, what will be the printed list after insertion?

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

void printList(struct Node* head) {
  struct Node* temp = head;
  if (head != NULL) {
    do {
      printf("%d -> ", temp->data);
      temp = temp->next;
    } while (temp != head);
  }
  printf("NULL\n");
}

int main() {
  struct Node* head = (struct Node*)malloc(sizeof(struct Node));
  struct Node* second = (struct Node*)malloc(sizeof(struct Node));
  struct Node* third = (struct Node*)malloc(sizeof(struct Node));

  head->data = 1; head->next = second;
  second->data = 2; second->next = third;
  third->data = 3; third->next = head;

  // Insert new node with data 4 at end
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = 4;
  newNode->next = head;
  third->next = newNode;

  printList(head);
  return 0;
}

medium

A. 1 -> 2 -> 3 -> 4 -> 1 -> ... (infinite loop)

B. 1 -> 2 -> 3 -> NULL

C. 3 -> 4 -> 1 -> 2 -> NULL

D. 1 -> 2 -> 3 -> 4 -> NULL

Solution

1. Step 1: Understand list before insertion

   Initial list is 1 -> 2 -> 3 -> back to 1 (circular).

2. Step 2: Insert new node at end

   New node with data 4 points to head; third node points to new node, extending list to 1 -> 2 -> 3 -> 4 -> back to 1.

3. Step 3: Print list

   printList prints nodes until it reaches head again, so output is 1 -> 2 -> 3 -> 4 -> NULL.

4. Final Answer:

   1 -> 2 -> 3 -> 4 -> NULL -> Option D

5. Quick Check:

   New node added at end, circular link maintained [OK]

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

Common Mistakes:

• Printing infinite loop by not stopping at head
• Forgetting to update last node's next pointer
• Incorrect print format

4. Identify the error in the following code snippet that attempts to insert a new node at the end of a circular linked list:

void insertEnd(struct Node** head, int data) {
  struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = *head;

  struct Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

medium

A. The function should not use double pointer for head.

B. newNode->next should be NULL instead of *head.

C. The while loop condition should check for temp->next != *head instead of NULL.

D. Memory allocation for newNode is missing.

Solution

1. Step 1: Analyze loop condition in circular list

   In a circular linked list, last node's next points to head, not NULL.

2. Step 2: Correct loop condition

   Loop should continue until temp->next equals head, not NULL, to find last node.

3. Final Answer:

   The while loop condition should check for temp->next != *head instead of NULL. -> Option C

4. Quick Check:

   Loop must detect circular end by comparing to head [OK]

Hint: In circular list, last node points to head, not NULL [OK]

Common Mistakes:

• Using NULL to detect end in circular list
• Setting newNode->next to NULL
• Not updating last node's next pointer

5. You have a circular linked list with only one node where head points to itself. You want to insert a new node at the end. Which sequence of steps correctly updates the list?

hard

A. Create new node, set newNode->next = head->next, set head->next = newNode.

B. Create new node, set newNode->next = head, set head->next = newNode, then update head to newNode.

C. Create new node, set newNode->next = NULL, set head->next = newNode.

D. Create new node, set newNode->next = newNode, set head = newNode.

Solution

1. Step 1: Understand single node circular list

   The single node has head->next pointing to itself (head).

2. Step 2: Insert at end

   Set newNode->next = head->next (which is head), then head->next = newNode. This makes head -> newNode -> head, maintaining circularity without changing head.

3. Final Answer:

   Create new node, set newNode->next = head->next, set head->next = newNode. -> Option A

4. Quick Check:

   head -> newNode -> head [OK]

Hint: For single node circular: newNode->next = head->next; head->next = newNode [OK]

Common Mistakes:

• Setting newNode->next to NULL breaking circularity
• Unnecessarily updating head to newNode
• Incorrectly linking new node to itself