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<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.

Leave a Reply

Your email address will not be published. Required fields are marked *