Open In App

Circular Singly Linked List | Insertion

Last Updated : 10 Jan, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

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.



Like Article
Suggest improvement
Previous
Next
Share your thoughts in the comments

Similar Reads