Searching a Linked List

(The following discussion uses data names defined elsewhere.)

The following COBOL code searches a linked list to find the name associated with a specified telephone number SEARCH-WTN: 

     SET CURR-P                        TO FIRST-P.
*
     IF CURR-P NOT = NULL
        SET ADDRESS OF TN-NODE         TO CURR-P
        PERFORM UNTIL CURR-P = NULL
        OR TN-WTN = SEARCH-WTN 
           SET CURR-P                  TO TN-NEXT-P
           IF CURR-P NOT = NULL
              SET ADDRESS OF TN-NODE   TO CURR-P
           END-IF 
        END-PERFORM.
*
     IF CURR-P = NULL
        DISPLAY 'NAME NOT FOUND'
     ELSE
        DISPLAY 'NAME IS: ' TN-NAME.
We are careful never to dereference CURR-P if it is NULL. If the list is initially empty, then CURR-P is already NULL, and the loop never executes at all.

In the following diagrams, the asterisk marks the node we're looking for. If the list already has one or more nodes in it, then CURR-P starts out pointing to the first node:

[first node]

In each pass through the loop, we hop to another node. Eventually we either find the node we're looking for...

[found]

...or we don't, and we fall off the end:

[not found]

Either way, the loop stops, thanks to the UNTIL clause. The search is successful if CURR-P is not NULL.

This procedure is similar to the traversal of the entire list, except that this traversal is only partial if the search is successful. As with a full traversal, a corrupted list may lead to an infinite loop. Similar precautions apply.

A search of a linked list is broadly similar to a conventional search of an array using the COBOL SEARCH verb. However, with linked lists there is no way to do a binary search (as in a COBOL SEARCH ALL). If you need to search efficiently through a large number of items, consider a skip list or an ordered tree instead of a linked list.

[home]COBOL Home [crane]Data Structures