Search Element in Doubly Linked List in Java

In this tutorial, we will learn how to write a Java program to search an element in doubly linked list.

Java Program to search an element in doubly linked list

In this program, we have a doubly linked list that contains the string elements. We are searching a specified string value in the list.

The detailed explanation is provided at the end of the program and brief explanation is provided in the program itself using comments.

//A Node represents the element in a Doubly linked list
//An element in Doubly linked list contains the pointer to
//previous as well as next element of the list
class Node {
    String data; //data of node
    Node prev; //address of previous node in list
    Node next; //address of next node in the list
    
    // Constructor of this class will be used to initialize a node
    public Node(String data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class SearchDoublyLinkedList {
    Node head; //contains the address of first element
    Node tail; //contains the address of last element

    // Constructor to initialize an empty doubly linked list
    public SearchDoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }

    // Method to add a node to the end of the doubly linked list
    public void addNode(String data) {
        Node newNode = new Node(data);
        if (head == null) {
            // If list is empty, set the new node as both head and tail
            head = tail = newNode;
        } else {
            // else, add the new node after the tail node and update tail
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // Method to search for an element in the doubly linked list
    public boolean search(String key) {
        Node current = head;
        while (current != null) {
            // If the data of the current node matches the key, return true
            if (current.data.equals(key)) {
                return true; // Element found
            }
            current = current.next;
        }
        return false; // Element not found
    }
}

public class Main {
    public static void main(String[] args) {
        //creating a doubly linked list with string elements
        SearchDoublyLinkedList dll = new SearchDoublyLinkedList();
        dll.addNode("one");
        dll.addNode("two");
        dll.addNode("three");
        dll.addNode("four");
        
        //we are going to search this element
        String searchKey = "three";
        if (dll.search(searchKey)) {
            System.out.println("Element " + searchKey + " found in the doubly linked list.");
        } else {
            System.out.println("Element " + searchKey + " not found in the doubly linked list.");
        }
    }
}

Output:

Element three found in the doubly linked list.

How this program works?

1. Node Class: It represents an element of Doubly linked list. Each node contains three fields:
   • data: Stores the value of the node, in this case, a String.
   • prev: Points to the previous node in the list.
   • next: Points to the next node in the list.
2. SearchDoublyLinkedList Class: This class represents the doubly linked list itself. It has two instance variables:
   • head: Contains the address of first element in the list.tail: Contains the address of last element in the list.
   This class also contains the following methods:
   • addNode(String data): Adds a new node with the specified data at the end of the doubly linked list.
   • search(String key): It traverses through the whole doubly linked list and searches the node with the given key value.
3. Main Class:
   • Inside the main method, we created an object of SearchDoublyLinkedList named dll.
   • Added few string elements using addNode() method.
   • We want to search an element with data "three" in the list.
   • We call search() method by passing the key "three", this method returns true if "three" is found in list, else it returns false.
4. Output:
   • Based on the result of search() method, prints the result whether the search term "three" is found in the list or not.

Related Articles:

• LinkedList in Java with Examples
• Search an element in LinkedList with example
• Insert an item in Doubly LinkedList in Java
• Adding elements at the beginning of the LinkedList