# Search an element in a Doubly Linked List

### 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 3rd 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.

### Dry Run ### Code Implementation

```#include
using namespace std;

struct DLLNode {
int data;
DLLNode* next;
DLLNode* prev;
};

DLLNode* new_node = (DLLNode*)malloc(sizeof(struct DLLNode));

new_node->data = new_data;
new_node->prev = NULL;

}

}

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()
{
int X = 7;
cout<

```
```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;

}
}

static int search(Node head_ref, int x) {

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) {
int X = 7;