Search elements in doubly circular linked list in C++

Given a doubly circular linked list and a keyword, we need to search the linked list for the keyword and give an appropriate message when found. Suppose we have a linked list with a specific character and we need 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 the key to find the solution to the given problem. Doubly linked lists do not have a fixed head, so we will start at any node and mark that node as the head until we encounter the head again, where we perform a linear search of the linked list and search for the keyword.

Let’s look at some input and output scenarios -

Suppose we have a two-way circular linked list, which has 5 nodes 3 4 5 6 7, we want to find The element of is 6.

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

Let us consider another situation where there is no element to search in a doubly circular linked list.

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

algorithm

The following are the steps to approach.

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

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

• Assign each previous part of the node to the next part of the node.

• Pass the key element to the key element that checks whether it exists in the doubly circular linked list.

• Returns true if the key exists in a two-way circular linked list.

• Else, it returns false.

The Chinese translation of

Example

is:

Example

The following is the C implementation code for performing a 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

The Chinese translation of

Explanation

is:

Explanation

Keyword 4 exists in the doubly linked list.

in conclusion

In a doubly circular linked list, we can start from any position because there is no fixed head and tail. In the above method, we have a "head", which is a pseudo-head, and we start our search from here. The time complexity of the above algorithm is O(n) because it is a linear search.

The above is the detailed content of Search elements in doubly circular linked list in C++. For more information, please follow other related articles on the PHP Chinese website!