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.
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.
Note: We will be using the singly circular linked list to represent the working of circular linked list.
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,
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 |
C#
|
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
|
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,
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 |
C#
|
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
|
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
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 |
C#
|
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
|
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,
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 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 will point to the first node in the linked list. By doing this we ensure that when we insert a new node at the beginning or at the end of the list, we need not traverse the entire list. This is because the last points to the last node while last->next points to the first node. This wouldn’t have been possible if we had pointed the external pointer to the first node. Basic OperationsThe circular linked list supports insertion, deletion, and traversal of the list. We will discuss each of the operations in detail now. InsertionWe can insert a node in a circular linked list either as a first node [empty list], in the beginning, in the end, or in between the other nodes. Let us see each of these insertion operations using a pictorial representation below. #1] Insert in an empty list When there are no nodes in circular list and the list is empty, the last pointer is null, then we insert a new node N by pointing the last pointer to the node N as shown above. The next pointer of N will point to the node N itself as there is only one node. Thus N becomes the first as well as last node in the list. #2] Insert at the beginning of the list As shown in the above representation, when we add a node at the beginning of the list, the next pointer of the last node points to the new node N thereby making it a first node. N->next = last->next Last->next = N #3] Insert at the end of the list To insert a new node at the end of the list, we follow these steps: N-> next = last ->next; #4] Insert in between the list Suppose we need to insert a new node N between N3 and N4, we first need to traverse the list and locate the node after which the new node is to be inserted, in this case, its N3. After the node is located, we perform the following steps. N -> next = N3 -> next; This inserts a new node N after N3. DeletionThe deletion operation of the circular linked list involves locating the node that is to be deleted and then freeing its memory. For this we maintain two additional pointers curr and prev and then traverse the list to locate the node. The given node to be deleted can be the first node, the last node or the node in between. Depending on the location we set the curr and prev pointers and then delete the curr node. A pictorial representation of the deletion operation is shown below. TraversalTraversal is a technique of visiting each and every node. In linear linked lists like singly linked list and doubly linked lists, traversal is easy as we visit each node and stop when NULL is encountered. However, this is not possible in a circular linked list. In a circular linked list, we start from the next of the last node which is the first node and traverse each node. We stop when we once again reach the first node. Now we present an implementation of the circular linked list operations using C++ and Java. We have implemented insertion, deletion and traversal operations here. For a clear understanding, we have depicted the circular linked list as Thus to the last node 50, we again attach node 10 which is the first node, thereby indicating it as a circular linked list. #include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty[struct Node *last, int new_data] { // if last is not null then list is not empty, so return if [last != NULL] return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin[struct Node *last, int new_data] { //if list is empty then add the node by calling insertInEmpty if [last == NULL] return insertInEmpty[last, new_data]; //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd[struct Node *last, int new_data] { //if list is empty then add the node by calling insertInEmpty if [last == NULL] return insertInEmpty[last, new_data]; //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter[struct Node *last, int new_data, int after_item] { //return null if list is empty if [last == NULL] return NULL; struct Node *temp, *p; p = last -> next; do { if [p ->data == after_item] { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if [p == last] last = temp; return last; } p = p -> next; } while[p != last -> next]; cout next=[*head]->next; free[*head]; *head=last->next; } // end of list is reached or node to be deleted not there in the list while[last->next!=*head&&last->next->data!=key] { last=last->next; } // node to be deleted is found, so free the memory and display the list if[last->next->data==key] { d=last->next; last->next=d->next; coutChủ Đề |