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.

Example

Example

The following is the C implementation code for performing a search operation in a doubly linked list:

#include  #include  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

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!