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:
At the beginning of the list.
At the end of the list.
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:
- Create newNode.
- If the list is empty (
last == null), make newNode point to itself; it is the only node and is returned as the newlast. - Otherwise point newNode.next at the current first node (
last.next) and set last.next = newNode. The new node is now first, andlastdoes not change.
This is O(1).
//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);
}
}
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:
- Create newNode. If the list is empty, make it point to itself and return it.
- Otherwise set newNode.next = last.next (the first node) and last.next = newNode.
- Move
lastto newNode, because the new node is now the last node of the ring.
This is also O(1).
//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);
}
}
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):
- Reject positions smaller than 1. If the list is empty, only position 1 is valid, and the new node points to itself.
- Position 1 is an insertion at the beginning.
- 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.
- Link the new node in: newNode.next = currNode.next, then currNode.next = newNode.
- If currNode was the last node, the new node becomes the new
last.
Reaching the position takes O(n) in the worst case.
// 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);
}
}
Original list: 20 30 40 50 List after insertions: 20 30 99 40 50