Search for a Value in Linked List in DSA Java

Mental Model

We look at each item in the list one by one until we find the value or reach the end.

Analogy: Like flipping through pages of a book to find a specific word, checking each page in order.

head -> [1] -> [2] -> [3] -> null
           ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3, search for value 2

Goal: Find if value 2 exists in the list and return true if found, false otherwise.

Step 1: Check first node value

head -> [1↑] -> 2 -> 3 -> null

Why: Start at the first node to see if it matches the value

Step 2: Move to next node and check value

head -> 1 -> [2↑] -> 3 -> null

Why: First node was not 2, so check the next node

Step 3: Found value 2, stop search

head -> 1 -> [2↑] -> 3 -> null

Why: Value matches the search target, so we can stop

Result:

head -> 1 -> [2↑] -> 3 -> null
Found: true

Annotated Code

DSA Java

public class LinkedListSearch {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public static boolean search(Node head, int target) {
        Node current = head;
        while (current != null) {
            if (current.data == target) {
                return true; // found the target
            }
            current = current.next; // move to next node
        }
        return false; // target not found
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        int target = 2;
        boolean found = search(head, target);
        System.out.println("Found: " + found);
    }
}

Node current = head;

Start searching from the first node

while (current != null) {

Keep checking nodes until the end of the list

if (current.data == target) {

Check if current node has the target value

return true; // found the target

Stop search and return true when found

current = current.next; // move to next node

Advance to the next node to continue search

return false; // target not found

Return false if we reach the end without finding target

Output

Found: true

Complexity Analysis

Time: O(n) because we may need to check each node once until we find the value or reach the end

Space: O(1) because we only use a few variables regardless of list size

vs Alternative: Compared to arrays, linked list search is similar in time but slower than hash-based search which is O(1)

Edge Cases

Empty list (head is null)

Returns false immediately because there are no nodes to check

DSA Java

while (current != null) {

Value is at the first node

Returns true immediately without checking further nodes

DSA Java

if (current.data == target) {

Value not present in the list

Checks all nodes and returns false at the end

DSA Java

return false; // target not found

When to Use This Pattern

When you need to find if a value exists in a linked list, use linear search by checking nodes one by one because linked lists do not support direct access.

Common Mistakes

Mistake: Not moving to the next node inside the loop, causing an infinite loop
Fix: Add 'current = current.next;' inside the while loop to advance the pointer

Mistake: Checking for null after accessing current.data, causing null pointer error
Fix: Check 'current != null' before accessing 'current.data' in the loop condition

Summary

Searches each node in the linked list to find a target value.

Use when you need to check if a value exists in a linked list.

Remember to move through nodes one by one until you find the value or reach the end.

Practice

1. What is the main purpose of searching for a value in a linked list?

easy

A. To add a new node at the end

B. To delete the first node

C. To find if the value exists in the list

D. To reverse the linked list

Solution

1. Step 1: Understand the search operation

   Searching means checking each node to see if it contains the target value.

2. Step 2: Identify the goal of searching

   The goal is to find whether the value is present or not in the linked list.

3. Final Answer:

   To find if the value exists in the list -> Option C

4. Quick Check:

   Search means find value presence = To find if the value exists in the list [OK]

Hint: Search means check nodes for value presence [OK]

Common Mistakes:

• Confusing search with insertion or deletion
• Thinking search changes the list
• Assuming search reverses the list

2. Which of the following is the correct way to start traversing a linked list in Java to search for a value target?

easy

A. Node current = head; while(current != null) { if(current.data == target) break; current = current.next; }

B. Node current = null; while(current != head) { if(current.data == target) break; current = current.next; }

C. Node current = head; while(current.next != null) { if(current.data == target) break; current = current.next; }

D. Node current = head.next; while(current != null) { if(current.data == target) break; current = current.next; }

Solution

1. Step 1: Initialize traversal from head node

   Traversal must start from the head node to check all nodes including the first.

2. Step 2: Loop until current is null

   Loop continues while current is not null to cover all nodes.

3. Final Answer:

   Node current = head; while(current != null) { if(current.data == target) break; current = current.next; } -> Option A

4. Quick Check:

   Start at head and loop till null = Node current = head; while(current != null) { if(current.data == target) break; current = current.next; } [OK]

Hint: Start at head; loop while node not null [OK]

Common Mistakes:

• Starting traversal from null or head.next
• Looping until current.next is null misses last node
• Using wrong loop condition causing errors

3. What will be the output of the following code snippet if the linked list contains nodes with values 3 -> 5 -> 7 -> null and we search for value 5?

Node current = head;
boolean found = false;
while(current != null) {
  if(current.data == 5) {
    found = true;
    break;
  }
  current = current.next;
}
System.out.println(found);

medium

A. false

B. null

C. Compilation error

D. true

Solution

1. Step 1: Traverse nodes checking for value 5

   Nodes checked in order: 3 (no), 5 (yes), loop breaks and found = true.

2. Step 2: Print the found variable

   Since value 5 is found, found is true, so output is true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Value 5 found = true [OK]

Hint: If value found, print true; else false [OK]

Common Mistakes:

• Assuming output is node data instead of boolean
• Thinking loop misses the value 5
• Confusing true/false output

4. Identify the error in the following code that searches for a value in a linked list:

Node current = head;
while(current.next != null) {
  if(current.data == target) {
    System.out.println("Found");
    break;
  }
  current = current.next;
}

medium

A. It causes a null pointer exception

B. It misses checking the last node

C. It never breaks the loop

D. It prints "Found" multiple times

Solution

1. Step 1: Analyze loop condition

   The loop runs while current.next != null, so it stops before the last node.

2. Step 2: Check if last node is checked

   Since last node's next is null, last node is never checked for target value.

3. Final Answer:

   It misses checking the last node -> Option B

4. Quick Check:

   Loop condition excludes last node = misses last node check [OK]

Hint: Loop till current != null to check all nodes [OK]

Common Mistakes:

• Using current.next != null instead of current != null
• Assuming last node is checked
• Ignoring possibility of missing target at last node

5. Given a singly linked list where each node contains an integer, write a method to return the index (0-based) of the first occurrence of a target value. If the value is not found, return -1. Which approach correctly implements this search?

hard

A. Traverse from head, increment index each step, return index if found, else -1 after loop

B. Traverse from head, return node data if found, else return null

C. Traverse from tail backwards, return index if found, else 0

D. Traverse from head, increment index only when value matches, return index or -1

Solution

1. Step 1: Traverse from head with index counter

   Start at head, keep an index starting at 0, check each node's data.

2. Step 2: Return index if value matches, else -1 after full traversal

   If node data equals target, return current index; if not found after loop, return -1.

3. Final Answer:

   Traverse from head, increment index each step, return index if found, else -1 after loop -> Option A

4. Quick Check:

   Index search = traverse + count + return index or -1 [OK]

Hint: Count nodes from head; return index on match, else -1 [OK]

Common Mistakes:

• Returning node data instead of index
• Traversing from tail in singly linked list (not possible)
• Incrementing index only on match causing wrong count