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++
struct Node* addToEmpty( struct Node* last, int data)
{
if (last != NULL)
return last;
struct Node* temp
= ( struct Node*) malloc ( sizeof ( struct Node));
temp->data = data;
last = temp;
temp->next = last;
return last;
}
|
Java
static Node addToEmpty(Node last, int data)
{
if (last != null )
return last;
Node temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
Python3
def addToEmpty( self , data):
if ( self .last ! = None ):
return self .last
temp = Node(data)
self .last = temp
self .last. next = self .last
return self .last
|
C#
static Node addToEmpty(Node last, int data)
{
if (last != null )
return last;
Node temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
Javascript
function addToEmpty(last , data)
{
if (last != null )
return last;
var temp = new Node();
temp.data = data;
last = temp;
temp.next = last;
return last;
}
|
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++
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;
}
|
Java
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;
}
|
Python3
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
|
C#
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;
}
|
Javascript
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;
}
|
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++
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;
}
|
Java
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;
}
|
Python3
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
|
C#
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;
}
|
Javascript
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;
}
|
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++
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;
}
|
Java
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;
}
|
Python3
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
|
C#
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;
}
|
Javascript
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;
}
|
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++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* addToEmpty( struct Node* last, int data)
{
if (last != NULL)
return last;
struct Node* temp
= ( struct Node*) malloc ( sizeof ( struct Node));
temp->data = data;
last = temp;
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 (last == NULL) {
cout << "List is empty." << endl;
return ;
}
p = last->next;
do {
cout << p->data << " " ;
p = p->next;
} while (p != last->next);
}
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);
traverse(last);
return 0;
}
|
Java
public class GFG {
static class Node {
int data;
Node next;
};
static Node addToEmpty(Node last, int data)
{
if (last != null )
return last;
Node temp = new Node();
temp.data = data;
last = temp;
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 (last == null ) {
System.out.println( "List is empty." );
return ;
}
p = last.next;
do {
System.out.print(p.data + " " );
p = p.next;
} while (p != last.next);
}
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 );
traverse(last);
}
}
|
Python3
class Node:
def __init__( self , data):
self .data = data
self . next = 0
class CircularLinkedList:
def __init__( self ):
self .last = None
def addToEmpty( self , data):
if ( self .last ! = None ):
return self .last
temp = Node(data)
self .last = temp
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
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()
|
C#
using System;
public class GFG {
public class Node {
public int data;
public Node next;
};
static Node addToEmpty(Node last, int data)
{
if (last != null )
return last;
Node temp = new Node();
temp.data = data;
last = temp;
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 (last == null ) {
Console.WriteLine( "List is empty." );
return ;
}
p = last.next;
do {
Console.Write(p.data + " " );
p = p.next;
} while (p != last.next);
}
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);
traverse(last);
}
}
|
Javascript
class Node {
constructor() {
this .data = 0;
this .next = null ;
}
}
function addToEmpty(last, data) {
if (last != null ) return last;
var temp = new Node();
temp.data = data;
last = temp;
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 (last == null ) {
document.write( "List is empty.<br>" );
return ;
}
p = last.next;
do {
document.write(p.data + " " );
p = p.next;
} while (p != last.next);
}
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);
|
Time Complexity: O(N)
Auxiliary Space: O(1), as we are not using any extra space.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...