Searching in a Linked List in Java — Step by Step Explanation

In this article, we will learn how to search for an item in a linked list in Java step by step.

Searching means checking whether a particular value exists in the linked list or not.

---

What is Searching in a Linked List?

Searching in a linked list means comparing a given item with the data of each node one by one until:

• The item is found
• Or the end of the list is reached

If the item is found, its position is displayed.

If the item is not found, the search becomes unsuccessful.

---

Algorithm to Search an Item in a Linked List

1. Set ptr = START
2. Set pos = 1
3. Repeat until ptr = NULL
4. If ITEM = ptr.INFO
5. Print ITEM found at position pos
6. Exit loop
7. ptr = ptr.LINK
8. pos = pos + 1
9. If ptr = NULL
10. Print "Item not found"
11. END

Explanation

• ptr starts from the first node
• The item is compared with each node
• If matched, the position is displayed
• If not matched, move to the next node
• The process continues until the item is found or the list ends

---

Step 1: Understanding the Node Class

Each node contains:

• data — stores the value
• link — stores the address of the next node

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class TestNode {
    public static void main(String[] args) {

        Node n = new Node(10);

        System.out.println("Data: " + n.data);
        System.out.println("Link: " + n.link);
    }
}

Explanation

The node stores one value and the reference of the next node.

---

Step 2: Creating a Linked List

The linked list starts from a reference variable called start.

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    LinkedList() {
        start = null;
    }

    boolean isEmpty() {
        return start == null;
    }
}

class TestList {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        if (list.isEmpty()) {
            System.out.println("List is empty");
        }
    }
}

---

Step 3: Inserting Nodes into the Linked List

Before searching, we need some nodes in the linked list.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void display() {

        Node ptr = start;

        while (ptr != null) {
            System.out.print(ptr.data + " -> ");
            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestInsert {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.display();
    }
}

Output

10 -> 20 -> 30 -> NULL

---

Step 4: Basic Search Operation

Now let us search for an item in the linked list.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void search(int value) {

        Node ptr = start;
        int pos = 1;

        while (ptr != null) {

            if (ptr.data == value) {

                System.out.println("Item found at position " + pos);
                return;
            }

            ptr = ptr.link;
            pos++;
        }

        System.out.println("Item not found");
    }
}

class TestSearch {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.insertAtEnd(5);
        list.insertAtEnd(2);
        list.insertAtEnd(7);
        list.insertAtEnd(4);

        list.search(7);
    }
}

Output

Item found at position 3

Explanation

The pointer ptr moves from node to node and compares the value.

If the value matches, the position is displayed.

---

Step 5: Searching for an Item That Does Not Exist

If the item is not present, the search continues until the pointer becomes null.

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void search(int value) {

        Node ptr = start;
        int pos = 1;

        while (ptr != null) {

            if (ptr.data == value) {

                System.out.println("Item found at position " + pos);
                return;
            }

            ptr = ptr.link;
            pos++;
        }

        System.out.println("Item is not in the list.");
    }
}

class TestSearchNotFound {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        list.insertAtEnd(5);
        list.insertAtEnd(2);
        list.insertAtEnd(7);

        list.search(100);
    }
}

Output

Item is not in the list.

---

Step 6: Complete Search Program

This complete program creates a linked list using user input and then searches for a given number.

import java.io.*;

class Node {

    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {

    Node start;

    LinkedList() {
        start = null;
    }

    boolean isEmpty() {
        return start == null;
    }

    void insertAtEnd(int value) {

        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void traverse() {

        Node ptr = start;

        while (ptr.link != null) {

            System.out.print(ptr.data + " -> ");
            ptr = ptr.link;
        }

        System.out.println(ptr.data + " !!!!");
    }

    void search(int value) {

        Node ptr = start;
        int pos = 1;

        while (ptr != null) {

            if (ptr.data == value) {

                System.out.println("Item " + value +
                        " found at position " + pos);

                break;
            } else {

                ptr = ptr.link;
                pos++;
            }
        }

        if (ptr == null) {

            System.out.println("Item " + value +
                    " is not in the list.");
        }
    }
}

class LinkedListTest {

    public static void main(String[] args) throws IOException {

        int num;

        LinkedList list = new LinkedList();

        BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in));

        System.out.println("Starting List Test for SEARCHING");

        for (int i = 0; i < 7; i++) {

            System.out.print("Enter a number: ");

            num = Integer.parseInt(br.readLine());

            list.insertAtEnd(num);
        }

        System.out.println("\nNow the List is:");

        list.traverse();

        System.out.print("\nEnter number to be searched for: ");

        num = Integer.parseInt(br.readLine());

        list.search(num);

        System.out.println("\nList Test Over");
    }
}

Sample Output

Starting List Test for SEARCHING

Enter a number: 6
Enter a number: 3
Enter a number: 90
Enter a number: 4
Enter a number: 3
Enter a number: 35
Enter a number: 17

Now the List is:

3 -> 3 -> 4 -> 6 -> 17 -> 35 -> 90 !!!!

Enter number to be searched for: 17

Item 17 found at position 5

List Test Over

---

How Searching Works

Suppose the linked list is:

3 -> 3 -> 4 -> 6 -> 17 -> 35 -> 90

Now we search for 17.

Step	Current Node	Comparison	Result
1	3	17 == 3	No
2	3	17 == 3	No
3	4	17 == 4	No
4	6	17 == 6	No
5	17	17 == 17	Found

---

Important Concepts Used

• Traversal of linked list
• Searching node by node
• Using pointer variables
• Position counting
• Comparing node data
• Handling unsuccessful search

---

Recommended Teaching Sequence

1. Explain node structure
2. Create a linked list
3. Insert nodes into the list
4. Traverse the linked list
5. Compare item with each node
6. Track node position
7. Handle successful search
8. Handle unsuccessful search
9. Take user input and test the program

---

Key Learning

Searching in a linked list works sequentially.

Each node is visited one by one until:

• The item is found
• Or the end of the list is reached

Unlike arrays, linked lists do not support direct indexing. Therefore, searching requires traversal through nodes sequentially.