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:
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,
|
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
|
|
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
|
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,
|
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
|
|
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
|
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
|
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
|
|
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
|
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,
|
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 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 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
Java
Python3
C#
Javascript
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. C
Java
Python3
C#
Javascript
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
Circular Linked ListCircular Linked List is little more complicated linked data structure. In the circular linked list we can insert elements anywhere in the list whereas in the array we cannot insert element anywhere in the list because it is in the contiguous memory. In the circular linked list the previous element stores the address of the next element and the last element stores the address of the starting element. The elements points to each other in a circular way which forms a circular chain. The circular linked list has a dynamic size which means the memory can be allocated when it is required. Application of Circular Linked List
Implementing Circular Linked ListImplementing a circular linked list is very easy and almost similar to linear linked list implementation, with the only difference being that, in circular linked list the last Node will have it's next point to the Head of the List. In Linear linked list the last Node simply holds NULL in it's next pointer. So this will be oue Node class, as we have already studied in the lesson, it will be used to form the List. class Node { public: int data; //pointer to the next node node* next; node[] { data = 0; next = NULL; } node[int x] { data = x; next = NULL; } }Circular Linked ListCircular Linked List class will be almost same as the Linked List class that we studied in the previous lesson, with a few difference in the implementation of class methods. class CircularLinkedList { public: node *head; //declaring the functions //function to add Node at front int addAtFront[node *n]; //function to check whether Linked list is empty int isEmpty[]; //function to add Node at the End of list int addAtEnd[node *n]; //function to search a value node* search[int k]; //function to delete any Node node* deleteNode[int x]; CircularLinkedList[] { head = NULL; } }Insertion at the BeginningSteps to insert a Node at beginning :
Insertion at the EndSteps to insert a Node at the end :
Searching for an Element in the ListIn searhing we do not have to do much, we just need to traverse like we did while getting the last node, in this case we will also compare the data of the Node. If we get the Node with the same data, we will return it, otherwise we will make our pointer point the next Node, and so on. node* CircularLinkedList :: search[int x] { node *ptr = head; while[ptr != NULL && ptr->data != x] { //until we reach the end or we find a Node with data x, we keep moving ptr = ptr->next; } return ptr; }Deleting a Node from the ListDeleting a node can be done in many ways, like we first search the Node with data which we want to delete and then we delete it. In our approach, we will define a method which will take the data to be deleted as argument, will use the search method to locate it and will then remove the Node from the List. To remove any Node from the list, we need to do the following :
Insertion into circular singly linked list at beginningThere are two scenario in which a node can be inserted in circular singly linked list at beginning. Either the node will be inserted in an empty list or the node is to be inserted in an already filled list. Firstly, allocate the memory space for the new node by using the malloc method of C language. In the first scenario, the condition head == NULL will be true. Since, the list in which, we are inserting the node is a circular singly linked list, therefore the only node of the list [which is just inserted into the list] will point to itself only. We also need to make the head pointer point to this node. This will be done by using the following statements. In the second scenario, the condition head == NULL will become false which means that the list contains at least one node. In this case, we need to traverse the list in order to reach the last node of the list. This will be done by using the following statement. At the end of the loop, the pointer temp would point to the last node of the list. Since, in a circular singly linked list, the last node of the list contains a pointer to the first node of the list. Therefore, we need to make the next pointer of the last node point to the head node of the list and the new node which is being inserted into the list will be the new head node of the list therefore the next pointer of temp will point to the new node ptr. This will be done by using the following statements. the next pointer of temp will point to the existing head node of the list. Now, make the new node ptr, the new head node of the circular singly linked list. in this way, the node ptr has been inserted into the circular singly linked list at beginning. Video liên quanChủ Đề |