Insert at Position (Circular Linked List)

With a tail pointer (tail->next = first node), insert at a 0-based index pos works like the linear list case, but you must respect the ring: pos == 0 is insert at beginning, pos == n (list length n) is insert at end, and 0 < pos < n needs a walk of pos - 1 steps from head—O(pos), worst case O(n).

C program (return tail)

Valid indices for a list of length n are 0 … n (inclusive): n means “after the last node.” Invalid pos leaves tail unchanged. An empty list only accepts pos == 0.

• count_nodes walks the ring once to get n.
• Ends delegate to insert_begin / insert_end; middle inserts splice after the predecessor of index pos.

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

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

static int count_nodes(struct Node *tail)
{
    if (tail == NULL)
        return 0;
    struct Node *h = tail->next;
    struct Node *c = h;
    int n = 0;
    do {
        n++;
        c = c->next;
    } while (c != h);
    return n;
}

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;
}

struct Node *insert_end(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 newNode;
}

/* pos is 0-based; valid 0..n where n = count_nodes(tail). */
struct Node *insert_at(struct Node *tail, int pos, int data)
{
    if (tail == NULL) {
        if (pos != 0)
            return NULL;
        return insert_end(NULL, data);
    }
    int n = count_nodes(tail);
    if (pos < 0 || pos > n)
        return tail;
    if (pos == 0)
        return insert_begin(tail, data);
    if (pos == n)
        return insert_end(tail, data);

    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return tail;
    newNode->data = data;
    struct Node *head = tail->next;
    struct Node *cur = head;
    for (int i = 0; i < pos - 1; i++)
        cur = cur->next;
    newNode->next = cur->next;
    cur->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;
    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_at(tail, 0, 10);
    tail = insert_at(tail, 1, 20);
    tail = insert_at(tail, 2, 30);

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

    free_list(tail);
    return 0;
}

Program output

Overall program flow

Why the first inserts hit insert_end

After the first node, appending is always pos == n (insert after the current last). That is O(1) per call here. A middle insert would walk from head—see Insert at Position (SLL) for the same splice pattern on an open chain.

Index:  0     1     2
        10 → 20 → 30 ─┘
        ▲         ▲ tail
        └─────────┘
        tail→next

Complexity summary

For production code you can often avoid a separate count_nodes pass by branching on pos with smarter logic or by tracking length in a struct—but the idea stays the same.

See also Insert at Beginning (CLL) · Insert at End (CLL) · Insert at Position (SLL)