How many pointers need to be modified in a circular linked list when inserting a new record?

Circular Singly Linked List | Insertion

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

Table of Contents Show

Circular Singly Linked List | Insertion
Sorted insert for circular linked list
Data Structures Questions – Set 10

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:

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.

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.

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

C++

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

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

# 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

Javascript

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

After insertion,

Function to insert nodes at the beginning of the list,

C++

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

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

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

Javascript

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

After insertion,

Function to insert a node at the end of the List

C++

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

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

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

Javascript

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

After searching and insertion,

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

C++

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

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

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

Javascript

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

C++

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

Java

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

Python3

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

Javascript

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

Article Tags :

Linked List

circular linked list

Practice Tags :

Linked List

circular linked list

Read Full Article

Sorted insert for circular linked list

Difficulty Level: Rookie
Write a C function to insert a new value in a sorted Circular Linked List (CLL). For example, if the input CLL is following.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Algorithm:
Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, following are the three cases that need to be handled.

1) Linked List is empty: a) since new_node is the only node in CLL, make a self loop. new_node->next = new_node; b) change the head pointer to point to new node. *head_ref = new_node; 2) New node is to be inserted just before the head node: (a) Find out the last node using a loop. while(current->next != *head_ref) current = current->next; (b) Change the next of last node. current->next = new_node; (c) Change next of new node to point to head. new_node->next = *head_ref; (d) change the head pointer to point to new node. *head_ref = new_node; 3) New node is to be inserted somewhere after the head: (a) Locate the node after which new node is to be inserted. while ( current->next!= *head_ref && current->next->data < new_node->data) { current = current->next; } (b) Make next of new_node as next of the located pointer new_node->next = current->next; (c) Change the next of the located pointer current->next = new_node;

C++

// C++ program for sorted insert
// in circular linked list
#include <bits/stdc++.h>

using namespace std;
/* structure for a node */

class Node
{ 

public:

int data;

Node *next;
}; 
/* function to insert a new_node in a list in sorted way. 
Note that this function expects a pointer to head node 
as this can modify the head of the input linked list */

void sortedInsert(Node** head_ref, Node* new_node)
{ 

Node* current = *head_ref;

// Case 1 of the above algo

if (current == NULL)

{

new_node->next = new_node;

*head_ref = new_node;

}

// Case 2 of the above algo

else if (current->data >= new_node->data)

{

/* If value is smaller than head's value then

we need to change next of last node */

while(current->next != *head_ref)

current = current->next;

current->next = new_node;

new_node->next = *head_ref;

*head_ref = new_node;

}

// Case 3 of the above algo

else

{

/* Locate the node before the point of insertion */

while (current->next!= *head_ref &&

current->next->data < new_node->data)

current = current->next;

new_node->next = current->next;

current->next = new_node;

}
} 
/* Function to print nodes in a given linked list */

void printList(Node *start)
{ 

Node *temp;

if(start != NULL)

{

temp = start;

do {

cout<<temp->data<<" ";

temp = temp->next;

} while(temp != start);

}
} 
/* Driver code */

int main()
{ 

int arr[] = {12, 56, 2, 11, 1, 90};

int list_size, i;

/* start with empty linked list */

Node *start = NULL;

Node *temp;

/* Create linked list from the array arr[].

Created linked list will be 1->2->11->12->56->90 */

for (i = 0; i< 6; i++)

{

temp = new Node();

temp->data = arr[i];

sortedInsert(&start, temp);

}

printList(start);

return 0;
} 
// This code is contributed by rathbhupendra.

#include<stdio.h>
#include<stdlib.h>
/* structure for a node */

struct Node
{

int data;

struct Node *next;
};
/* function to insert a new_node in a list in sorted way.

Note that this function expects a pointer to head node

as this can modify the head of the input linked list */

void sortedInsert(struct Node** head_ref, struct Node* new_node)
{

struct Node* current = *head_ref;

// Case 1 of the above algo

if (current == NULL)

{

new_node->next = new_node;

*head_ref = new_node;

}

// Case 2 of the above algo

else if (current->data >= new_node->data)

{

/* If value is smaller than head's value then

we need to change next of last node */

while(current->next != *head_ref)

current = current->next;

current->next = new_node;

new_node->next = *head_ref;

*head_ref = new_node;

}

// Case 3 of the above algo

else

{

/* Locate the node before the point of insertion */

while (current->next!= *head_ref &&

current->next->data < new_node->data)

current = current->next;

new_node->next = current->next;

current->next = new_node;

}
}
/* Function to print nodes in a given linked list */

void printList(struct Node *start)
{

struct Node *temp;

if(start != NULL)

{

temp = start;

printf("\n");

do {

printf("%d ", temp->data);

temp = temp->next;

} while(temp != start);

}
}
/* Driver program to test above functions */

int main()
{

int arr[] = {12, 56, 2, 11, 1, 90};

int list_size, i;

/* start with empty linked list */

struct Node *start = NULL;

struct Node *temp;

/* Create linked list from the array arr[].

Created linked list will be 1->2->11->12->56->90 */

for (i = 0; i< 6; i++)

{

temp = (struct Node *)malloc(sizeof(struct Node));

temp->data = arr[i];

sortedInsert(&start, temp);

}

printList(start);

return 0;
}

Java

// Java program for sorted insert in circular linked list

class Node
{

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}
}

class LinkedList
{

Node head;

// Constructor

LinkedList() { head = null; }

/* function to insert a new_node in a list in sorted way.

Note that this function expects a pointer to head node

as this can modify the head of the input linked list */

void sortedInsert(Node new_node)

{

Node current = head;

// Case 1 of the above algo

if (current == null)

{

new_node.next = new_node;

head = new_node;

}

// Case 2 of the above algo

else if (current.data >= new_node.data)

{

/* If value is smaller than head's value then

we need to change next of last node */

while (current.next != head)

current = current.next;

current.next = new_node;

new_node.next = head;

head = new_node;

}

// Case 3 of the above algo

else

{

/* Locate the node before the point of insertion */

while (current.next != head &&

current.next.data < new_node.data)

current = current.next;

new_node.next = current.next;

current.next = new_node;

}

}

// Utility method to print a linked list

void printList()

{

if (head != null)

{

Node temp = head;

do

{

System.out.print(temp.data + " ");

temp = temp.next;

} while (temp != head);

}

}

// Driver code to test above

public static void main(String[] args)

{

LinkedList list = new LinkedList();

// Creating the linkedlist

int arr[] = new int[] {12, 56, 2, 11, 1, 90};

/* start with empty linked list */

Node temp = null;

/* Create linked list from the array arr[].

Created linked list will be 1->2->11->12->56->90*/

for (int i = 0; i < 6; i++)

{

temp = new Node(arr[i]);

list.sortedInsert(temp);

}

list.printList();

}
}
// This code has been contributed by Mayank Jaiswal

Python3

# Node class 

class Node:

# Constructor to initialize the node object

def __init__(self, data):

self.data = data

self.next = None

class LinkedList:

# Function to initialize head

def __init__(self):

self.head = None

# Function to insert a new node at the beginning

def push(self, new_data):

new_node = Node(new_data)

new_node.next = self.head

self.head = new_node

# Utility function to print the linked LinkedList

def printList(self):

temp = self.head

print(temp.data,end=' ')

temp = temp.next

while(temp != self.head):

print (temp.data,end=' ')

temp = temp.next

""" function to insert a new_node in a list in sorted way.

Note that this function expects a pointer to head node

as this can modify the head of the input linked list """

def sortedInsert(self, new_node):

current = self.head

# Case 1 of the above algo

if current is None:

new_node.next = new_node

self.head = new_node

# Case 2 of the above algo

elif (current.data >= new_node.data):

# If value is smaller than head's value then we

# need to change next of last node

while current.next != self.head :

current = current.next

current.next = new_node

new_node.next = self.head

self.head = new_node

# Case 3 of the above algo

else:

# Locate the node before the point of insertion

while (current.next != self.head and

current.next.data < new_node.data):

current = current.next

new_node.next = current.next

current.next = new_node
# Driver program to test the above function
#llist = LinkedList()

arr = [12, 56, 2, 11, 1, 90]

list_size = len(arr)
# start with empty linked list

start = LinkedList()
# Create linked list from the array arr[]
# Created linked list will be 1->2->11->12->56->90

for i in range(list_size):

temp = Node(arr[i])

start.sortedInsert(temp)
start.printList()
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

// C# program for sorted insert 
// in circular linked list 

using System;

class LinkedList
{ 

public class Node

{

public int data;

public Node next;

public Node(int d)

{

data = d;

next = null;

}

}

Node head;

// Constructor

LinkedList()

{

head = null;

}

/* function to insert a new_node

in a list in sorted way. Note that

this function expects a pointer

to head node as this can modify

the head of the input linked list */

void sortedInsert(Node new_node)

{

Node current = head;

// Case 1 of the above algo

if (current == null)

{

new_node.next = new_node;

head = new_node;

}

// Case 2 of the above algo

else if (current.data >= new_node.data)

{

/* If value is smaller than

head's value then we need

to change next of last node */

while (current.next != head)

current = current.next;

current.next = new_node;

new_node.next = head;

head = new_node;

}

// Case 3 of the above algo

else

{

/* Locate the node before

the point of insertion */

while (current.next != head &&

current.next.data < new_node.data)

current = current.next;

new_node.next = current.next;

current.next = new_node;

}

}

// Utility method to print a linked list

void printList()

{

if (head != null)

{

Node temp = head;

do

{

Console.Write(temp.data + " ");

temp = temp.next;

}

while (temp != head);

}

}

// Driver code

public static void Main(String []args)

{

LinkedList list = new LinkedList();

// Creating the linkedlist

int []arr = {12, 56, 2, 11, 1, 90};

/* start with empty linked list */

Node temp = null;

/* Create linked list from the

array arr[]. Created linked list

will be 1->2->11->12->56->90*/

for (int i = 0; i < 6; i++)

{

temp = new Node(arr[i]);

list.sortedInsert(temp);

}

list.printList();

}
} 
// This code has been contributed 
// by Arnab Kundu

Javascript

<script>
// javascript program for sorted insert in circular linked list
class Node {

constructor(val) {

this.data = val;

this.next = null;

}
}

var head = null;

/*

* function to insert a new_node in a list in sorted way.

* Note that this function expects a pointer to head node

* as this can modify the head of the

* input linked list

*/

function sortedInsert(new_node) {

var current = head;

// Case 1 of the above algo

if (current == null) {

new_node.next = new_node;

head = new_node;

}

// Case 2 of the above algo

else if (current.data >= new_node.data) {

/*

* If value is smaller than head's value then we

* need to change next of last node

*/

while (current.next != head)

current = current.next;

current.next = new_node;

new_node.next = head;

head = new_node;

}

// Case 3 of the above algo

else {

/* Locate the node before the point of insertion */

while (current.next != head && current.next.data < new_node.data)

current = current.next;

new_node.next = current.next;

current.next = new_node;

}

}

// Utility method to print a linked list

function printList() {

if (head != null) {

var temp = head;

do {

document.write(temp.data + " ");

temp = temp.next;

} while (temp != head);

}

}

// Driver code to test above

// Creating the linkedlist

var arr = [ 12, 56, 2, 11, 1, 90 ];

/* start with empty linked list */

var temp = null;

/*

* Create linked list from the array arr.

* Created linked list will be

* 1->2->11->12->56->90

*/

for (i = 0; i < 6; i++) {

temp = new Node(arr[i]);

sortedInsert(temp);

}

printList();
// This code contributed by umadevi9616
</script>

Output:

1 2 11 12 56 90

Time Complexity: O(n) where n is the number of nodes in the given linked list.

Case 2 of the above algorithm/code can be optimized. To implement the suggested change we need to modify case 2 to follow.

// Case 2 of the above algo

else if (current->data >= new_node->data)
{

// swap the data part of head node and new node

// assuming that we have a function swap(int *, int *)

swap(&(current->data), &(new_node->data));

new_node->next = (*head_ref)->next;

(*head_ref)->next = new_node;
}

Java

// Case 2 of the above algo

else if (current.data >= new_node.data)
{

// swap the data part of head node and new node

// assuming that we have a function swap(int *, int *)

Node tmp = current.data;

current.data = new_node.data;

new_node.data = tmp;

new_node.next = (head_ref).next;

(head_ref).next = new_node;
}
// This code is contributed by pratham76.

Python3

# Case 2 of the above algo

elif (current.data >= new_node.data):

# swap the data part of head node and new node

# assuming that we have a function swap(int *, int *)

tmp = current.data;

current.data = new_node.data;

new_node.data = tmp;

new_node.next = (head_ref).next;

(head_ref).next = new_node;
# This code is contributed by _saurabh_jaiswal

// Case 2 of the above algo

else if (current.data >= new_node.data)
{

// swap the data part of head node and new node

// assuming that we have a function swap(int *, int *)

Node tmp = current.data;

current.data = new_node.data;

new_node.data = tmp;

new_node.next = (head_ref).next;

(head_ref).next = new_node;
}
// This code is contributed by rutvik_56

Javascript

<script>
// Case 2 of the above algo

else if (current.data >= new_node.data)
{

// swap the data part of head node and new node

// assuming that we have a function swap(int *, int *)

let tmp = current.data;

current.data = new_node.data;

new_node.data = tmp;

new_node.next = (head_ref).next;

(head_ref).next = new_node;
}

// This code is contributed by avanitrachhadiya2155
</script>

Please write comments if you find the above code/algorithm incorrect, or find other ways to solve the same problem.

Article Tags :

Linked List

Amazon

circular linked list

Microsoft

Zoho

Practice Tags :

Zoho

Amazon

Microsoft

Linked List

circular linked list

Read Full Article

Data Structures Questions – Set 10

Aruna

December 25, 2015

AffairsCloud YouTube Channel - Click Here

AffairsCloud APP Click Here

Dear Aspirants,
Welcome to the Professional Knowledge Section in Affairscloud.com. Here we are providing sample questions in Data Structures. It will be useful for the IBPS SO IT officer and SBI Assistant Manager(System). We have also included some important questions that are repeatedly asked in previous exams.

A postfix expression is merely the _____ of the prefix expression.
(A) Forward
(B) Reverse
(C) Inverse
(D) None of the above
Answer
(B) Reverse
Which of the following begins the search with the element that is located in the middle of the Array?
(A) Random Search
(B) Parallel Search
(C) Binary Search
(D) Serial Search
Answer
(D) Serial Search
In a Circular linked list, insertion of a record involves the modification of____
(A) 1 Pointer
(B) 2 Pointer
(C) 3 Pointer
(D) None of the above
Answer
(B) 2 Pointer
Which of the following is useful in traversing a given graph by breadth first search?
(A) Stack
(B) List
(C) Queue
(D) None of the above
Answer
(C) Queue
A characteristic of the data that binary search uses but linear search ignores is______
(A) Order of the list
(B) length of the list
(C) Both (A) & (B)
(D) None of the above
Answer
(A) Order of the list
A sort which iteratively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called__________
(A) Heap Sort
(B) Quick Sort
(C) Selection Sort
(D) None of the above
Answer
(C) Selection Sort
To insert a node in a circular list at rear position, it should be inserted at ______ of the Queue.
(A) Front – 1 position
(B) Rear position
(C) Front position
(D) None of the above
Answer
(C) Front position
In an extended-binary tree, the nodes with two children are called ……..
(A) Interior node
(B) Domestic node
(C) Internal node
(D) Inner node
Answer
(C) Internal node
A terminal node in a binary tree is called ______
(A) Child
(B) Leaf
(C) Branch
(D) None of the above
Answer
(B) Leaf
Sequential representation of binary tree uses ______
(A) Three dimensional arrays
(B) Array with pointers
(C) Two dimensional arrays
(D) None of the above
Answer
(B) Array with pointers

AffairsCloud Recommends Oliveboard Mock Test

IBPS RRB Officer 2021 - Free Mock Test
IBPS RRB Assistant 2021 - Free Mock Test
SBI Clerk 2021 - Free Mock Test
SBI PO - Free Mock Test
IBPS Clerk - Free Mock Test
RBI Grade B - Free Mock Test

AffairsCloud Ebook - Support Us to Grow

Download Current Affairs APP
We are Hiring: Subject Matter Expert (English/Reasoning/Aptitude) – Freelancer/Full Time

Govt Jobs by Category

Bank Jobs 2022 - 2,315 Vacancies

Govt Jobs 2022 - 4,315 Vacancies

Railway Jobs 2022 - 796 Vacancies

SSC Recruitment 2022 - Various Vacancies

ONGC Recruitment 2022 - Various Vacancies

Bank Jobs Notification

Central Bank of India Officer Recruitment 2022 - 535 Posts
BOB Senior Manager, Manager, Assistant Vice President Recruitment 2022 - 09 Posts
MSC Bank Specialized Officer Recruitment 2022 - 17 Posts
RBI Assistant 2022 Notification Out - 950 Assistant Vacancies, Apply Online @www.rbi.org.in
BOB Office Assistant, Faculty Recruitment 2022 - 03 Posts