Insert at Beginning (Circular Linked List)

In a singly circular linked list (CLL), inserting at the front is still O(1) if you keep a tail pointer with the usual invariant: tail->next is the first node (logical head). Create a node, link it before the old first node, then set tail->next to the new node. The empty list and the one-node ring (next points to itself) are special cases handled in the same function.

C program (return updated tail)

The function returns the tail pointer so main can write tail = insert_begin(tail, value);. For a non-empty list, tail still points at the last node after a front insert; only tail->next moves to the new front.

• Empty (tail == NULL): one new node; newNode->next = newNode; return it as tail.
• Non-empty: newNode->next = tail->next; then tail->next = newNode;; return tail unchanged.

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

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

struct Node *insert_begin(struct Node *tail, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return tail;

    newNode->data = data;
    if (tail == NULL) {
        newNode->next = newNode;
        return newNode;
    }
    newNode->next = tail->next;
    tail->next = newNode;
    return tail;
}

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

void free_list(struct Node *tail)
{
    if (tail == NULL)
        return;
    struct Node *head = tail->next;
    tail->next = NULL;   /* break ring, then free like a linear list */
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void)
{
    struct Node *tail = NULL;

    tail = insert_begin(tail, 30);
    tail = insert_begin(tail, 20);
    tail = insert_begin(tail, 10);

    print_list(tail);   /* 10 20 30 */

    free_list(tail);
    return 0;
}

Program output

Traversal path for print_list()

The loop starts at head (tail->next), prints each data, advances cur = cur->next, and stops when cur returns to head (full lap around the ring).

Start at head (tail→next) = [10]
    ↓
Print 10 → move to next → [20]
    ↓
Print 20 → move to next → [30]
    ↓
Print 30 → move to next → [10]
    ↓
Stop (back to head)

Output: 10 20 30

Overall program flow

Each insert_begin call in detail

Call 1: insert_begin(NULL, 30)

After call 1 (one-node ring):

tail → [30 | ──┐
         └────┘  (next points to self)

Call 2: insert_begin(0x1000, 20) — tail is node 30

After call 2: ring 20 → 30 → 20; tail still at 30.

tail (0x1000) ──→ [30 | 0x2000] ──→ [20 | 0x1000] ──→ …
                  last              first (tail->next)

Call 3: insert_begin(0x1000, 10)

After call 3: ring 10 → 20 → 30 → 10.

tail->next (0x3000) = first
 10 → 20 → 30 ─┘
         ▲      │
         └──────┘  tail (0x1000) points to last (30)

Memory layout (example addresses)

Final ring in heap

Visual representation

        tail (last = n3 @ 0x1000)
              │
              ▼
         ┌──────────────┐
    ┌───→│ data: 30     │
    │    │ next: 0x3000 ┼───┐
    │    └──────────────┘   │
    │          n3           │
    │                       ▼
    │    ┌──────────────┐  ┌──────────────┐
    │    │ data: 10     │  │ data: 20     │
    └────┼ next: 0x2000 ┼─→│ next: 0x1000 ┼──┘
         └──────────────┘  └──────────────┘
              n1                 n2
         (tail->next)         (inserted 2nd)

Detailed step-by-step: call 3 (insert 10)

Inside insert_begin when tail is 0x1000 (node 30) and data is 10:

Complexity summary

With a tail pointer and tail->next as the first node, insert at the beginning of a CLL is O(1): two pointer writes and no walk around the ring. If you only stored head, you would need an O(n) pass to find the last node and fix its next when inserting at the front.

Alternative: pass struct Node **tail and update *tail inside the function when the list is empty (first insert). Same logic. See also Insert at Beginning (SLL) and CLL vs SLL, tail pointer.