Check if given key is exist in doubly linked list
The given problem revolves around a doubly linked list data structure, focusing on finding whether a given key exists within the list or not. A doubly linked list is a data structure composed of nodes, where each node contains a value and pointers to both its previous and next nodes. The goal is to efficiently determine whether a specific key is present in the list.
Problem Statement
In this problem, we are provided with a Java code implementation of a doubly linked list, along with a function
named searchKey(int key)
which aims to determine if a given key exists within the linked list.
Example
Let's go through a detailed example to understand the problem and solution better.
Suppose we have the following doubly linked list:
Linked List: 8 <> 2 <> 23 <> 4 <> 7 <> 3 <> 9
Idea to Solve the Problem
To solve this problem, we can use a twopointer approach. We maintain two pointers, one starting from the head of the list and moving forward, and another starting from the tail of the list and moving backward. We compare the values of the nodes pointed to by these pointers with the given key. If the key matches any of the node values, we conclude that the key exists in the list. If the two pointers meet or cross each other, we conclude that we have searched the entire list and the key doesn't exist.
Pseudocode
function searchKey(key):
frontPointer = head
rearPointer = tail
while frontPointer is not null and rearPointer is not null:
if frontPointer.data == key or rearPointer.data == key:
return true
if frontPointer == rearPointer or frontPointer.next == rearPointer:
return false
frontPointer = frontPointer.next
rearPointer = rearPointer.prev
return false
Algorithm Explanation
 We start with two pointers,
frontPointer
initialized to the head of the list andrearPointer
initialized to the tail of the list.  We iterate while both pointers are not null.
 In each iteration, we compare the values of the nodes pointed to by
frontPointer
andrearPointer
with the given key. If either value matches the key, we return
true
as the key exists in the list.
 If either value matches the key, we return
 We then check whether the
frontPointer
andrearPointer
have met each other or are adjacent to each other. If they meet or are adjacent, we conclude that we have searched the entire list and the key doesn't
exist, so we return
false
.
 If they meet or are adjacent, we conclude that we have searched the entire list and the key doesn't
exist, so we return
 If none of the above conditions are met, we move the
frontPointer
to the next node and therearPointer
to the previous node.  We repeat steps 35 until one of the terminating conditions is met.
 If we reach the end of the loop without finding a match, we return
false
indicating that the key is not present in the list.
Program Solution

1) Search an element in doubly linked list in java
2) Search an element in doubly linked list in c++
3) Search an element in doubly linked list in c
4) Search an element in doubly linked list in c#
5) Search an element in doubly linked list in php
6) Search an element in doubly linked list in python
7) Search an element in doubly linked list in ruby
8) Search an element in doubly linked list in scala
9) Search an element in doubly linked list in swift
10) Search an element in doubly linked list in kotlin
11) Search an element in doubly linked list in node js
12) Search an element in doubly linked list in golang
13) Search an element in doubly linked list in vb.net
14) Search an element in doubly linked list in typescript
Time Complexity
The time complexity of the search operation depends on the position of the key in the linked list. In the worst
case, we will iterate through the entire list once. The twopointer approach ensures that each node is checked at
most twice (once with the frontPointer
and once with the rearPointer
), leading to a linear
time complexity of O(n), where n is the number of nodes in the linked list.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment