Insert at End (Circular Linked List)

In a singly circular linked list (CLL) with a tail pointer, inserting at the end is O(1). Keep the ring intact by making the new node point to the current first node (tail->next), connect old tail to the new node, then move tail to the new node.

C program (return updated tail)

The function returns the tail pointer so main can write tail = insert_end(tail, value);. For non-empty lists, both pointer links and the tail update happen in constant time.

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

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

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

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

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 linearly */
    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_end(tail, 10);
    tail = insert_end(tail, 20);
    tail = insert_end(tail, 30);

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

    free_list(tail);
    return 0;
}

Program output

Traversal path for print_list()

Even after end insertion, traversal still starts at head = tail->next and completes one full loop.

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_end call in detail

Call 1: insert_end(NULL, 10)

After call 1 (one-node ring):

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

Call 2: insert_end(0x1000, 20)

After call 2: ring 10 → 20 → 10; tail moves to 20.

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

Call 3: insert_end(0x2000, 30)

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

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

Memory layout (example addresses)

Final ring in heap

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

Inside insert_end when tail is 0x2000 (node 20) and data is 30:

Complexity summary

With a tail pointer, end insertion in CLL is naturally O(1) and keeps tail->next as the first node. This is one of the main reasons CLL implementations prefer storing tail instead of only head.

See also Insert at Beginning (CLL) and CLL vs SLL, tail pointer.