Search for a Value in Linked List in DSA Java - Build from Scratch

Search for a Value in Linked List

📖 Scenario: Imagine you have a list of your favorite books arranged one after another. You want to find if a certain book is in your list.

🎯 Goal: You will build a simple linked list of book titles and write code to search if a specific book is in the list.

📋 What You'll Learn

Create a linked list with exactly these book titles in order: "Harry Potter", "The Hobbit", "1984", "Pride and Prejudice", "To Kill a Mockingbird"

Create a variable called searchTitle and set it to "1984"

Write a method called searchLinkedList that takes the head of the linked list and the searchTitle string, and returns true if the title is found, otherwise false

Print the result of searching for searchTitle in the linked list

💡 Why This Matters

🌍 Real World

Searching in linked lists is useful in many applications like managing playlists, task lists, or any ordered collection where you want to find if an item exists.

💼 Career

Understanding linked lists and how to search them is a fundamental skill for software developers, especially when working with data structures and algorithms.

1

Create the Linked List

Create a linked list of book titles using the Node class. The list must have these titles in order: "Harry Potter", "The Hobbit", "1984", "Pride and Prejudice", "To Kill a Mockingbird". Use the Node class provided below.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        // Create the linked list nodes and link them
        // Your code here
    }
}

Hint

Start by creating the first node with "Harry Potter" and then link each next node with the next book title.

2

Set the Search Title

Create a variable called searchTitle and set it to the string "1984".

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) {
        Node head = new Node("Harry Potter");
        head.next = new Node("The Hobbit");
        head.next.next = new Node("1984");
        head.next.next.next = new Node("Pride and Prejudice");
        head.next.next.next.next = new Node("To Kill a Mockingbird");

        // Create the searchTitle variable
        // Your code here
    }
}

Hint

Use String searchTitle = "1984"; to create the variable.

3

Write the Search Method

Write a method called searchLinkedList that takes a Node called head and a String called searchTitle. The method should return true if searchTitle is found in any node's data, otherwise false. Use a while loop to check each node.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static boolean searchLinkedList(Node head, String searchTitle) {
        // Use a while loop to check each node's data
        // Your code here
    }

    public static void main(String[] args) {
        Node head = new Node("Harry Potter");
        head.next = new Node("The Hobbit");
        head.next.next = new Node("1984");
        head.next.next.next = new Node("Pride and Prejudice");
        head.next.next.next.next = new Node("To Kill a Mockingbird");

        String searchTitle = "1984";
    }
}

Hint

Use a while loop to move through the list. Check if current.data.equals(searchTitle). Return true if found, else return false after the loop.

4

Print the Search Result

In the main method, call searchLinkedList(head, searchTitle) and print the result using System.out.println.

DSA Java

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
        this.next = null;
    }
}

public class Main {
    public static boolean searchLinkedList(Node head, String searchTitle) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(searchTitle)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public static void main(String[] args) {
        Node head = new Node("Harry Potter");
        head.next = new Node("The Hobbit");
        head.next.next = new Node("1984");
        head.next.next.next = new Node("Pride and Prejudice");
        head.next.next.next.next = new Node("To Kill a Mockingbird");

        String searchTitle = "1984";
        // Print the search result
        // Your code here
    }
}

Hint

Use System.out.println(searchLinkedList(head, searchTitle)); to print the result.

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