Close Menu
Data Structures

Insertion in Circular Singly Linked List: A Comprehensive Guide

By

A circular singly linked list is a type of linked list in which the last node points back to the first node, forming a continuous loop. This unique property makes circular linked lists ideal for applications requiring a repetitive or circular structure, such as buffering, scheduling, and more.

Insertion is one of the most fundamental operations in a linked list. This article explains in detail the four main ways to perform insertion in a circular singly linked list, with a focus on implementation, logic, and step-by-step approaches. Additionally, we’ll explore the benefits of using a tail pointer (instead of a head pointer) for optimized insertions.

Insertion in an empty List in the circular Singly linked list

Why Choose a Tail Pointer Over a Head Pointer?

When dealing with circular singly linked lists, the choice between using a head pointer or a tail pointer can significantly affect the efficiency of insertion operations.

  • Insertion at the Beginning: If a head pointer is used, you must traverse the entire list to locate the last node so you can update its pointer. With a tail pointer, this traversal is unnecessary because the last node is already known.
  • Insertion at the End: Similarly, inserting at the end requires traversal to the last node when a head pointer is used. A tail pointer, however, provides direct access to the last node, reducing the insertion to constant time.

By employing a tail pointer, insertion at the beginning or at the end of a circular singly linked list becomes an O(1) operation, regardless of the list’s length. This makes the data structure highly efficient for scenarios with frequent insertions.

Insertion in a Circular Singly Linked List

Insertion in a circular singly linked list involves linking a new node while ensuring that the circular structure is maintained. This can be done in four primary ways:

1. Insertion in an Empty List

Inserting into an empty circular singly linked list is the simplest case, as there are no existing nodes to manage. The steps are straightforward:

  • Create a New Node: Allocate memory for the node and assign it the desired value.
  • Set the Node to Point to Itself: Since it’s the only node in the list, its next pointer should reference itself.
  • Update the Tail Pointer: The last (or tail) pointer is updated to point to the newly created node.
Insertion in an empty List in the circular linked list

Advantages:

This operation is the foundation for creating the list. The circular structure is established by ensuring the new node’s next pointer references itself.

Step-by-Step Implementation:

  • Check if the list is empty: If the last pointer is not nullptr, the list is non-empty, and no insertion occurs. Return the current last.
  • Create a new node: Allocate memory and initialize the node with the given value.
  • Establish the circular link: Set the new node’s next pointer to point to itself.
  • Update the last pointer: Set last to reference the new node.

Code Implementation In Multiple Programming Languages

C Implementation

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

// Define the Node structure
struct Node {
    int data;
    struct Node* next;
};

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

// Function to insert a node into an empty circular linked list
struct Node* insertInEmptyList(struct Node* last, int data) {
    if (last != NULL) return last; // List is not empty, return as is

    struct Node* newNode = createNode(data); // Create a new node
    last = newNode; // Update last to point to the new node
    return last;
}

// Function to print the list
void printList(struct Node* last) {
    if (last == NULL) return; // Empty list, no output

    struct Node* head = last->next; // Start from head node
    do {
        printf("%d ", head->data); // Print node data
        head = head->next;
    } while (head != last->next); // Loop back to start
    printf("\n");
}

int main() {
    struct Node* last = NULL;

    // Insert a node into the empty list
    last = insertInEmptyList(last, 1);

    // Print the list
    printf("List after insertion: ");
    printList(last);

    return 0;
}

C++ Implementation

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(this) {} // Constructor for Node
};

// Function to insert a node into an empty circular linked list
Node* insertInEmptyList(Node* last, int data) {
    if (last != nullptr) return last; // List is not empty

    Node* newNode = new Node(data); // Create a new node
    last = newNode; // Update last pointer
    return last;
}

// Function to print the list
void printList(Node* last) {
    if (last == nullptr) return; // Empty list

    Node* head = last->next; // Start from head
    do {
        cout << head->data << " "; // Print node data
        head = head->next;
    } while (head != last->next); // Loop back to start
    cout << endl;
}

int main() {
    Node* last = nullptr;

    // Insert a node into the empty list
    last = insertInEmptyList(last, 1);

    // Print the list
    cout << "List after insertion: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;
    public Node Next;

    public Node(int value) {
        Data = value;
        Next = this; // Circular link to itself
    }
}

class CircularLinkedList {
    public static Node InsertInEmptyList(Node last, int data) {
        if (last != null) return last; // List is not empty

        Node newNode = new Node(data); // Create a new node
        last = newNode; // Update last pointer
        return last;
    }

    public static void PrintList(Node last) {
        if (last == null) return; // Empty list

        Node head = last.Next; // Start from head
        do {
            Console.Write(head.Data + " "); // Print node data
            head = head.Next;
        } while (head != last.Next); // Loop back to start
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args) {
        Node last = null;

        // Insert a node into the empty list
        last = CircularLinkedList.InsertInEmptyList(last, 1);

        // Print the list
        Console.WriteLine("List after insertion: ");
        CircularLinkedList.PrintList(last);
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = this; // Circular link to itself
    }
}

class CircularLinkedList {
    public static Node insertInEmptyList(Node last, int data) {
        if (last != null) return last; // List is not empty

        Node newNode = new Node(data); // Create a new node
        last = newNode; // Update last pointer
        return last;
    }

    public static void printList(Node last) {
        if (last == null) return; // Empty list

        Node head = last.next; // Start from head
        do {
            System.out.print(head.data + " "); // Print node data
            head = head.next;
        } while (head != last.next); // Loop back to start
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        Node last = null;

        // Insert a node into the empty list
        last = CircularLinkedList.insertInEmptyList(last, 1);

        // Print the list
        System.out.println("List after insertion: ");
        CircularLinkedList.printList(last);
    }
}

JavaScript Implementation

class Node {
    constructor(value) {
        this.data = value;
        this.next = this; // Circular link to itself
    }
}

class CircularLinkedList {
    static insertInEmptyList(last, data) {
        if (last !== null) return last; // List is not empty

        const newNode = new Node(data); // Create a new node
        last = newNode; // Update last pointer
        return last;
    }

    static printList(last) {
        if (last === null) return; // Empty list

        let head = last.next; // Start from head
        do {
            process.stdout.write(`${head.data} `); // Print node data
            head = head.next;
        } while (head !== last.next); // Loop back to start
        console.log();
    }
}

// Main function
let last = null;

// Insert a node into the empty list
last = CircularLinkedList.insertInEmptyList(last, 1);

// Print the list
process.stdout.write("List after insertion: ");
CircularLinkedList.printList(last);

Python Implementation

class Node:
    def __init__(self, value):
        self.data = value
        self.next = self  # Circular link to itself

def insert_in_empty_list(last, data):
    if last is not None:
        return last  # List is not empty

    new_node = Node(data)  # Create a new node
    last = new_node  # Update last pointer
    return last

def print_list(last):
    if last is None:
        return  # Empty list

    head = last.next  # Start from head
    while True:
        print(head.data, end=" ")  # Print node data
        head = head.next
        if head == last.next:
            break  # Loop back to start
    print()

# Main function
last = None

# Insert a node into the empty list
last = insert_in_empty_list(last, 1)

# Print the list
print("List after insertion: ", end="")
print_list(last)

Key Concepts Across All Languages

  • Node Class or Structure: Represents each element in the circular linked list.
  • Insert Function: Handles empty list insertion.
  • Circular Link Maintenance: Ensures the next pointer always creates a circular structure.
  • Print Function: Traverses and prints the list while respecting the circular nature.

Output

List after insertion: 1

Time Complexity: O(1)
Auxiliary Space: O(1)

Explanation of Output

  • The program begins with an empty circular singly linked list.
  • A new node with the value 1 is inserted into the list. Since the list is empty, the node is created and its next pointer links back to itself, maintaining the circular structure.
  • When printing the list, the single node (1) is visited, and its data is displayed. The traversal stops when the program encounters the head node again, ensuring the circular nature is preserved.

2. Insertion at the Beginning

Inserting a new node at the beginning of a circular singly linked list requires updating both the new node and the tail pointer to maintain the circular structure.

  • Check if the List is Empty: If the list is empty, perform the same steps as inserting into an empty list.
  • Link the New Node: Set the next pointer of the new node to the current head of the list (last->next).
  • Update the Tail’s Pointer: Update the next pointer of the last node (last) to point to the new node.
Insertion at the beginning in circular linked list

Advantages:

This operation is efficient with a tail pointer since it avoids traversing the list. The insertion maintains the circular linkage by ensuring that both the tail and the new node-connect properly.

Step-by-Step Implementation:

  • Create a new node: Allocate memory and assign the node a value.
  • Check if the list is empty:
    • If last is nullptr, make the new node point to itself, and update last.
  • Insert at the beginning:
    • Set the new node’s next pointer to last->next (the current head).
    • Update last->next to point to the new node.

Code Implementation In Multiple Programming Languages

C Implementation

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

// Define the Node structure
struct Node {
    int data;
    struct Node *next;
};

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

// Function to insert a node at the beginning of the circular linked list
struct Node* insertAtBeginning(struct Node* last, int value) {
    struct Node* newNode = createNode(value);

    // If the list is empty
    if (last == NULL) {
        newNode->next = newNode;
        return newNode;
    }

    // Insert the new node at the beginning
    newNode->next = last->next;
    last->next = newNode;

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) return;

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

int main() {
    // Create circular linked list: 2, 3, 4
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);
    struct Node* last = first->next->next;
    last->next = first;

    printf("Original list: ");
    printList(last);

    // Insert 5 at the beginning
    last = insertAtBeginning(last, 5);

    printf("List after inserting 5 at the beginning: ");
    printList(last);

    return 0;
}

C++ Implementation

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data;
    Node* next;

    Node(int value) : data(value), next(nullptr) {} // Constructor for Node
};

// Function to insert a node at the beginning of the circular linked list
Node* insertAtBeginning(Node* last, int value) {
    Node* newNode = new Node(value);

    // If the list is empty
    if (last == nullptr) {
        newNode->next = newNode;
        return newNode;
    }

    // Insert the new node at the beginning
    newNode->next = last->next;
    last->next = newNode;

    return last;
}

// Function to print the circular linked list
void printList(Node* last) {
    if (last == nullptr) return;

    Node* head = last->next;
    do {
        cout << head->data << " ";
        head = head->next;
    } while (head != last->next);
    cout << endl;
}

int main() {
    // Create circular linked list: 2, 3, 4
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);
    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    // Insert 5 at the beginning
    last = insertAtBeginning(last, 5);

    cout << "List after inserting 5 at the beginning: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;
    public Node Next;

    public Node(int value) {
        Data = value;
        Next = null;
    }
}

class CircularLinkedList {
    public static Node InsertAtBeginning(Node last, int value) {
        Node newNode = new Node(value);

        // If the list is empty
        if (last == null) {
            newNode.Next = newNode;
            return newNode;
        }

        // Insert the new node at the beginning
        newNode.Next = last.Next;
        last.Next = newNode;

        return last;
    }

    public static void PrintList(Node last) {
        if (last == null) return;

        Node head = last.Next;
        do {
            Console.Write(head.Data + " ");
            head = head.Next;
        } while (head != last.Next);
        Console.WriteLine();
    }
}

class Program {
    static void Main() {
        // Create circular linked list: 2, 3, 4
        Node first = new Node(2);
        first.Next = new Node(3);
        first.Next.Next = new Node(4);
        Node last = first.Next.Next;
        last.Next = first;

        Console.WriteLine("Original list: ");
        CircularLinkedList.PrintList(last);

        // Insert 5 at the beginning
        last = CircularLinkedList.InsertAtBeginning(last, 5);

        Console.WriteLine("List after inserting 5 at the beginning: ");
        CircularLinkedList.PrintList(last);
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = null;
    }
}

class CircularLinkedList {
    public static Node insertAtBeginning(Node last, int value) {
        Node newNode = new Node(value);

        // If the list is empty
        if (last == null) {
            newNode.next = newNode;
            return newNode;
        }

        // Insert the new node at the beginning
        newNode.next = last.next;
        last.next = newNode;

        return last;
    }

    public static void printList(Node last) {
        if (last == null) return;

        Node head = last.next;
        do {
            System.out.print(head.data + " ");
            head = head.next;
        } while (head != last.next);
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        // Create circular linked list: 2, 3, 4
        Node first = new Node(2);
        first.next = new Node(3);
        first.next.next = new Node(4);
        Node last = first.next.next;
        last.next = first;

        System.out.println("Original list: ");
        CircularLinkedList.printList(last);

        // Insert 5 at the beginning
        last = CircularLinkedList.insertAtBeginning(last, 5);

        System.out.println("List after inserting 5 at the beginning: ");
        CircularLinkedList.printList(last);
    }
}

JavaScript Implementation

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
    }
}

class CircularLinkedList {
    static insertAtBeginning(last, value) {
        const newNode = new Node(value);

        // If the list is empty
        if (!last) {
            newNode.next = newNode;
            return newNode;
        }

        // Insert the new node at the beginning
        newNode.next = last.next;
        last.next = newNode;

        return last;
    }

    static printList(last) {
        if (!last) return;

        let head = last.next;
        do {
            process.stdout.write(`${head.data} `);
            head = head.next;
        } while (head !== last.next);
        console.log();
    }
}

// Main function
let first = new Node(2);
first.next = new Node(3);
first.next.next = new Node(4);
let last = first.next.next;
last.next = first;

console.log("Original list:");
CircularLinkedList.printList(last);

// Insert 5 at the beginning
last = CircularLinkedList.insertAtBeginning(last, 5);

console.log("List after inserting 5 at the beginning:");
CircularLinkedList.printList(last);

Python Implementation

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

def insert_at_beginning(last, value):
    new_node = Node(value)

    # If the list is empty
    if last is None:
        new_node.next = new_node
        return new_node

    # Insert the new node at the beginning
    new_node.next = last.next
    last.next = new_node

    return last

def print_list(last):
    if last is None:
        return

    head = last.next
    while True:
        print(head.data, end=" ")
        head = head.next
        if head == last.next:
            break
    print()

# Create circular linked list: 2, 3, 4
first = Node(2)
first.next = Node(3)
first.next.next = Node(4)
last = first.next.next
last.next = first

print("Original list:")
print_list(last)

# Insert 5 at the beginning
last = insert_at_beginning(last, 5)

print("List after inserting 5 at the beginning:")
print_list(last)

Expected Output of all Programs

Original list: 2 3 4
List after inserting 5 at the beginning: 5 2 3 4

Time Complexity

The time complexity for inserting a node at the beginning of a circular singly linked list is O(1).

  • This is because the insertion operation involves a fixed number of steps:
    • Creating a new node.
    • Adjusting pointers (last->next and newNode->next).

Auxiliary Space

The auxiliary space is O(1).

  • The operation does not use any additional data structures or recursion, aside from the constant space required to create a new node.

Summary

  • Time Complexity: O(1)
    • The performance is constant and does not depend on the number of nodes in the list.
  • Auxiliary Space: O(1)
    • Only a small, constant amount of extra memory is used during the operation.

3. Insertion at the End

To insert a new node at the end of the list, you must link the new node to the current head and update the tail pointer.

  • Check if the List is Empty: Handle the case where the list is empty as described in the first method.
  • Link the New Node to the Head: Set the next pointer of the new node to the current head (last->next).
  • Update the Tail Pointer: Update the next pointer of the current tail to reference the new node. Finally, update the last pointer to the new node.
Insertion at the end in circular linked list

Advantages:

This operation, like insertion at the beginning, is O(1) with a tail pointer. The tail pointer ensures that there is no need to traverse the list.

Step-by-Step Implementation:

  • Create a new node: Allocate memory and initialize it with the desired value.
  • Check if the list is empty:
    • If last is nullptr, initialize the list as described earlier.
  • Insert at the end:
    • Set the new node’s next pointer to the head (last->next).
    • Update the current tail’s next pointer to the new node.
    • Update last to reference the new node.

Code Implementation In Multiple Programming Languages

C Implementation

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

// Define the Node structure
struct Node {
    int data;
    struct Node* next;
};

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

// Function to insert a node at the end of a circular linked list
struct Node* insertEnd(struct Node* tail, int value) {
    struct Node* newNode = createNode(value);
    if (tail == NULL) {
        // If the list is empty, initialize it with the new node
        tail = newNode;
        newNode->next = newNode;
    } else {
        // Insert new node after the current tail and update the tail pointer
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
    return tail;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) return;

    struct Node* head = last->next;
    while (1) {
        printf("%d ", head->data);
        head = head->next;
        if (head == last->next) break;
    }
    printf("\n");
}

int main() {
    // Create circular linked list: 2, 3, 4
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    struct Node* last = first->next->next;
    last->next = first;

    printf("Original list: ");
    printList(last);

    // Insert elements at the end of the circular linked list
    last = insertEnd(last, 5);
    last = insertEnd(last, 6);

    printf("List after inserting 5 and 6: ");
    printList(last);

    return 0;
}

C++ Implementation

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// Function to insert a node at the end of a circular linked list
Node* insertEnd(Node* tail, int value) {
    Node* newNode = new Node(value);
    if (tail == nullptr) {
        tail = newNode;
        newNode->next = newNode;
    } else {
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
    return tail;
}

// Function to print the circular linked list
void printList(Node* last) {
    if (!last) return;

    Node* head = last->next;
    do {
        cout << head->data << " ";
        head = head->next;
    } while (head != last->next);
    cout << endl;
}

int main() {
    // Create circular linked list: 2, 3, 4
    Node* first = new Node(2);
    first->next = new Node(3);
    first->next->next = new Node(4);
    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    // Insert elements at the end of the circular linked list
    last = insertEnd(last, 5);
    last = insertEnd(last, 6);

    cout << "List after inserting 5 and 6: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int data;
    public Node next;

    public Node(int value) {
        data = value;
        next = null;
    }
}

class CircularLinkedList {
    public Node InsertEnd(Node tail, int value) {
        Node newNode = new Node(value);
        if (tail == null) {
            tail = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
        return tail;
    }

    public void PrintList(Node tail) {
        if (tail == null) return;

        Node head = tail.next;
        do {
            Console.Write(head.data + " ");
            head = head.next;
        } while (head != tail.next);
        Console.WriteLine();
    }
}

class Program {
    static void Main(string[] args) {
        CircularLinkedList list = new CircularLinkedList();

        // Create circular linked list: 2, 3, 4
        Node first = new Node(2);
        first.next = new Node(3);
        first.next.next = new Node(4);
        Node tail = first.next.next;
        tail.next = first;

        Console.WriteLine("Original list: ");
        list.PrintList(tail);

        // Insert elements at the end of the circular linked list
        tail = list.InsertEnd(tail, 5);
        tail = list.InsertEnd(tail, 6);

        Console.WriteLine("List after inserting 5 and 6: ");
        list.PrintList(tail);
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = null;
    }
}

class CircularLinkedList {
    Node insertEnd(Node tail, int value) {
        Node newNode = new Node(value);
        if (tail == null) {
            tail = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
        return tail;
    }

    void printList(Node tail) {
        if (tail == null) return;

        Node head = tail.next;
        do {
            System.out.print(head.data + " ");
            head = head.next;
        } while (head != tail.next);
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        // Create circular linked list: 2, 3, 4
        Node first = new Node(2);
        first.next = new Node(3);
        first.next.next = new Node(4);
        Node tail = first.next.next;
        tail.next = first;

        System.out.println("Original list: ");
        list.printList(tail);

        // Insert elements at the end of the circular linked list
        tail = list.insertEnd(tail, 5);
        tail = list.insertEnd(tail, 6);

        System.out.println("List after inserting 5 and 6: ");
        list.printList(tail);
    }
}

JavaScript Implementation

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
    }
}

class CircularLinkedList {
    insertEnd(tail, value) {
        const newNode = new Node(value);
        if (!tail) {
            tail = newNode;
            newNode.next = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
        return tail;
    }

    printList(tail) {
        if (!tail) return;

        let head = tail.next;
        do {
            process.stdout.write(head.data + " ");
            head = head.next;
        } while (head !== tail.next);
        console.log();
    }
}

const list = new CircularLinkedList();

// Create circular linked list: 2, 3, 4
let first = new Node(2);
first.next = new Node(3);
first.next.next = new Node(4);
let tail = first.next.next;
tail.next = first;

console.log("Original list: ");
list.printList(tail);

// Insert elements at the end of the circular linked list
tail = list.insertEnd(tail, 5);
tail = list.insertEnd(tail, 6);

console.log("List after inserting 5 and 6: ");
list.printList(tail);

Python Implementation

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

class CircularLinkedList:
    def insert_end(self, tail, value):
        new_node = Node(value)
        if tail is None:
            tail = new_node
            new_node.next = new_node
        else:
            new_node.next = tail.next
            tail.next = new_node
            tail = new_node
        return tail

    def print_list(self, tail):
        if tail is None:
            return
        head = tail.next
        while True:
            print(head.data, end=" ")
            head = head.next
            if head == tail.next:
                break
        print()

# Create circular linked list: 2, 3, 4
first = Node(2)
first.next = Node(3)
first.next.next = Node(4)
tail = first.next.next
tail.next = first

print("Original list: ")
cll = CircularLinkedList()
cll.print_list(tail)

# Insert elements at the end of the circular linked list
tail = cll.insert_end(tail, 5)
tail = cll.insert_end(tail, 6)

print("List after inserting 5 and 6: ")
cll.print_list(tail)

Expected Output

Original list: 2 3 4
List after inserting 5 and 6: 2 3 4 5 6

Explanation of the Output

  • The original list starts with the nodes 2 → 3 → 4, forming a circular singly linked list.
    • The last node (4) points back to the first node (2), completing the circular structure.
  • Insertion at the end:
    • First, the value 5 is inserted at the end. The new node becomes the new tail, pointing to the head (2).
    • Next, the value 6 is inserted similarly, becoming the new tail and maintaining the circular structure.
  • The final list is 2 → 3 → 4 → 5 → 6, with the last node (6) pointing back to the first node (2).

Time Complexity and Auxiliary Space

  • Time Complexity: O(1)
    • Insertion involves a constant number of steps regardless of the list size.
  • Auxiliary Space: O(1)
    • No additional space is used except for the node being created.

4. Insertion at a Specific Position

Inserting a node at a specific position requires determining whether the position is valid and then updating the relevant pointers to maintain the circular structure.

  • Validate the Position: If the list is empty and the position is not 1, the position is invalid.
  • Handle Special Cases: For position 1, insert the node at the beginning. For positions beyond the current length, the position is invalid.
  • Traverse the List: Iterate to the desired position and insert the new node by updating the relevant pointers.
  • Update the Tail Pointer (if Necessary): If the new node is inserted at the end, update the last pointer.
Insertion at specific position in circular linked list

Advantages:

This operation is flexible, allowing insertion at any position. While insertion at specific positions generally requires traversal, it supports applications where precise positioning is necessary.

Step-by-Step Implementation:

  • Validate the position:
    • If the list is empty (last == nullptr) and the position is not 1, print an error message.
  • Handle special cases:
    • If the position is 1, call the insertion-at-beginning method.
  • Traverse to the insertion point:
    • Loop through the list to find the node preceding the desired position.
    • If the position is out of bounds, print an error message.
  • Insert the node:
    • Update the next pointers of the surrounding nodes to include the new node.
  • Update the tail pointer:
    • If the new node is added at the end, update the last pointer.

Code Implementation In Multiple Programming Languages

C Implementation

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

// Define the Node structure
struct Node {
    int data;
    struct Node* next;
};

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

// Function to insert a node at a specific position in a circular linked list
struct Node* insertAtPosition(struct Node* last, int data, int pos) {
    if (last == NULL) {
        // If the list is empty
        if (pos != 1) {
            printf("Invalid position!\n");
            return last;
        }
        // Create a new node and make it point to itself
        struct Node* newNode = createNode(data);
        last = newNode;
        last->next = last;
        return last;
    }

    // Create a new node with the given data
    struct Node* newNode = createNode(data);
    struct Node* curr = last->next;

    if (pos == 1) {
        // Insert at the beginning
        newNode->next = curr;
        last->next = newNode;
        return last;
    }

    // Traverse the list to find the insertion point
    for (int i = 1; i < pos - 1; ++i) {
        curr = curr->next;
        if (curr == last->next) {
            printf("Invalid position!\n");
            return last;
        }
    }

    // Insert the new node at the desired position
    newNode->next = curr->next;
    curr->next = newNode;

    // Update last if the new node is inserted at the end
    if (curr == last) {
        last = newNode;
    }

    return last;
}

// Function to print the circular linked list
void printList(struct Node* last) {
    if (last == NULL) {
        printf("List is empty.\n");
        return;
    }

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

int main() {
    // Create circular linked list: 2 -> 3 -> 4 -> (back to 2)
    struct Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    struct Node* last = first->next->next;
    last->next = first; // Completing the circular link

    printf("Original list: ");
    printList(last);

    // Insert elements at specific positions
    int data = 5, pos = 2;
    last = insertAtPosition(last, data, pos);

    printf("List after insertions: ");
    printList(last);

    return 0;
}

Explanation

  • Node Creation (createNode): Dynamically allocates memory for a node, sets its data, and initializes the next pointer to NULL.
  • Insertion Logic (insertAtPosition):
    • Handles special cases like inserting into an empty list or inserting at the beginning.
    • Traverses the circular list to find the correct position.
    • Updates pointers to maintain the circular structure.
  • Traversal (printList):
    • Starts from last->next (head of the list).
    • Traverses the list using a do-while loop to ensure all nodes are printed.

C++ Implementation

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data;
    Node *next;
};

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

// Function to insert a node at a specific position in a circular linked list
Node* insertAtPosition(Node* last, int data, int pos) {
    if (last == nullptr) {
        if (pos != 1) {
            cout << "Invalid position!" << endl;
            return last;
        }
        Node* newNode = createNode(data);
        last = newNode;
        last->next = last;
        return last;
    }

    Node* newNode = createNode(data);
    Node* curr = last->next;

    if (pos == 1) {
        newNode->next = curr;
        last->next = newNode;
        return last;
    }

    for (int i = 1; i < pos - 1; ++i) {
        curr = curr->next;
        if (curr == last->next) {
            cout << "Invalid position!" << endl;
            return last;
        }
    }

    newNode->next = curr->next;
    curr->next = newNode;

    if (curr == last) last = newNode;
    return last;
}

// Function to print the circular linked list
void printList(Node* last) {
    if (last == nullptr) return;

    Node* head = last->next;
    do {
        cout << head->data << " ";
        head = head->next;
    } while (head != last->next);
    cout << endl;
}

int main() {
    Node* first = createNode(2);
    first->next = createNode(3);
    first->next->next = createNode(4);

    Node* last = first->next->next;
    last->next = first;

    cout << "Original list: ";
    printList(last);

    int data = 5, pos = 2;
    last = insertAtPosition(last, data, pos);

    cout << "List after insertions: ";
    printList(last);

    return 0;
}

C# Implementation

using System;

class Node {
    public int Data;
    public Node Next;

    public Node(int value) {
        Data = value;
        Next = null;
    }
}

class CircularLinkedList {
    public static Node InsertAtPosition(Node last, int data, int pos) {
        if (last == null) {
            if (pos != 1) {
                Console.WriteLine("Invalid position!");
                return last;
            }
            Node newNode = new Node(data);
            last = newNode;
            last.Next = last;
            return last;
        }

        Node newNode = new Node(data);
        Node curr = last.Next;

        if (pos == 1) {
            newNode.Next = curr;
            last.Next = newNode;
            return last;
        }

        for (int i = 1; i < pos - 1; ++i) {
            curr = curr.Next;
            if (curr == last.Next) {
                Console.WriteLine("Invalid position!");
                return last;
            }
        }

        newNode.Next = curr.Next;
        curr.Next = newNode;

        if (curr == last) last = newNode;
        return last;
    }

    public static void PrintList(Node last) {
        if (last == null) return;

        Node head = last.Next;
        do {
            Console.Write(head.Data + " ");
            head = head.Next;
        } while (head != last.Next);
        Console.WriteLine();
    }

    public static void Main() {
        Node first = new Node(2);
        first.Next = new Node(3);
        first.Next.Next = new Node(4);

        Node last = first.Next.Next;
        last.Next = first;

        Console.WriteLine("Original list: ");
        PrintList(last);

        int data = 5, pos = 2;
        last = InsertAtPosition(last, data, pos);

        Console.WriteLine("List after insertions: ");
        PrintList(last);
    }
}

Java Implementation

class Node {
    int data;
    Node next;

    Node(int value) {
        data = value;
        next = null;
    }
}

public class CircularLinkedList {
    static Node insertAtPosition(Node last, int data, int pos) {
        if (last == null) {
            if (pos != 1) {
                System.out.println("Invalid position!");
                return last;
            }
            Node newNode = new Node(data);
            last = newNode;
            last.next = last;
            return last;
        }

        Node newNode = new Node(data);
        Node curr = last.next;

        if (pos == 1) {
            newNode.next = curr;
            last.next = newNode;
            return last;
        }

        for (int i = 1; i < pos - 1; ++i) {
            curr = curr.next;
            if (curr == last.next) {
                System.out.println("Invalid position!");
                return last;
            }
        }

        newNode.next = curr.next;
        curr.next = newNode;

        if (curr == last) last = newNode;
        return last;
    }

    static void printList(Node last) {
        if (last == null) return;

        Node head = last.next;
        do {
            System.out.print(head.data + " ");
            head = head.next;
        } while (head != last.next);
        System.out.println();
    }

    public static void main(String[] args) {
        Node first = new Node(2);
        first.next = new Node(3);
        first.next.next = new Node(4);

        Node last = first.next.next;
        last.next = first;

        System.out.println("Original list: ");
        printList(last);

        int data = 5, pos = 2;
        last = insertAtPosition(last, data, pos);

        System.out.println("List after insertions: ");
        printList(last);
    }
}

JavaScript Implementation

class Node {
    constructor(value) {
        this.data = value;
        this.next = null;
    }
}

function insertAtPosition(last, data, pos) {
    if (!last) {
        if (pos !== 1) {
            console.log("Invalid position!");
            return last;
        }
        const newNode = new Node(data);
        last = newNode;
        last.next = last;
        return last;
    }

    const newNode = new Node(data);
    let curr = last.next;

    if (pos === 1) {
        newNode.next = curr;
        last.next = newNode;
        return last;
    }

    for (let i = 1; i < pos - 1; ++i) {
        curr = curr.next;
        if (curr === last.next) {
            console.log("Invalid position!");
            return last;
        }
    }

    newNode.next = curr.next;
    curr.next = newNode;

    if (curr === last) last = newNode;
    return last;
}

function printList(last) {
    if (!last) return;

    let head = last.next;
    do {
        process.stdout.write(head.data + " ");
        head = head.next;
    } while (head !== last.next);
    console.log();
}

const first = new Node(2);
first.next = new Node(3);
first.next.next = new Node(4);

let last = first.next.next;
last.next = first;

console.log("Original list: ");
printList(last);

const data = 5, pos = 2;
last = insertAtPosition(last, data, pos);

console.log("List after insertions: ");
printList(last);

Python Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert_at_position(last, data, pos):
    if not last:
        if pos != 1:
            print("Invalid position!")
            return last
        new_node = Node(data)
        last = new_node
        last.next = last
        return last

    new_node = Node(data)
    curr = last.next

    if pos == 1:
        new_node.next = curr
        last.next = new_node
        return last

    for _ in range(1, pos - 1):
        curr = curr.next
        if curr == last.next:
            print("Invalid position!")
            return last

    new_node.next = curr.next
    curr.next = new_node

    if curr == last:
        last = new_node
    return last

def print_list(last):
    if not last:
        return
    head = last.next
    while True:
        print(head.data, end=" ")
        head = head.next
        if head == last.next:
            break
    print()

first = Node(2)
first.next = Node(3)
first.next.next = Node(4)

last = first.next.next
last.next = first

print("Original list: ")
print_list(last)

data, pos = 5, 2
last = insert_at_position(last, data, pos)

print("List after insertions: ")
print_list(last)

Expected Output

Original list: 2 3 4 
List after insertions: 2 5 3 4

Output Explanation

Let’s break down the output for the provided implementations:

Input Details

  • Original Circular Linked List: 2 -> 3 -> 4 -> (back to 2)
  • Insert Data: 5
  • Position: 2

Step-by-Step Output

  1. Original List:
    • The circular linked list is printed starting from the node next to last:
Original list: 2 3 4

This is because the list is traversed starting from last->next.

  1. Insertion at Position 2:
    • A new node with data 5 is created.
    • The new node is inserted after the first node (2), and its next pointer is updated to point to the second node (3).
    • The next pointer of the first node (2) is updated to point to the new node (5).
    • The updated circular linked list is: 2 -> 5 -> 3 -> 4 -> (back to 2)
  1. Updated List After Insertion:
    • The circular linked list is printed again, starting from the node next to last:
List after insertions: 2 5 3 4

Time Complexity

The time complexity of inserting a node at a specific position in a circular linked list depends on the position at which the node is inserted.

  • Best Case:
    • If the position is 1 (inserting at the beginning), the time complexity is O(1) because it requires only a constant amount of operations to update pointers.
  • Worst Case:
    • If the position is at the end or out of bounds, the function traverses the entire list, leading to a time complexity of O(n), where n is the number of nodes in the list.
  • Average Case:
    • On average, the time complexity is O(n/2) (which simplifies to O(n)) since it may traverse half the list.

Auxiliary Space Complexity

The auxiliary space complexity is O(1) because the function only uses a constant amount of extra space for pointers like curr and newNode.

Summary

  • Time Complexity:
    • Best case: O(1)
    • Worst case: O(n)
    • Average case: O(n)
  • Auxiliary Space Complexity: O(1)

Conclusion

Insertion in a circular singly linked list is a versatile operation with applications in various computer science fields. Using a tail pointer simplifies and optimizes insertions, particularly at the beginning and end of the list. Whether inserting into an empty list, at the beginning, at the end, or at a specific position, the key is to carefully update pointers to maintain the circular structure.

By mastering these techniques, developers can efficiently manage circular linked lists in scenarios such as real-time systems, resource scheduling, and dynamic memory allocation.

  1. Introduction to Circular Linked Lists: A Comprehensive Guide
  2. Understanding Circular Singly Linked Lists: A Comprehensive Guide
  3. Circular Doubly Linked List: A Comprehensive Guide
  4. Insertion in Circular Singly Linked List: A Comprehensive Guide
  5. Insertion in an Empty Circular Linked List: A Detailed Exploration
  6. Insertion at the Beginning in Circular Linked List: A Detailed Exploration
  7. Insertion at the End of a Circular Linked List: A Comprehensive Guide
  8. Insertion at a Specific Position in a Circular Linked List: A Detailed Exploration
  9. Deletion from a Circular Linked List: A Comprehensive Guide
  10. Deletion from the Beginning of a Circular Linked List: A Detailed Exploration
  11. Deletion at Specific Position in Circular Linked List: A Detailed Exploration
  12. Deletion at the End of a Circular Linked List: A Comprehensive Guide
  13. Searching in a Circular Linked List: A Comprehensive Exploration

Frequently Asked Questions (FAQs) on Insertion in Circular Singly Linked List

What is a Circular Singly Linked List, and how does it differ from other linked lists?

A circular singly linked list is a type of linked list where the last node is connected back to the first node, forming a loop. Unlike a singly linked list, where the last node points to nullptr, and a doubly linked list, where nodes have pointers to both previous and next nodes, the circular singly linked list maintains a circular connection through its last node.

Advantages:

  • Continuous traversal without needing to reset to the head.
  • Efficient for applications like round-robin scheduling and buffering systems.

Differences:

  • Singly Linked List: Linear; the last node points to nullptr.
  • Doubly Linked List: Each node points to both its previous and next nodes.
  • Circular Singly Linked List: The last node points back to the first, forming a loop.

What are the main insertion operations in a Circular Singly Linked List?

Insertion in a circular singly linked list can be performed in four primary ways:

  • Insertion in an Empty List: Creates a new node that points to itself and becomes the only node in the list.
  • Insertion at the Beginning: Adds a new node before the current head, updating the last->next pointer to maintain the circular structure.
  • Insertion at the End: Appends a new node after the current tail, updates its next pointer to the head, and reassigns the tail pointer.
  • Insertion at a Specific Position: Adds a new node at a designated position, requiring traversal to locate the correct insertion point.

Each operation ensures the list maintains its circular structure by appropriately updating pointers.

Why is a Tail Pointer more efficient than a Head Pointer in Circular Linked Lists?

Using a tail pointer instead of a head pointer enhances the efficiency of insertion operations for two key reasons:

  • Constant Time Insertions:
    • With a tail pointer, both beginning and end insertions are O(1) because the tail pointer directly accesses the last node.
    • With a head pointer, insertion at the beginning requires traversing the list to update the last node’s next pointer, making it O(n).
  • Simplified Implementation:
    • A tail pointer ensures that operations requiring the last node (e.g., end insertion) don’t involve unnecessary traversal.

Real-world analogy: A tail pointer is like keeping the key to the back door of a circular track, while a head pointer requires circling back to the beginning for access.

How is a node inserted into an empty Circular Singly Linked List?

Insertion into an empty circular singly linked list involves creating a single node that references itself, establishing the circular structure.

Steps:

  • Check for Empty List: Verify that the last pointer is nullptr.
  • Create a New Node: Allocate memory and assign the node its value.
  • Establish Circular Link: Set the next pointer of the new node to itself.
  • Update the Tail Pointer: Point the last pointer to the newly created node.

Example:

Suppose we insert 10 into an empty list. The new node is created, its next points to itself, and the tail (last) references it. This forms a self-contained loop.

How do you insert a node at the beginning of a Circular Singly Linked List?

Inserting at the beginning involves adding a new node before the current head and updating the last node’s next pointer.

Steps:

  • Create a New Node: Allocate memory and assign the value.
  • Check if the List is Empty:
    • If empty, follow the steps for empty list insertion.
  • Update Pointers:
    • Set the next pointer of the new node to the current head (last->next).
    • Update the last->next pointer to reference the new node.

Example:

For a list containing 10 -> 20 -> 30, inserting 5 at the beginning updates the list to 5 -> 10 -> 20 -> 30.

How do you insert a node at the end of a Circular Singly Linked List?

To insert a node at the end of the list, a new node is added after the current tail, and the tail pointer is updated to the new node.

Steps:

  • Check if the List is Empty: If so, follow the steps for empty list insertion.
  • Create a New Node: Allocate memory and assign the value.
  • Update Pointers:
    • Set the next pointer of the new node to the head (last->next).
    • Update the next pointer of the current tail to the new node.
    • Update the last pointer to the new node.

Example:

For a list 10 -> 20 -> 30, inserting 40 at the end results in 10 -> 20 -> 30 -> 40, with 40 as the new tail.

How is a node inserted at a specific position in a Circular Singly Linked List?

Insertion at a specific position involves traversing the list to locate the correct insertion point and updating the surrounding pointers.

Steps:

  • Validate the Position: Ensure the position exists (e.g., position 1 for an empty list).
  • Create a New Node: Allocate memory and assign the value.
  • Insert at Beginning (if position = 1): Call the beginning insertion method.
  • Traverse to the Desired Position: Locate the node preceding the insertion point.
  • Update Pointers: Adjust the next pointers of surrounding nodes to include the new node.
  • Update Tail (if Inserted at End): If the node is inserted at the end, update the tail pointer.

Example:

For 10 -> 20 -> 30, inserting 15 at position 2 results in 10 -> 15 -> 20 -> 30.

What are some applications of Circular Singly Linked Lists?

Circular singly linked lists are widely used in computer science due to their unique structure. Common applications include:

  • Round-robin Scheduling:
    • Used in operating systems to allocate CPU time in a cyclic manner.
  • Data Buffers:
    • Ideal for managing fixed-size buffers (e.g., circular queues).
  • Music Playlists:
    • Continuously looping through songs in a playlist.
  • Gaming:
    • Tracking players’ turns in multiplayer games.
  • Traffic Management:
    • Managing circular traffic flows, such as roundabouts.

What happens if an invalid position is provided for insertion?

If an invalid position is provided, the insertion operation fails gracefully:

  • Empty List:
    • If the list is empty and the position isn’t 1, the operation is invalid because there are no nodes to traverse or adjust.
  • Out-of-Bounds Position:
    • For non-empty lists, positions beyond the current length + 1 are invalid.

In both cases, an error message is displayed (e.g., “Invalid position!”), and no changes are made to the list.

How can you ensure that the Circular Singly Linked List remains circular after insertions?

To maintain the circular structure:

  • Always Update the Tail’s Next Pointer:
    • For all operations, ensure that the last->next pointer correctly references the head.
  • Adjust Pointers During Traversal:
    • When inserting at a specific position, carefully update the next pointers of surrounding nodes.
  • Handle Edge Cases:
    • For empty lists or tail insertions, verify the circular linkage.

By following these principles, the list’s circular nature is preserved, ensuring that the last node always points to the first.

Share.
Examsmeta Logo

Examsmeta serves as a comprehensive hub for educational resources across diverse disciplines. Designed to deliver high-quality, topic-wise notes and articles, it caters to students, educators, researchers, and lifelong learners. The goal is to make learning accessible, engaging, and effective for all. With a focus on providing detailed, accurate, and up-to-date content, Examsmeta fosters a passion for learning and supports both academic and professional growth. Whether it's exam preparation, research, or knowledge expansion, this platform offers guidance every step of the way.