Search for a value in Linked List

Linked lists are made up of a sequence of nodes where each node links to the next one, forming a chain-like structure. Searching for a value in a linked list involves visiting each node in the list in sequence, access its value and checking if it is equal to the desired value. We continue doing this until reaching the end of the list or until we find the desired node.

Algorithm

Start at the head (first node) of the linked list.
Compare the value of the current node with the target value you are searching for.
If the values match, the search is successful, and you have found the target value.
If the values do not match, move to the next node in the list by following the reference (pointer) to the next node.
Repeat steps 2-4 until either the target value is found or the end of the list is reached (the next pointer is null).
If the target value is not found after reaching the end of the list, the search is unsuccessful.

The time complexity of this search algorithm is O(N), where N is the number of nodes in the linked list. This is because, in the worst case, you may need to traverse the entire list to find the target value or reach the end of the list.

Code

Below is the code to iterate through all nodes in a linked list while printing the values in order.


# Node class to store a item/value and link to the next node
class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

# Function to create a sample linked list with 4 nodes
def make_linked_list():
  # Create the nodes first before linking them
  node1 = Node(1)
  node2 = Node(2)
  node3 = Node(3)
  node4 = Node(4)
  
  # Let us now link/chain the nodes in order
  # to form a linked list
  node1.next = node2
  node2.next = node3
  node3.next = node4
  node4.next = None

  # First node is the head node of the linked list
  head = node1
  return head

# Function to search for a value in given linked list
# Returns the node with search value if search succeeds
# Otherwise returns None
def search_value(head_node, value):
  cur_node = head_node
  # Iterate through all nodes until we reach tail node
  while cur_node != None:
    if cur_node.value == value:
      print("Found a matching node for value:", value)
      return cur_node
    cur_node = cur_node.next
  
  # Return None if we did not find a matching element
  print("Couldn't find a matching node for value:", value)
  return None

# Let's now test the search function
head_node = make_linked_list()
node = search_value(head_node, 2)
node = search_value(head_node, 19)


#include <stdio.h>
#include <stdlib.h>

// Node struct to store a item/value and link to the next node
typedef struct Node {
  int value;
  struct Node* next;
} Node;

// Function to create a new node
Node* create_node(int value) {
  Node* new_node = (Node*)malloc(sizeof(Node));
  new_node->value = value;
  new_node->next = NULL;
  return new_node;
}

// Function to create a sample linked list with 4 nodes
Node* make_linked_list() {
  // Create the nodes first before linking them
  Node* node1 = create_node(1);
  Node* node2 = create_node(2);
  Node* node3 = create_node(3);
  Node* node4 = create_node(4);
  
  // Let us now link/chain the nodes in order to form a linked list
  node1->next = node2;
  node2->next = node3;
  node3->next = node4;
  node4->next = NULL;

  // First node is the head node of the linked list
  return node1;
}

// Function to search for a value in given linked list
// Returns the node with search value if search succeeds
// Otherwise returns NULL
Node* search_value(Node* head_node, int value) {
  Node* cur_node = head_node;
  // Iterate through all nodes until we reach tail node
  while (cur_node != NULL) {
    if (cur_node->value == value) {
      printf("Found a matching node for value: %d\n", value);
      return cur_node;
    }
    cur_node = cur_node->next;
  }
  
  // Return NULL if we did not find a matching element
  printf("Couldn't find a matching node for value: %d\n", value);
  return NULL;
}

int main() {
  // Let's now test the search function
  Node* head_node = make_linked_list();
  Node* node = search_value(head_node, 2);
  node = search_value(head_node, 19);
  // TODO: clean up all the nodes
  return 0;
}


#include <iostream>
#include <memory>

// Node class to store a item/value and link to the next node
class Node {
public:
  int value;
  std::unique_ptr<Node> next;

  Node(int val) : value(val), next(nullptr) {}
};

// Function to create a sample linked list with 4 nodes
std::unique_ptr<Node> make_linked_list() {
  // Create the nodes first before linking them
  auto node1 = std::make_unique<Node>(1);
  auto node2 = std::make_unique<Node>(2);
  auto node3 = std::make_unique<Node>(3);
  auto node4 = std::make_unique<Node>(4);

  // Let us now link/chain the nodes in order
  // to form a linked list
  node1->next = std::move(node2);
  node2->next = std::move(node3);
  node3->next = std::move(node4);

  // First node is the head node of the linked list
  return node1;
}

// Function to search for a value in given linked list
// Returns the node with search value if search succeeds
// Otherwise returns nullptr
Node* search_value(std::unique_ptr<Node>& head_node, int value) {
  Node* cur_node = head_node.get();
  // Iterate through all nodes until we reach tail node
  while (cur_node != nullptr) {
    if (cur_node->value == value) {
      std::cout << "Found a matching node for value: " << value << std::endl;
      return cur_node;
    }
    cur_node = cur_node->next.get();
  }

  // Return nullptr if we did not find a matching element
  std::cout << "Couldn't find a matching node for value: " << value << std::endl;
  return nullptr;
}

int main() {
  auto head_node = make_linked_list();
  Node* node = search_value(head_node, 2);
  node = search_value(head_node, 19);
  return 0;
}


// Node class to store a item/value and link to the next node
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// Function to create a sample linked list with 4 nodes
function makeLinkedList() {
  // Create the nodes first before linking them
  const node1 = new Node(1);
  const node2 = new Node(2);
  const node3 = new Node(3);
  const node4 = new Node(4);

  // Let us now link/chain the nodes in order
  // to form a linked list
  node1.next = node2;
  node2.next = node3;
  node3.next = node4;
  node4.next = null;

  // First node is the head node of the linked list
  const head = node1;
  return head;
}

// Function to search for a value in given linked list
// Returns the node with search value if search succeeds
// Otherwise returns null
function searchValue(headNode, value) {
  let currentNode = headNode;
  // Iterate through all nodes until we reach tail node
  while (currentNode !== null) {
    if (currentNode.value === value) {
      console.log("Found a matching node for value:", value);
      return currentNode;
    }
    currentNode = currentNode.next;
  }

  // Return null if we did not find a matching element
  console.log("Couldn't find a matching node for value:", value);
  return null;
}

// Let's now test the search function
const headNode = makeLinkedList();
searchValue(headNode, 2);
searchValue(headNode, 19);


public class Main {

  // Node class to store a item/value and link to the next node
  static class Node {
    int value;
    Node next;

    Node(int value) {
      this.value = value;
      this.next = null;
    }
  }

  // Function to create a sample linked list with 4 nodes
  static Node makeLinkedList() {
    // Create the nodes first before linking them
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);

    // Let us now link/chain the nodes in order
    // to form a linked list
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = null;

    // First node is the head node of the linked list
    return node1;
  }

  // Function to search for a value in given linked list
  // Returns the node with search value if search succeeds
  // Otherwise returns null
  static Node searchValue(Node headNode, int value) {
    Node currentNode = headNode;
    // Iterate through all nodes until we reach tail node
    while (currentNode != null) {
      if (currentNode.value == value) {
        System.out.println("Found a matching node for value: " + value);
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    // Return null if we did not find a matching element
    System.out.println("Couldn't find a matching node for value: " + value);
    return null;
  }

  public static void main(String[] args) {
    // Let's now test the search function
    Node headNode = makeLinkedList();
    Node node = searchValue(headNode, 2);
    node = searchValue(headNode, 19);
  }
}