Traversing a Linked List

(The following discussion uses data names defined elsewhere.)

The following COBOL code traverses a linked list from beginning to end, displaying the contents of each node. 

     SET CURR-P                     TO FIRST-P.
*
     PERFORM UNTIL CURR-P = NULL
        SET ADDRESS OF TN-NODE      TO CURR-P
        DISPLAY TN-WTN ' ' TN-NAME
        SET CURR-P                  TO TN-NEXT-P
     END-PERFORM.
The UNTIL clause prevents us from trying to dereference a NULL pointer. If the list is initially empty, then CURR-P is already NULL, and the loop never executes at all.

If the list already has one or more nodes in it, then CURR-P starts out pointing to the first node:

[first node]

After the first iteration of the loop, CURR-P points to the second node:

[second node]

We keep looping, and eventually CURR-P points to the last node:

[last node]

After one more iteration, CURR-P falls off the end, and is NULL.

[finished]

The loop stops.

If the linked list becomes corrupted, so that the last node points to a previous node instead of to NULL, then the traversal becomes an infinite loop.

It is not easy to detect this kind of corruption. The simplest approach is to count the nodes as you traverse them, and quit if the count ever surpasses some appropriate threshhold.

Another approach is to keep a flag in each node. As you traverse the list, set each flag. If you ever encounter a node whose flag is already set, then you have detected corruption in the list. Once you reach the end, you must traverse the list again to clear the flags.

The best approach is to not corrupt the list in the first place. All operations which change the list should operate through a small set of list-manipulation routines, each of which is correct. If you scatter your list-manipulating code all over the program, you'll probably mess it up somewhere. Or someone coming after you will.

[home]COBOL Home [structure] Data Structures