14.7 Tricks of the Trade: Debugging Programs with Linked Lists

The three most common errors in writing programs using dyamic structures are dereferencing a null pointer, infinite loops and infinite recursion, and off-by-one problems.

Dereferencing a Null Pointer

When processing linked data structures, make sure that the pointer to the next node is not NULL. If pointer P has the value NULL, the record P.ALL is undefined. Therefore, the condition

    ( P.ALL.ID /= 9999) AND ( P /= NULL)

will cause Constraint_Error to be raised when P is NULL. You can prevent this by writing the expression using the short-circuit operator AND THEN:

    ( P /= NULL) AND THEN ( P.ALL.ID /= 9999)

This causes the left side to be evaluated first and evaluates the right side only if the left side is True.

Infinite Loops and Infinite Recursion

A linked list program can get into an infinte loop in two ways. First, if you write a WHILE loop and forget to write an incrementation step, the loop has no way to progress toward completion. In this case, the program will either appear to "hang" or possibly will display the same value over and over.

Second, your program could get stuck in an infinite loop or infinite recursion while creating a dynamic data structure. If this happens, it is quite possible that the program will keep allocating new blocks and consume all the memory cells in the storage pool. If this happens, Storage_Error is raised. For both of these reasons, be especially careful in writing the WHILE condition and the loop incrementation statement. Be certain the loop is always initialized properly and incremented each time through. Also be careful that your recursive programs will eventually reach a stopping case.

Off-by-One Errors

Off-by-one errors are common in linked list programs. In traversing a list with K elements, for example, sometimes only the first K-1 elements or the last K-1 are displayed. These logic errors will not raise exceptions but will give incorrect results. They are usually caused by careless loop initialization or termination conditions. Note that a program that tries to go one step too far will generally "fall off the end of the list," causing Constraint_Error to be raised upon dereferencing a null pointer.

Some debugging tools allow you to display the value of a pointer variable, but such a value cannot normally be displayed with Text_IO procedures. It is therefore difficult to debug programs that manipulate pointers. You will have to trace the execution of such a program by printing an information field that uniquely identifies the list element being processed instead of the pointer value itself. In doing a trace, drawing a picture of the list as it is built and manipulated is enormously helpful.

When writing driver programs, it is often helpful to create a sample linked structure using the technique shown in Figure 14.1. The data and pointer fields of the structure can be defined using assignment statements.