Posted on by Kalkicode

# 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 two-pointer 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):
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

1. We start with two pointers, `frontPointer` initialized to the head of the list and `rearPointer` initialized to the tail of the list.
2. We iterate while both pointers are not null.
3. In each iteration, we compare the values of the nodes pointed to by `frontPointer` and `rearPointer` with the given key.
• If either value matches the key, we return `true` as the key exists in the list.
4. We then check whether the `frontPointer` and `rearPointer` 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`.
5. If none of the above conditions are met, we move the `frontPointer` to the next node and the `rearPointer` to the previous node.
6. We repeat steps 3-5 until one of the terminating conditions is met.
7. 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.

## 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 two-pointer 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.

## Comment

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.

Categories
Relative Post