Insert at Beginning 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 beginning means adding a new node before the current first node and updating the last node to point to this new node.

Analogy: Imagine people sitting in a circle holding hands. To add a new person at the start, you place them before the first person and make sure the last person now holds the new person's hand, keeping the circle unbroken.

Before insertion:
head -> 1 -> 2 -> 3 -> back to head (1)

After insertion of 0 at beginning:
head -> 0 -> 1 -> 2 -> 3 -> back to head (0)

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 0 at beginning

Goal: Add a new node with value 0 at the start and keep the list circular

Step 1: Create new node with value 0

new_node(0) -> null, list: 1 -> 2 -> 3 -> back to 1

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

Step 2: Find last node (node with value 3) that points back to head (1)

1 -> 2 -> 3 -> [points to head(1)]

Why: To maintain circularity, last node must point to new head

Step 3: Set new_node.next to current head (1)

new_node(0) -> 1 -> 2 -> 3 -> back to 1

Why: New node should point to old first node

Step 4: Set last node's next to new_node (0)

1 -> 2 -> 3 -> new_node(0) -> 1 (circular)

Why: Last node must point to new first node to keep circle

Step 5: Update head pointer to new_node (0)

head -> 0 -> 1 -> 2 -> 3 -> back to 0

Why: Head must point to the new first node

Result:

head -> 0 -> 1 -> 2 -> 3 -> back to 0

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 insert at beginning of circular linked list
void insertAtBeginning(Node** head_ref, int new_data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = new_data;

    if (*head_ref == NULL) {
        // List is empty: new node points to itself
        new_node->next = new_node;
        *head_ref = new_node;
        return;
    }

    // Find last node which points back to head
    Node* last = *head_ref;
    while (last->next != *head_ref) {
        last = last->next; // advance last to next node
    }

    // Insert new_node before head and update last's next
    new_node->next = *head_ref; // new node points to old head
    last->next = new_node;      // last node points to new node
    *head_ref = new_node;       // head updated to new node
}

// Function to 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
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);

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

    // Insert 0 at beginning
    insertAtBeginning(&head, 0);

    printf("After inserting 0 at beginning:\n");
    printList(head);

    return 0;
}

while (last->next != *head_ref) { last = last->next; // advance last to next node }

advance last pointer to find the last node that points to head

new_node->next = *head_ref; // new node points to old head

link new node to current head to insert at beginning

last->next = new_node; // last node points to new node

update last node to point to new node to maintain circularity

*head_ref = new_node; // head updated to new node

update head pointer to new node as new first element

Output

Original list:

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

After inserting 0 at beginning:

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

Complexity Analysis

Time: O(n) because we must traverse the list to find the last node before insertion

Space: O(1) because insertion uses only a fixed amount of extra memory for the new node

vs Alternative: Compared to a singly linked list insertion at beginning which is O(1), circular list insertion requires O(n) to update the last node's pointer

Edge Cases

empty list

new node points to itself and becomes head, forming a single-node circular list

DSA C

if (*head_ref == NULL) {
        new_node->next = new_node;
        *head_ref = new_node;
        return;
    }

single node list

last node is the head itself; after insertion, last node points to new node and new node points to old head

DSA C

while (last->next != *head_ref) {
        last = last->next;
    }

When to Use This Pattern

When you see a problem asking to insert at the start of a circular linked list, remember you must update the last node's pointer to maintain the circle.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new head, breaking the circular link
Fix: Always find the last node and set its next pointer to the new node after insertion

Summary

Inserts a new node at the start of a circular linked list and updates pointers to keep the circle intact.

Use when you need to add elements quickly at the beginning of a circular linked list.

The key is to update the last node's next pointer to the new head to maintain circularity.