1.5.4 Searching for List Elements1.5.3 Inserting List Elements1.5 Dynamic Data Structures1.5.5 Deleting List Elements

1.5.4 Searching for List Elements

Suppose we are looking for the first node of a list that holds a particular key value (for instance for retrieving other data stored in the node or for updating these data). The only possibility to find the node is to follow the chain of node links starting with head; the search stops when the node is found or when we reach the null reference. Thus we develop the following method:

  // ---------------------------------------------------------
  // node = search(value)
  // 'node' is the result of searching 'value' in 'this' list
  //
  // Output:
  //   all nodes referenced via 'this' remain unchanged.
  //   if 'node == null', then 'value' does not occur in 'this'
  //   if 'node != null', then 'node.value == value' and 'node'
  //     is the first node in 'this' for which this holds.
  // ---------------------------------------------------------
  Node search(int value)
  {
    Node node = head;
    while (node != null && node.value != value)
      node = node.next;
    return node;
  }

The local variable node holds a reference to the currently investigated node. Please note that it is not correct to exchange the conditions in the loop to

  while (node.value != value && node != null)
    node = node.next;

since we first have to know that node is not null before we are allowed to refer to the object field value (short-circuited evaluation of &&). After termination of the loop, we know that node either is null or holds value. We can therefore just return the current value of node to the caller.

Since the loop structure in this program nicely matches the pattern of the for-loop, one may express the method also as 

  Node search(int value)
  {
    for (Node node = head; node != null; node = node.next)
      if (node.value == value) return node;
    return null;
  }

In this way, searching for elements in a list closely resembles searching for elements in an unsorted array.


© Wolfgang Schreiner; February 3, 2005

1.5.4 Searching for List Elements1.5.3 Inserting List Elements1.5 Dynamic Data Structures1.5.5 Deleting List Elements