Searching an Element in Doubly Circular Linked List using C++

Given a double circular linked list and key, we have to search the key in the linked list and give a proper message if found. Suppose we have a linked list with the specific characters, and we have to search for an element in it. So let's start with the following linked list ?

<-> 5 <-> 8 <-> 9 <-> 2 <-> 4 <->

We will use 4 as a key to finding the solution to the given problem. A double-linked list has no fixed head, so we will start from any node and then mark that node as head, and till we hit this head again, we do a linear search over the linked list and search for the key.

Let's see some input-output scenarios ?

Assume, we are having a doubly circular linked list having 5 nodes <-> 3 <-> 4<-> 5<-> 6<-> 7<-> in it and the element to be found is 6.

Input = <-> 3 <-> 4<-> 5<-> 6<-> 7<-> key=6 Output = Element found 

Let's consider another scenario where the element to be searched is not present in the doubly circular linked list.

Input = <-> 10<->20<->30<->40<->50<-> key=100 Output = Element not found 

Algorithm

The below following steps are the way of approach.

• Implement a linked list and pass values to the nodes by assigning the forward node in each node of the linked list.

• Assigning previous part of the node to the next part of the last node.

• Assigning every previous part of the node to next part of the node.

• Passing the key element to check whether it is present in the doubly circular linked list.

• If the key is present in the doubly circular linked list, returns true.

• Else, it returns false.

Example

Following is the C++ implementation code to perform search operation in a doubly linked list ?

 #include <iostream> #include <vector> using namespace std; class Node { public: int val; Node *left, *right; Node(int val) { this->val = val; } }; bool solve(Node* root, int key) { Node* copy = root; do { if(copy->val == key) return true; copy = copy->right; }while(copy!=root); return false; } int main() { // assigning the forward node in each node of the linked list Node* phead = new Node(5); phead->right = new Node(8); phead->right->right = new Node(9); phead->right->right->right = new Node(2); phead->right->right->right->right = new Node(4); phead->right->right->right->right->right = phead; // assignment of the previous node in each node in the linked list // assigning the previous of the head to the last element phead->left = phead->right->right->right->right; // assigning the left node in each node of the linked list phead->right->left = phead; phead->right->right->left = phead->right; phead->right->right->right->left = phead->right->right; phead->right->right->right->right->left = phead->right->right->right; if(solve(phead, 4)) cout << "Element present"; else cout << "Element not present"; return 0; } 
 
 
 

Output

Element present 

Explanation

The key 4 is present in the double linked list.

Conclusion

In a doubly circular linked list, we can start from anywhere as there is no fixed head and no fixed tail. In the above approach, we have a "head," which is a pseudo head from where we would start our search. The time complexity of the above algorithm is O(n) as a linear search.