### Introduction

Learn the most efficient way to search an element in a doubly linked list.

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we are given a Doubly Linked List, and we need to search for a node with value X in the list and return its position.

### Problem Statement Understanding:

Letâ€™s try to understand the problem statement with the help of an example.

If the given doubly linked list is head â†” 4 â†” 5 â†” 7 â†” 6 â†” 2 â†” 1 â†” 9 and X = 7.

- According to the problem statement, we will have to search for the node with value X in the list, and finally, after finding the node, we have to return its position in the list.
- We can clearly see that node with value 7 is present in the list, and this node is at 3
^{rd}position (considering one based indexing) in the list. - So finally, we will output 3, as 3 is the position of a node with value X = 7 in the given list.

**Input:** head â†” 4 â†” 5 â†” 7 â†” 6 â†” 2 â†” 1 â†” 9, X(element to be searched) = 7

**Output:** 3

Also, there can be multiple nodes with value X in the list, so that’s why we will return the position of the first node with value X in the list.

**Note:** If there is no node with the value of X in the list, the output will be -1.

Now I think the problem statement is clear, so letâ€™s see how we can approach it.

Letâ€™s move to the approach section.

### Approach

In order to find an element **X** in the given doubly linked list:

- We need to traverse the list until either the node is null or we have found the node with value
**X**which we were searching for. - Also, we need a variable
**position**that will keep the count of the elements we have visited so far. - Then finally, we will return the location of the element
**X**in our list which will be given by the variable**position**.

### Algorithm

- First, we need to create a variable
**position**that will keep track of number of nodes traversed. - Then using a pointer, say,
**temp**, we will traverse the given list till the next node of the**temp**is null, or we found the element we were searching for. - Then we will check if the current node’s data is equal to the element we were searching for or not.
- If
**temp.data == X**, our**position**variable will give the location of the element to be searched for and we will output it. - Else, it means that there is no node with value
**X**in the given list, so we will output**-1**.

- If

### Dry Run

### Code Implementation

#include<stdio.h> #include<stdlib.h> // Structure of a node of // the doubly linked list struct Node { int data; struct Node* next; struct Node* prev; }; // Function to insert a node at the // beginning of the Doubly Linked List void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head_ref); if ((*head_ref) != NULL) { (*head_ref)->prev = new_node; } (*head_ref) = new_node; } // Function to find the position of // an integer in doubly linked list int search(struct Node** head_ref, int x) { struct Node* temp = *head_ref; int pos = 0; while (temp->data != x && temp->next != NULL) { pos++; temp = temp->next; } if (temp->data != x) return -1; return (pos + 1); } int main() { struct Node* head = NULL; int X = 8; // Create the doubly linked list // 18 <-> 15 <-> 8 <-> 9 <-> 14 push(&head, 14); push(&head, 9); push(&head, 8); push(&head, 15); push(&head, 18); printf("%d ",search(&head, X)); return 0; }

#include <bits stdc++.h=""> using namespace std; struct DLLNode { int data; DLLNode* next; DLLNode* prev; }; void push(DLLNode** head, int new_data){ DLLNode* new_node = (DLLNode*)malloc(sizeof(struct DLLNode)); new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head); if ((*head) != NULL) { (*head)->prev = new_node; } (*head) = new_node; } int search_the_element(DLLNode** head, int X){ DLLNode* temp = *head; int position = 0; while (temp->data != X && temp->next != NULL) { position++; temp = temp->next; } if (temp->data != X) return -1; return (position + 1); } int main() { DLLNode* head = NULL; int X = 7; push(&head, 9); push(&head, 1); push(&head, 2); push(&head, 6); push(&head, 7); push(&head, 5); push(&head, 4); cout<<search_the_element(&head, x) return=0;

public class Prepbytes { static class Node { int data; Node next; Node prev; }; static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.prev = null; new_node.next = head_ref; if (head_ref != null) { head_ref.prev = new_node; } head_ref = new_node; return head_ref; } static int search(Node head_ref, int x) { Node temp = head_ref; int position = 1; while (temp.data != x && temp.next != null) { position++; temp = temp.next; } if (temp.data != x) return -1; return position; } public static void main(String[] args) { Node head = null; int X = 7; head = push(head, 9); head = push(head, 1); head = push(head, 2); head = push(head, 6); head = push(head, 7); head = push(head, 5); head = push(head, 4); System.out.print(search(head, X)); } }

class Node: def __init__(self): self.data = 0 self.next = None self.prev = None def push(head_ref, new_data): new_Node = Node() new_Node.data = new_data new_Node.prev = None new_Node.next = head_ref if (head_ref != None): head_ref.prev = new_Node head_ref = new_Node return head_ref def search(head_ref, x): temp = head_ref position = 0 while (temp.data != x and temp.next != None): position+=1 temp = temp.next if (temp.data != x): return -1 return (position + 1) if __name__ == '__main__': head = None X = 7 head = push(head, 9) head = push(head, 1) head = push(head, 2) head = push(head, 6) head = push(head, 7) head = push(head, 5) head = push(head, 4) print(search(head, X))

#### Output

3

**Time Complexity:** O(n), where n is the total number of nodes in the Doubly Linked List.

[forminator_quiz id=”4722″]

So, in this blog, we have tried to explain how you can search a value in a doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.