00:00

Insertion in Circular Linked List

Last updated:

Inserting into a circular linked list is like inserting into a singly linked list, except that the ring must stay closed: the last node's next must always refer to the first node. The programs on this page keep a reference to the last node (often called last or tail). The first node is then simply last.next, so both ends of the ring are reachable in O(1).

This tutorial covers three insert positions:

  1. At the beginning of the list.

  2. At the end of the list.

  3. At the specific position of the list.

1. Insert a node at the beginning of the list.

With a reference to the last node, no walk is needed:

  1. Create newNode.
  2. If the list is empty (last == null), make newNode point to itself; it is the only node and is returned as the new last.
  3. Otherwise point newNode.next at the current first node (last.next) and set last.next = newNode. The new node is now first, and last does not change.

This is O(1).

InsertAtBeginningInCLL.java
//Java Program to insert a new node at the beginning of List
public class InsertAtBeginningInCLL {
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
    }
  }

  // Function to insert a new node at the beginning
  static Node insertAtBeginning(Node last, int value) {
    // Create a node
    Node newNode = new Node(value);

    // If the list is empty
    // Make the new node point to itself and set it as last
    if (last == null) {
      newNode.next = newNode;
      return newNode;
    }

    // If the list is not empty
    // Insert the new node at the beginning of the list
    newNode.next = last.next;
    last.next = newNode;

    return last;
  }

  // Function to print the list
  static void printList(Node last) {
    // Returns if list is empty
    if (last == null)
      return;

    Node head = last.next;
    while (true) {
      System.out.print(head.data + " ");
      head = head.next;
      if (head == last.next)
        break;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a circular linked list
    Node first = new Node(20);
    first.next = new Node(30);
    first.next.next = new Node(40);
    first.next.next.next = new Node(50);
    Node last = first.next.next.next;
    last.next = first;

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

    // Inserting 10 at the beginning
    last = insertAtBeginning(last, 10);

    System.out.println("List after inserting 10 at the beginning: ");
    printList(last);
  }
}
Output
Original list:
20 30 40 50
List after inserting 10 at the beginning:
10 20 30 40 50

2. Insert a node at the end of the circular linked list.

Inserting at the end is the same link change as inserting at the beginning, followed by one more step:

  1. Create newNode. If the list is empty, make it point to itself and return it.
  2. Otherwise set newNode.next = last.next (the first node) and last.next = newNode.
  3. Move last to newNode, because the new node is now the last node of the ring.

This is also O(1).

InsertAtEndInCLL.java
//Java Program to Insert a Node at the End of List
public class InsertAtEndInCLL {
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
    }
  }

  // Function to insert a node at the end
  static Node insertAtEnd(Node tail, int value) {
    // Create a new node
    Node newNode = new Node(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 list
  static void printList(Node last) {
    // Returns if list is empty
    if (last == null)
      return;

    Node head = last.next;
    while (true) {
      System.out.print(head.data + " ");
      head = head.next;
      if (head == last.next)
        break;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a circular linked list
    Node first = new Node(20);
    first.next = new Node(30);
    first.next.next = new Node(40);
    first.next.next.next = new Node(50);
    Node last = first.next.next.next;
    last.next = first;

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

    // Inserting 80 at the end of the list
    last = insertAtEnd(last, 80);

    System.out.println("List after inserting 80 at the end of the list: ");
    printList(last);
  }
}
Output
Original list:
20 30 40 50
List after inserting 80 at the end of the list:
20 30 40 50 80

3. Insert a node at a specific position of the list

Positions are counted from 1 (the first node):

  1. Reject positions smaller than 1. If the list is empty, only position 1 is valid, and the new node points to itself.
  2. Position 1 is an insertion at the beginning.
  3. Otherwise start currNode at the first node and move it forward position − 2 times, so it stops on the node that will come before the new node. If it comes back round to the first node, the position is out of range.
  4. Link the new node in: newNode.next = currNode.next, then currNode.next = newNode.
  5. If currNode was the last node, the new node becomes the new last.

Reaching the position takes O(n) in the worst case.

InsertAtSpecificPositionInCLL.java
// Java Program to Insert a Node At a Specific Position in List
public class InsertAtSpecificPositionInCLL {
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
    }
  }

  // Inserts data so that it becomes the node at the given position (1-based)
  static Node insertAtPosition(Node last, int data, int position) {
    // Positions start at 1
    if (position < 1) {
      System.out.println("Invalid position!");
      return last;
    }

    if (last == null) {
      // If the list is empty
      if (position != 1) {
        System.out.println("Invalid position!");
        return last;
      }
      // Create a new node and make it point to itself
      Node newNode = new Node(data);
      last = newNode;
      last.next = last;
      return last;
    }

    // Create a new node with the given data
    Node newNode = new Node(data);

    // Start at the first node (the node after last)
    Node currNode = last.next;

    if (position == 1) {
      // Insert at the beginning
      newNode.next = currNode;
      last.next = newNode;
      return last;
    }

    // Traverse the list to find the insertion point
    for (int i = 1; i < position - 1; ++i) {
      currNode = currNode.next;

      // If position is out of bounds
      if (currNode == last.next) {
        System.out.println("Invalid position!");
        return last;
      }
    }

    // Insert the new node at the given position
    newNode.next = currNode.next;
    currNode.next = newNode;

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

    return last;
  }

  // Function to print the list
  static void printList(Node last) {
    // Returns if list is empty
    if (last == null)
      return;

    Node head = last.next;
    while (true) {
      System.out.print(head.data + " ");
      head = head.next;
      if (head == last.next)
        break;
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // Create a circular linked list
    Node first = new Node(20);
    first.next = new Node(30);
    first.next.next = new Node(40);
    first.next.next.next = new Node(50);
    Node last = first.next.next.next;
    last.next = first;

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

    // Insert elements at specific positions
    int element = 99, position = 3;
    last = insertAtPosition(last, element, position);

    System.out.print("List after insertions: ");
    printList(last);
  }
}
Output
Original list: 20 30 40 50
List after insertions: 20 30 99 40 50