Searching in a Linked List

What Is Searching in a Linked List?

Linked list searching is the process of checking the nodes of a linked list to find a particular value or determine whether an element exists. Because linked lists do not provide direct access to an element by index, searching normally requires moving from one node to the next until the required value is found or the end of the list is reached.

For a singly linked list, searching begins at the head and follows the next reference of each node.

How Linked List Search Works

Consider the following linked list:

10 → 20 → 30 → 40 → null

To search for 30, start from the head and compare each node's data with the target:

Check 10 → no match
Check 20 → no match
Check 30 → match found

Once the target is found, the search can stop immediately. If traversal reaches null without finding the value, the value does not exist in the list.

Basic Linked List Search

A simple search function keeps a reference to the current node and moves it forward until either the target is found or the list ends.

function search(head, target) {
  let current = head;

  while (current !== null) {
    if (current.data === target) {
      return true;
    }

    current = current.next;
  }

  return false;
}

This function returns true when the value exists and false when the entire list has been checked without finding it.

Searching for a Value

Searching by value is the most common linked list search operation. The target value is compared with the data stored in each node.

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

const first = new Node(10);
const second = new Node(20);
const third = new Node(30);

first.next = second;
second.next = third;

function contains(head, target) {
  let current = head;

  while (current !== null) {
    if (current.data === target) {
      return true;
    }

    current = current.next;
  }

  return false;
}

console.log(contains(first, 20)); // true
console.log(contains(first, 50)); // false

Returning the Matching Node

Sometimes returning true or false is not enough. An algorithm may need the actual node containing the target value so that another operation can be performed using that node.

function findNode(head, target) {
  let current = head;

  while (current !== null) {
    if (current.data === target) {
      return current;
    }

    current = current.next;
  }

  return null;
}

Returning the node can be useful when implementing operations such as insertion after a particular node or checking relationships between nodes.

Finding the Position of a Value

Another common requirement is finding the index or position of a value instead of returning the node itself. An index counter can be incremented during traversal.

function findPosition(head, target) {
  let current = head;
  let position = 0;

  while (current !== null) {
    if (current.data === target) {
      return position;
    }

    current = current.next;
    position++;
  }

  return -1;
}

Returning -1 is a common convention for indicating that the target was not found.

Searching for Duplicate Values

A linked list can contain the same value more than once. A basic search usually returns the first matching occurrence because traversal stops as soon as the target is found.

10 → 20 → 30 → 20 → 40 → null

Searching for 20 returns the node at the first occurrence. If every matching position is required, traversal must continue after finding a match.

function findAllPositions(head, target) {
  const positions = [];
  let current = head;
  let position = 0;

  while (current !== null) {
    if (current.data === target) {
      positions.push(position);
    }

    current = current.next;
    position++;
  }

  return positions;
}

console.log(findAllPositions(head, 20));

Searching an Empty Linked List

An empty linked list has no nodes, so its head is null. A correctly written search should handle this case without attempting to access node properties.

function search(head, target) {
  let current = head;

  while (current !== null) {
    if (current.data === target) {
      return true;
    }

    current = current.next;
  }

  return false;
}

console.log(search(null, 10)); // false

The loop does not execute when head is null, so the function safely returns false.

Searching in a Sorted Linked List

A sorted linked list can sometimes allow the search to stop early. For example, if the values are stored in ascending order and the current value becomes greater than the target, the target cannot appear later in the list.

10 → 20 → 30 → 40 → 50 → null

When searching for 25, the search can stop after reaching 30. There is no need to inspect 40 or 50.

function searchSorted(head, target) {
  let current = head;

  while (current !== null) {
    if (current.data === target) {
      return true;
    }

    if (current.data > target) {
      return false;
    }

    current = current.next;
  }

  return false;
}

The worst-case complexity is still O(n). Sorting does not give a linked list the constant-time random access required for ordinary binary search.

Searching with a Recursive Approach

Linked list search can also be expressed recursively. Each recursive call checks the current node and then searches the remainder of the list.

function searchRecursive(node, target) {
  if (node === null) {
    return false;
  }

  if (node.data === target) {
    return true;
  }

  return searchRecursive(node.next, target);
}

The recursive version is concise, but it uses call-stack space proportional to the number of nodes visited. An iterative approach is usually preferable when the list can be large.

Searching Objects Stored in a Linked List

Linked list nodes do not have to contain primitive values. They can store objects such as users, products, tasks, or orders. In that case, the search condition can inspect one of the object's properties.

function findUser(head, userId) {
  let current = head;

  while (current !== null) {
    if (current.data.id === userId) {
      return current.data;
    }

    current = current.next;
  }

  return null;
}

This pattern is useful when a linked list represents application data rather than simple numeric values.

Complete Linked List Search Implementation

The following example provides multiple search operations using a reusable linked list class.

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  insert(data) {
    const newNode = new Node(data);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.size++;
  }

  contains(target) {
    let current = this.head;

    while (current !== null) {
      if (current.data === target) {
        return true;
      }

      current = current.next;
    }

    return false;
  }

  findNode(target) {
    let current = this.head;

    while (current !== null) {
      if (current.data === target) {
        return current;
      }

      current = current.next;
    }

    return null;
  }

  findPosition(target) {
    let current = this.head;
    let position = 0;

    while (current !== null) {
      if (current.data === target) {
        return position;
      }

      current = current.next;
      position++;
    }

    return -1;
  }

  print() {
    const values = [];
    let current = this.head;

    while (current !== null) {
      values.push(current.data);
      current = current.next;
    }

    console.log(values.join(' → '));
  }
}

const list = new LinkedList();

list.insert(10);
list.insert(20);
list.insert(30);
list.insert(40);

console.log(list.contains(30));       // true
console.log(list.contains(50));       // false
console.log(list.findPosition(30));   // 2
console.log(list.findNode(40).data);   // 40

Linked List Search Complexity

Here, n represents the number of nodes and k represents the number of matching values returned by a search that collects all occurrences.

Why Linked List Search Is O(n)

A linked list does not normally store nodes in a way that allows direct access by position. To reach the node at position i, the algorithm must follow the chain of references from the head.

head
 ↓
10 → 20 → 30 → 40 → 50 → null
     ↓
  visit each node

In the worst case, the target is the final node or does not exist at all. Therefore, almost every node may need to be inspected, resulting in O(n) time.

Linked List Search vs Array Search

Both arrays and linked lists can use linear search, but arrays also provide direct indexing. This makes some access patterns more convenient with arrays.

Common Linked List Search Mistakes

• Starting the search from the wrong node instead of the head.
• Forgetting to move current to current.next inside the loop.
• Accessing current.data after current has become null.
• Returning true without stopping at the correct match.
• Assuming a sorted linked list supports efficient binary search.
• Failing to define what should be returned when the target is not found.
• Not deciding whether duplicate values should return the first match or every match.

A Reliable Search Pattern

Most linked list search problems can be solved with the same basic traversal pattern: start at the head, inspect the current node, move forward, and stop when the target is found or the list ends.

let current = head;

while (current !== null) {
  // Check current node

  current = current.next;
}

The condition inside the loop can then be adapted depending on the problem. You may compare a value, inspect an object property, track a position, count matches, or perform another operation when a condition is satisfied.

Linked List Search in Interviews

Linked list search is a fundamental interview problem because it tests whether you understand sequential traversal and node references. Interview questions may ask you to search for a value, return its position, find the first or last occurrence, search a sorted list, or combine searching with insertion and deletion.

When solving these problems, identify what the function should return, determine whether duplicate values matter, and consider the empty-list case before writing the traversal.

Key Takeaways

• Linked list search normally starts at the head and follows next references.
• A basic search checks each node until the target is found or the list ends.
• Searching by value has O(n) worst-case time complexity.
• A search can return a boolean, matching node, position, or collection of matches.
• Duplicate values require deciding whether to return the first match or all matches.
• Sorted linked lists can sometimes stop early, but standard binary search is not efficient.
• Iterative traversal uses O(1) additional space.