Search a in Doubly Linked List

Q: How do you search for a value in a doubly linked list?

The search is O(n) in the worst case. Java example: 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 }

Q: Write a recursive search method for a doubly linked list.

Java example: static boolean contains(Node node, int value) { if (node == null) { return false; } if (node.data == value) { return true; } return contains(node.next, value); }

Q: How do you count how many times a value appears?

Java example: 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; }

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

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

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

Search a specific node in Doubly Linked List

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.

Was this tutorial helpful?

Help Us Improve

Search a specific node in Doubly Linked List

Java program to find a node in a doubly linked list

Class: Node

Class: SearchElementInDLL

Frequently Asked Questions (FAQ)