Circular Singly Linked List | Insertion

Last Updated : 10 Jan, 2023

We have discussed Singly and Circular Linked List in the following post:
Singly Linked List
Circular Linked List

Why Circular linked list?

In a singly linked list, for accessing any node of the linked list, we start traversing from the first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node. This problem can be solved by slightly altering the structure of a singly linked list. In a singly linked list, the next part (pointer to the next node) of the last node is NULL. If we utilize this link to point to the first node, then we can reach the preceding nodes. Refer to this for more advantages of circular linked lists.

In this post, the implementation and insertion of a node in a Circular Linked List using a singly linked list are explained.

Implementation of circular linked list:

To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node.

The pointer last points to node Z and last -> next points to node P.

Why have we taken a pointer that points to the last node instead of the first node?

For the insertion of a node at the beginning, we need to traverse the whole list. Also, for insertion at the end, the whole list has to be traversed. If instead of the start pointer, we take a pointer to the last node, then in both cases there won’t be any need to traverse the whole list. So insertion at the beginning or at the end takes constant time, irrespective of the length of the list.

Insertion in a circular linked list:

A node can be added in three ways:

Insertion in an empty list
Insertion at the beginning of the list
Insertion at the end of the list
Insertion in between the nodes

Insertion in an empty List:

Initially, when the list is empty, the last pointer will be NULL.

After inserting node T,

After insertion, T is the last node, so the pointer last points to node T. And Node T is the first and the last node, so T points to itself.

Below is the implementation of the above operation:

C++

// C++ program for the above operation 
struct Node* addToEmpty(struct Node* last, int data) 
{ 
    // This function is only for empty list 
    if (last != NULL) 
        return last; 
  
    // Creating a node dynamically. 
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    // Assigning the data. 
    temp->data = data; 
    last = temp; 
    // Note : list was empty. We link single node 
    // to itself. 
    temp->next = last; 
  
    return last; 
}

Java

// Java program for the above operation 
static Node addToEmpty(Node last, int data) 
{ 
    // This function is only for empty list 
    if (last != null) 
        return last; 
  
    // Creating a node dynamically. 
    Node temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
    last = temp; 
    // Note : list was empty. We link single node 
    // to itself. 
    temp.next = last; 
  
    return last; 
} 
  
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above operation 
def addToEmpty(self, data): 
  
        if (self.last != None): 
            return self.last 
  
        # Creating the newnode temp 
        temp = Node(data) 
        self.last = temp 
  
        # Creating the link 
        self.last.next = self.last 
        return self.last 
  # this code is contributed by shivanisinghss2110 

C#

// C# program for the above operation 
static Node addToEmpty(Node last, int data) 
{ 
    // This function is only for empty list 
    if (last != null) 
        return last; 
  
    // Creating a node dynamically. 
    Node temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
    last = temp; 
    // Note : list was empty. We link single node 
    // to itself. 
    temp.next = last; 
  
    return last; 
} 
  
// This code contributed by umadevi9616

Javascript

// Javascript program for the above operation 
function addToEmpty(last , data) 
{ 
    // This function is only for empty list 
    if (last != null) 
      return last; 
  
    // Creating a node dynamically. 
    var temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
    last = temp; 
    // Note : list was empty. We link single node 
    // to itself. 
    temp.next = last; 
  
    return last; 
} 
  
// This code contributed by umadevi9616  

Time Complexity: O(1), As we have to perform constant number of operations.
Auxiliary Space: O(1), As constant extra space is used.

Insertion at the beginning of the list

To insert a node at the beginning of the list, follow these steps:

Create a node, say T
Make T -> next = last -> next
last -> next = T

After insertion,

Below is the implementation of the above operation:

C++

// C++ program for the above operation 
  
struct Node* addBegin(struct Node* last, int data) 
{ 
    if (last == NULL) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically. 
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    // Assigning the data. 
    temp->data = data; 
  
    // Adjusting the links. 
    temp->next = last->next; 
    last->next = temp; 
  
    return last; 
}

Java

// Java program for the above operation 
  
static Node addBegin(Node last, int data) 
{ 
    if (last == null) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically 
    Node temp = new Node(); 
  
    // Assigning the data 
    temp.data = data; 
  
    // Adjusting the links 
    temp.next = last.next; 
    last.next = temp; 
  
    return last; 
} 
  
// This code is contributed by rutvik_56

Python3

# Python3 program for the above operation 
  
def addBegin(self, data): 
  
    if (self.last == None): 
        return self.addToEmpty(data) 
  
    temp = Node(data) 
    temp.next = self.last.next
    self.last.next = temp 
  
    return self.last 
  # this code is contributed by shivanisinghss2110 

C#

// C# program for the above operation 
  
static Node addBegin(Node last, int data) 
{ 
    if (last == null) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically 
    Node temp = new Node(); 
  
    // Assigning the data 
    temp.data = data; 
  
    // Adjusting the links 
    temp.next = last.next; 
    last.next = temp; 
  
    return last; 
} 
  
// This code is contributed by Pratham76

Javascript

// Javascript program for the above operation 
  
function addBegin(last , data) 
{ 
    if (last == null) 
      return addToEmpty(last, data); 
   
    // Creating a node dynamically. 
    var temp = new Node(); 
   
    // Assigning the data. 
    temp.data = data; 
  
    // Adjusting the links. 
    temp.next = last.next; 
    last.next = temp; 
    return last; 
} 
   
// This code contributed by Shivani 

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

Insertion at the end of the list

To insert a node at the end of the list, follow these steps:

Create a node, say T
Make T -> next = last -> next
last -> next = T
last = T

After insertion

Below is the implementation of the above operation:

C++

// C++ program for the above operation 
  
struct Node* addEnd(struct Node* last, int data) 
{ 
    if (last == NULL) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically. 
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    // Assigning the data. 
    temp->data = data; 
  
    // Adjusting the links. 
    temp->next = last->next; 
    last->next = temp; 
    last = temp; 
  
    return last; 
}

Java

// Java program for the above operation 
  
static Node addEnd(Node last, int data) 
{ 
    if (last == null) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically. 
    Node temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
  
    // Adjusting the links. 
    temp.next = last.next; 
    last.next = temp; 
    last = temp; 
  
    return last; 
} 
  
// This code is contributed by shivanisinghss2110

Python3

# Python3 program for the above operation 
  
def addEnd(self, data): 
  
    if (self.last == None): 
        return self.addToEmpty(data) 
 # Assigning the data. 
    temp = Node(data) 
  
  # Adjusting the links. 
    temp.next = self.last.next
    self.last.next = temp 
    self.last = temp 
  
    return self.last 
  
   # This code is contributed by shivanisinghss2110 

C#

// C# program for the above operation 
  
static Node addEnd(Node last, int data) 
{ 
    if (last == null) 
        return addToEmpty(last, data); 
  
    // Creating a node dynamically. 
    Node temp = new Node(); 
  
    // Assigning the data. 
    temp.data = data; 
  
    // Adjusting the links. 
    temp.next = last.next; 
    last.next = temp; 
    last = temp; 
  
    return last; 
} 
  
// This code is contributed by shivanisinghss2110

Javascript

// Javascript program for the above operation 
  
    function addEnd(last, data) { 
        if (last == null) return addToEmpty(last, data); 
  
        var temp = new Node(); 
  
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
        last = temp; 
  
        return last; 
    } 
  
    // this code is contributed by shivanisinghss2110 

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

Insertion in between the nodes

To insert a node in between the two nodes, follow these steps:

Create a node, say T.
Search for the node after which T needs to be inserted, say that node is P.
Make T -> next = P -> next;
P -> next = T.

Suppose 12 needs to be inserted after the node that has the value 8,

After searching and insertion,

Below is the implementation of the above operation:

C++

// C++ program for the above operation 
  
struct Node* addAfter(struct Node* last, int data, int item) 
{ 
    if (last == NULL) 
        return NULL; 
  
    struct Node *temp, *p; 
    p = last->next; 
  
    // Searching the item. 
    do { 
        if (p->data == item) { 
            // Creating a node dynamically. 
            temp 
                = (struct Node*)malloc(sizeof(struct Node)); 
  
            // Assigning the data. 
            temp->data = data; 
  
            // Adjusting the links. 
            temp->next = p->next; 
  
            // Adding newly allocated node after p. 
            p->next = temp; 
  
            // Checking for the last node. 
            if (p == last) 
                last = temp; 
  
            return last; 
        } 
        p = p->next; 
    } while (p != last->next); 
  
    cout << item << " not present in the list." << endl; 
    return last; 
}

Java

// Java program for the above operation 
  
static Node addAfter(Node last, int data, int item) 
{ 
    if (last == null) 
        return null; 
  
    Node temp, p; 
    p = last.next; 
    do { 
        if (p.data == item) { 
            temp = new Node(); 
            temp.data = data; 
            temp.next = p.next; 
            p.next = temp; 
  
            if (p == last) 
                last = temp; 
            return last; 
        } 
        p = p.next; 
    } while (p != last.next); 
  
    System.out.println(item + " not present in the list."); 
    return last; 
} 
  
// This code is contributed by shivanisinghss2110

Python3

# Python3 program for the above operation 
  
def addAfter(self, data, item): 
  
    if (self.last == None): 
        return None
  
    temp = Node(data) 
    p = self.last.next
    while p: 
        if (p.data == item): 
            temp.next = p.next
            p.next = temp 
  
            if (p == self.last): 
                self.last = temp 
                return self.last 
            else: 
                return self.last 
        p = p.next
        if (p == self.last.next): 
            print(item, "not present in the list") 
            break
  
# This code is contributed by shivanisinghss2110 

C#

// C# program for the above operation 
  
static Node addAfter(Node last, int data, int item) 
{ 
    if (last == null) 
        return null; 
  
    Node temp, p; 
    p = last.next; 
    do { 
        if (p.data == item) { 
            temp = new Node(); 
            temp.data = data; 
            temp.next = p.next; 
            p.next = temp; 
  
            if (p == last) 
                last = temp; 
            return last; 
        } 
        p = p.next; 
    } while (p != last.next); 
  
    Console.WriteLine(item + " not present in the list."); 
    return last; 
} 
  
// This code is contributed by shivanisinghss2110

Javascript

// Javascript program for the above operation 
  
 function addAfter(last, data, item) { 
        if (last == null) return null; 
  
        var temp, p; 
        p = last.next; 
        do { 
          if (p.data == item) { 
            temp = new Node(); 
            temp.data = data; 
            temp.next = p.next; 
            p.next = temp; 
  
            if (p == last) last = temp; 
            return last; 
          } 
          p = p.next; 
        } while (p != last.next); 
  
        document.write(item + " not present in the list. <br>"); 
        return last; 
      } 
        
    // This code is contributed by shivanisinghss2110 
     

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

Below is a complete program that uses all of the above methods to create a circular singly linked list.

C++

// C++ program for the above methods 
  
#include <bits/stdc++.h> 
using namespace std; 
  
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
struct Node* addToEmpty(struct Node* last, int data) 
{ 
    // This function is only for empty list 
    if (last != NULL) 
        return last; 
  
    // Creating a node dynamically. 
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    // Assigning the data. 
    temp->data = data; 
    last = temp; 
  
    // Creating the link. 
    last->next = last; 
    return last; 
} 
  
struct Node* addBegin(struct Node* last, int data) 
{ 
    if (last == NULL) 
        return addToEmpty(last, data); 
  
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
    temp->data = data; 
    temp->next = last->next; 
    last->next = temp; 
    return last; 
} 
  
struct Node* addEnd(struct Node* last, int data) 
{ 
    if (last == NULL) 
        return addToEmpty(last, data); 
  
    struct Node* temp 
        = (struct Node*)malloc(sizeof(struct Node)); 
  
    temp->data = data; 
    temp->next = last->next; 
    last->next = temp; 
    last = temp; 
  
    return last; 
} 
  
struct Node* addAfter(struct Node* last, int data, int item) 
{ 
    if (last == NULL) 
        return NULL; 
  
    struct Node *temp, *p; 
    p = last->next; 
  
    do { 
        if (p->data == item) { 
            temp 
                = (struct Node*)malloc(sizeof(struct Node)); 
            temp->data = data; 
            temp->next = p->next; 
            p->next = temp; 
            if (p == last) 
                last = temp; 
            return last; 
        } 
        p = p->next; 
    } while (p != last->next); 
  
    cout << item << " not present in the list." << endl; 
    return last; 
} 
  
void traverse(struct Node* last) 
{ 
    struct Node* p; 
  
    // If list is empty, return. 
    if (last == NULL) { 
        cout << "List is empty." << endl; 
        return; 
    } 
  
    // Pointing to first Node of the list. 
    p = last->next; 
  
    // Traversing the list. 
    do { 
        cout << p->data << " "; 
        p = p->next; 
    } while (p != last->next); 
} 
  
// Driver code 
int main() 
{ 
    struct Node* last = NULL; 
    last = addToEmpty(last, 6); 
    last = addBegin(last, 4); 
    last = addBegin(last, 2); 
    last = addEnd(last, 8); 
    last = addEnd(last, 12); 
    last = addAfter(last, 10, 8); 
  
    // Function call 
    traverse(last); 
    return 0; 
}

Java

// Java program for the above methods 
  
public class GFG { 
    static class Node { 
        int data; 
        Node next; 
    }; 
    
    static Node addToEmpty(Node last, int data) 
    { 
        // This function is only for empty list 
        
        if (last != null) 
            return last; 
        // Creating a node dynamically 
  
        Node temp = new Node(); 
        // Assigning the data. 
        
        temp.data = data; 
        last = temp; 
        // Creating the link. 
        
        last.next = last; 
        return last; 
    } 
    
    static Node addBegin(Node last, int data) 
    { 
        if (last == null) 
            return addToEmpty(last, data); 
        
        Node temp = new Node(); 
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
        return last; 
    } 
    
    static Node addEnd(Node last, int data) 
    { 
        if (last == null) 
            return addToEmpty(last, data); 
  
        Node temp = new Node(); 
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
        last = temp; 
        return last; 
    } 
    
    static Node addAfter(Node last, int data, int item) 
    { 
        if (last == null) 
            return null; 
        
        Node temp, p; 
        p = last.next; 
        do { 
            if (p.data == item) { 
                temp = new Node(); 
                temp.data = data; 
                temp.next = p.next; 
                p.next = temp; 
                if (p == last) 
                    last = temp; 
                return last; 
            } 
            p = p.next; 
        } while (p != last.next); 
        
        System.out.println(item 
                           + " not present in the list."); 
        return last; 
    } 
    
    static void traverse(Node last) 
    { 
        Node p; 
        // If list is empty, return. 
        
        if (last == null) { 
            System.out.println("List is empty."); 
            return; 
        } 
        // Pointing to first Node of the list. 
        
        p = last.next; 
        // Traversing the list. 
        
        do { 
            System.out.print(p.data + " "); 
            p = p.next; 
        } while (p != last.next); 
    } 
    
    // Driver code 
    public static void main(String[] args) 
    { 
        Node last = null; 
        last = addToEmpty(last, 6); 
        last = addBegin(last, 4); 
        last = addBegin(last, 2); 
        last = addEnd(last, 8); 
        last = addEnd(last, 12); 
        last = addAfter(last, 10, 8); 
        
          // Function call 
        traverse(last); 
    } 
} 
/* This code contributed by PrinciRaj1992 */
// This code is updated by Susobhan AKhuli

Python3

# Python3 program for the above methods 
  
  
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = 0
  
  
class CircularLinkedList: 
    def __init__(self): 
        self.last = None
  
    # This function is only for empty list 
    def addToEmpty(self, data): 
        if (self.last != None): 
            return self.last 
        # Creating the newnode temp 
        temp = Node(data) 
        self.last = temp 
        # Creating the link 
        self.last.next = self.last 
        return self.last 
  
    def addBegin(self, data): 
        if (self.last == None): 
            return self.addToEmpty(data) 
        temp = Node(data) 
        temp.next = self.last.next
        self.last.next = temp 
        return self.last 
  
    def addEnd(self, data): 
        if (self.last == None): 
            return self.addToEmpty(data) 
        temp = Node(data) 
        temp.next = self.last.next
        self.last.next = temp 
        self.last = temp 
        return self.last 
  
    def addAfter(self, data, item): 
  
        if (self.last == None): 
            return None
  
        temp = Node(data) 
        p = self.last.next
        while p: 
            if (p.data == item): 
                temp.next = p.next
                p.next = temp 
  
                if (p == self.last): 
                    self.last = temp 
                    return self.last 
                else: 
                    return self.last 
            p = p.next
            if (p == self.last.next): 
                print(item, "not present in the list") 
                break
  
    def traverse(self): 
        if (self.last == None): 
            print("List is empty") 
            return
        temp = self.last.next
        while temp: 
            print(temp.data, end=" ") 
            temp = temp.next
            if temp == self.last.next: 
                break
  
  
# Driver Code 
if __name__ == '__main__': 
    llist = CircularLinkedList() 
    last = llist.addToEmpty(6) 
    last = llist.addBegin(4) 
    last = llist.addBegin(2) 
    last = llist.addEnd(8) 
    last = llist.addEnd(12) 
    last = llist.addAfter(10, 8) 
    llist.traverse() 
# This code is contributed by 
# Aditya Singh 

C#

// C# program for the above methods 
  
using System; 
  
public class GFG { 
  
    public class Node { 
        public int data; 
        public Node next; 
    }; 
  
    static Node addToEmpty(Node last, int data) 
    { 
        // This function is only for empty list 
        if (last != null) 
            return last; 
  
        // Creating a node dynamically. 
        Node temp = new Node(); 
  
        // Assigning the data. 
        temp.data = data; 
        last = temp; 
  
        // Creating the link. 
        last.next = last; 
  
        return last; 
    } 
  
    static Node addBegin(Node last, int data) 
    { 
        if (last == null) 
            return addToEmpty(last, data); 
  
        Node temp = new Node(); 
  
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
  
        return last; 
    } 
  
    static Node addEnd(Node last, int data) 
    { 
        if (last == null) 
            return addToEmpty(last, data); 
  
        Node temp = new Node(); 
  
        temp.data = data; 
        temp.next = last.next; 
        last.next = temp; 
        last = temp; 
  
        return last; 
    } 
  
    static Node addAfter(Node last, int data, int item) 
    { 
        if (last == null) 
            return null; 
  
        Node temp, p; 
        p = last.next; 
        do { 
            if (p.data == item) { 
                temp = new Node(); 
                temp.data = data; 
                temp.next = p.next; 
                p.next = temp; 
  
                if (p == last) 
                    last = temp; 
                return last; 
            } 
            p = p.next; 
        } while (p != last.next); 
  
        Console.WriteLine(item 
                          + " not present in the list."); 
        return last; 
    } 
  
    static void traverse(Node last) 
    { 
        Node p; 
  
        // If list is empty, return. 
        if (last == null) { 
            Console.WriteLine("List is empty."); 
            return; 
        } 
  
        // Pointing to first Node of the list. 
        p = last.next; 
  
        // Traversing the list. 
        do { 
            Console.Write(p.data + " "); 
            p = p.next; 
  
        } while (p != last.next); 
    } 
  
    // Driver code 
    public static void Main(String[] args) 
    { 
        Node last = null; 
  
        last = addToEmpty(last, 6); 
        last = addBegin(last, 4); 
        last = addBegin(last, 2); 
        last = addEnd(last, 8); 
        last = addEnd(last, 12); 
        last = addAfter(last, 10, 8); 
  
          // Function call 
        traverse(last); 
    } 
} 
// This code contributed by Rajput-Ji

Javascript

    class Node { 
        constructor() { 
            this.data = 0; 
            this.next = null; 
        } 
    } 
  
function addToEmpty(last, data) { 
    // This function is only for empty list         
    if (last != null) return last; 
    // Creating a node dynamically.         
    var temp = new Node(); 
    // Assigning the data.     
    temp.data = data; 
    last = temp; 
    // Creating the link.     
    last.next = last; 
    return last; 
} 
  
function addBegin(last, data) { 
    if (last == null) return addToEmpty(last, data); 
    var temp = new Node(); 
    temp.data = data; 
    temp.next = last.next; 
    last.next = temp; 
    return last; 
} 
  
function addEnd(last, data) { 
    if (last == null) return addToEmpty(last, data); 
    var temp = new Node(); 
    temp.data = data; 
    temp.next = last.next; 
    last.next = temp; 
    last = temp; 
    return last; 
} 
  
function addAfter(last, data, item) { 
    if (last == null) return null; 
    var temp, p; 
    p = last.next; 
    do { 
        if (p.data == item) { 
            temp = new Node(); 
            temp.data = data; 
            temp.next = p.next; 
            p.next = temp; 
            if (p == last) last = temp; 
            return last; 
        } 
        p = p.next; 
    } while (p != last.next); 
    document.write(item + " not present in the list. <br>"); 
    return last; 
} 
  
function traverse(last) { 
    var p; 
    // If list is empty, return.         
    if (last == null) { 
        document.write("List is empty.<br>"); 
        return; 
    } 
    // Pointing to first Node of the list.     
    p = last.next; 
    // Traversing the list.         
    do { 
        document.write(p.data + " "); 
        p = p.next; 
    } while (p != last.next); 
} 
  
// Driver code     
var last = null; 
last = addToEmpty(last, 6); 
last = addBegin(last, 4); 
last = addBegin(last, 2); 
last = addEnd(last, 8); 
last = addEnd(last, 12); 
last = addAfter(last, 10, 8); 
traverse(last); 

Output

2 4 6 8 10 12

Time Complexity: O(N)
Auxiliary Space: O(1), as we are not using any extra space.

Suggest improvement

Introduction to Circular Linked List

Insertion in Doubly Circular Linked List

Share your thoughts in the comments

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Types of Linked List

Basic operations on Linked List

Easy problems on Linked List

Medium problems on Linked List

Hard problems on Linked List

Circular Singly Linked List | Insertion

Why Circular linked list?

Implementation of circular linked list:

Why have we taken a pointer that points to the last node instead of the first node?

Insertion in a circular linked list:

Insertion in an empty List:

C++

Java

Python3

C#

Javascript

Insertion at the beginning of the list

C++

Java

Python3

C#

Javascript

Insertion at the end of the list

C++

Java

Python3

C#

Javascript

Insertion in between the nodes

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?