Posted on by Kalkicode
Code Doubly linked list

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):
    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

  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.

Program Solution

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.

New Comment