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 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
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
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.
Circular Singly Linked List | Insertion
We have discussed Singly and Circular Linked List in the following post:
Singly Linked List
Circular Linked List