Contents  Introduction  Getting Started  The Linked List  Node Design  Node Allocation  Node Insertion  - Unsorted  Linked List  Traversal  Searching  Node Deletion  End of File  Source code  Printable version  Adobe PDF version     The Series  Linked Lists

Searching

Searching a linked list is very much like the traversal algorithm just described. The only real difference is that as you go to each node in the list, you compare the data in the node to the "key" data that you are searching for. In this example, I will show you the algorithm using an entire node record as the "key", but keep in mind that this is not the only way to accomplish the search. I leave the other avenues of exploration to you.

First, let's see how to search the linked list visually by looking at Figure 1.5.

As you can see, searching is in fact almost the same as traversing the list. In the code, the only real difference is an extra conditional statement for comparing the key node data with the current node's data that will force the traversal loop to exit should the statement be true. Take a look at the function Find, which returns a pointer to a node. If Find returns NULL, then no matches were found.

Keep in mind that this is a linear search, and that the linear search tends to be slow. This is the only way we can search this particular data structure because of the nature of the links. You can do more advanced searches on linked lists by adding more links and changing the nature of the linked list overall. We will get into that in a later article. In the meantime, here's the Find code:

node_t *Find(node_t *head, node_t keyRecord)
{
  node_t *current;
  bool found;

  current = head;
  found = false;

  while ((current != NULL) && (!found))
  {
    if (current->id == keyRecord.id)
      found = true;
    else
      current = current->next;
  }

  return current;
}

Next : Node Deletion