We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Search a specific node in Doubly Linked List
Last updated:
Searching a specific node in a doubly linked list involves traversing through the list while checking each node's value. If the target value is found, we can return the node; otherwise, continue until the end of the list is reached, indicating that the node is not present.
In this tutorial, we will understand how to search for a specific node in a doubly linked list with a given Java program.
Java program to find a node in a doubly linked list
Class: Node
Node.java
public class Node {
int data; // Data stored in the node
Node prev; // Reference to the next node in the list
Node next; // Reference to the previous node in the list
// Constructor to initialize a new node with data
Node(int new_data) {
data = new_data;
prev = null;
next = null;
}
}
Class: SearchElementInDLL
SearchElementInDLL.java
// Java Program to search a node in a Doubly Linked List
public class SearchElementInDLL {
static Node head;
// Method to insert a node in doubly linked list
static void insertNode(int data) {
Node newNode = new Node(data);
Node last = head;
if (head == null) {
head = newNode;
return;
}
while (last.next != null) {
last = last.next;
}
last.next = newNode;
newNode.prev = last;
}
// Method to find the position of an integer
static void search(int search_element) {
Node tempNode = head;
int pos = 0;
// Traverse the doubly linked list
while (tempNode != null && tempNode.data != search_element) {
pos++;
tempNode = tempNode.next;
}
// If the search element is not found in the list
if (tempNode == null || tempNode.data != search_element) {
System.out.println("Element: " + search_element + " is not found.");
return;
}
// If the search element is found in the list
System.out.println("Element: " + search_element + "
is found at the position: " + (pos + 1));
}
// Method to print a list
static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create a doubly linked list
insertNode(10);
insertNode(20);
insertNode(30);
insertNode(40);
insertNode(50);
System.out.print("Doubly linked list:");
printList(head);
// Searching element 40
search(40);
// Searching element 400
search(400);
}
}
Output
Doubly linked list:10 20 30 40 50
Element: 40 is found at the position: 4
Element: 400 is not found.
Frequently Asked Questions (FAQ)
Q1. How do you search for a value in a doubly linked list?
SearchValue.java
static int indexOf(Node head, int value) {
int index = 0;
for (Node current = head; current != null; current = current.next) {
if (current.data == value) {
return index;
}
index++;
}
return -1; // not found
}
The search is O(n) in the worst case.
Q2. Can searching from both ends make it faster?
You can check from the head and the tail at the same time, which finds values near either end faster. The worst case is still O(n), because about half the list may be checked from each side:
SearchBothEnds.java
static boolean contains(Node head, Node tail, int value) {
Node left = head, right = tail;
while (left != null && right != null) {
if (left.data == value || right.data == value) {
return true;
}
if (left == right || left.next == right) {
break; // the pointers met
}
left = left.next;
right = right.prev;
}
return false;
}
Q3. Can you use binary search on a sorted doubly linked list?
Not efficiently. Finding the middle node still requires walking through the list, so each step costs O(n). For fast searching on sorted data, use an array with binary search or a balanced binary search tree.
Q4. Write a Java method that returns the node holding a value.
FindNode.java
static Node find(Node head, int value) {
Node current = head;
while (current != null && current.data != value) {
current = current.next;
}
return current; // null if not found
}
Returning the node is useful because you can then delete or insert around it in O(1).
Q5. Write a recursive search method for a doubly linked list.
SearchRecursive.java
static boolean contains(Node node, int value) {
if (node == null) {
return false;
}
if (node.data == value) {
return true;
}
return contains(node.next, value);
}
Q6. How do you find the last occurrence of a value?
Search backward from the tail; the first match is the last occurrence:
LastOccurrence.java
static Node findLast(Node tail, int value) {
for (Node current = tail; current != null; current = current.prev) {
if (current.data == value) {
return current;
}
}
return null;
}
Q7. How do you count how many times a value appears?
CountOccurrences.java
static int countOccurrences(Node head, int value) {
int count = 0;
for (Node current = head; current != null; current = current.next) {
if (current.data == value) {
count++;
}
}
return count;
}
Q8. What is the best and worst case of searching?
The best case is O(1), when the value is in the first node checked. The worst case is O(n), when the value is in the last node or not present at all.
Q9. How can you make lookups in a linked list O(1)?
Keep a HashMap from each key to its node, as an LRU cache does. The map finds the node in O(1), and the doubly linked list lets you remove or move that node in O(1). The cost is extra memory for the map.
Q10. What should a search method return when the list is empty?
It should handle head == null without errors and return the "not found" result, such as -1, false or null. The loop condition current != null already covers this case.