Algorithm to insert a node at the beginning of circular linked list

Q. Program to insert a new node at the beginning of the circular linked list.

Explanation

In this program, we will create a circular linked list and insert every new node at the beginning of the list. If the list is empty, then head and tail will point to the newly added node. If the list is not empty, then we will store the data of the head into a temporary node temp and make new node as the head. This new head will point to the temporary node. In simple words, the newly added node will be the first node(head) and previous head(temp) will become the second node of the list.

Algorithm to insert a node at the beginning of circular linked list

After inserting new node to the beginning of the list

Algorithm to insert a node at the beginning of circular linked list

New represents the newly added node. Earlier A was the head of the list. When new is added to the beginning of the list, new will become the new head, and it will point to the previous head, i.e., A.

Algorithm

  1. Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
  2. Define another class for creating the circular linked list and it has two nodes: head and tail. It has two methods: addAtStart() and display() .
  3. addAtStart() will add the node to the beginning of the list:
    1. It first checks whether the head is null (empty list), then it will insert the node as the head.
    2. Both head and tail will point to newly added node.
    3. If the list is not empty, then the newly added node will become the new head, and it will point to previous head.
  4. display() will show all the nodes present in the list.
    1. Define a new node 'current' that will point to the head.
    2. Print current.data till current will points to head again.
    3. Current will point to the next node in the list in each iteration.

Circular Singly Linked List | Insertion

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

Why Circular? 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 next 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.
The structure thus formed is a circular singly linked list and looks like this:

Algorithm to insert a node at the beginning of circular linked list

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

Implementation
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.



Algorithm to insert a node at the beginning of circular linked list

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 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
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.

Algorithm to insert a node at the beginning of circular linked list

After inserting node T,

Algorithm to insert a node at the beginning of circular linked list

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.
Function to insert a node into an empty list,




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;
}




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




# 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
# this code is contributed by shivanisinghss2110




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




<script>
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
</script>


Insertion at the beginning of the list
To insert a node at the beginning of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next.
3. last -> next = T.

Algorithm to insert a node at the beginning of circular linked list

After insertion,

Algorithm to insert a node at the beginning of circular linked list

Function to insert nodes at the beginning of the list,




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;
}




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




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




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




<script>
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
</script>


Insertion at the end of the list
To insert a node at the end of the list, follow these steps:
1. Create a node, say T.
2. Make T -> next = last -> next;
3. last -> next = T.
4. last = T.

Algorithm to insert a node at the beginning of circular linked list

After insertion,

Algorithm to insert a node at the beginning of circular linked list

Function to insert a node at the end of the List




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;
}




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




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




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




<script>
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
</script>


Insertion in between the nodes
To insert a node in between the two nodes, follow these steps:
1. Create a node, say T.
2. Search for the node after which T needs to be inserted, say that node is P.
3. Make T -> next = P -> next;
4. P -> next = T.
Suppose 12 needs to be inserted after the node has the value 10,

Algorithm to insert a node at the beginning of circular linked list

After searching and insertion,

Algorithm to insert a node at the beginning of circular linked list

Function to insert a node at the end of the List,




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;
}




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




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




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




<script>
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
</script>

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




#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);
}
// Driven Program
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;
}




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);
}
// Driven 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);
traverse(last);
}
}
/* This code contributed by PrinciRaj1992 */




class Node:
def __init__(self, data):
self.data = data
self.next = None
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




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);
}
// Driven 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);
traverse(last);
}
}
// This code contributed by Rajput-Ji




<script>
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);
}
// Driven 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);
</script>

Output:

2 4 6 8 10 12

This article is contributed by Anuj Chauhan. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Algorithm to insert a node at the beginning of circular linked list




Article Tags :
Linked List
circular linked list
Practice Tags :
Linked List
circular linked list

Circular Linked List

In this article, you will learn what circular linked list is and its types with implementation.

A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle.

There are basically two types of circular linked list:

1. Circular Singly Linked List

Here, the address of the last node consists of the address of the first node.

Algorithm to insert a node at the beginning of circular linked list
Circular Linked List Representation

2. Circular Doubly Linked List

Here, in addition to the last node storing the address of the first node, the first node will also store the address of the last node.

Algorithm to insert a node at the beginning of circular linked list
Circular Doubly Linked List Representation

Note: We will be using the singly circular linked list to represent the working of circular linked list.


Inserting a node at the beginning of a linked list

The new node will be added at the beginning of a linked list.


Example

Assume that the linked list has elements: 20 30 40 NULL

If we insert 100, it will be added at the beginning of a linked list.

After insertion, the new linked list will be

100 20 30 40 NULL




Required knowledge

Basic C programming, Functions, Dynamic memory allocation, Circular linked list

Algorithm to insert a new node at the beginning of a Circular linked list

For inserting new node at the beginning of a circular linked list. We need to connect new node with the first node and re-connect the last node with new node instead of head node.

Algorithm to insert new node at the beginning of Circular linked list %%Input : head {Pointer to first node of the linked list} Begin If (head == NULL) then write ('List is empty') End if Else then alloc (newNode) read (data) newNode.data ← data; newNode.next ← head; current ← head; While (current.next != head) do current ← current.next; End while current.next ← newNode; End if End

C Exercises: Insert a node at the beginning of a circular linked list

Last update on December 20 2021 09:10:12 (UTC/GMT +8 hours)