Concatenating Linked Lists in COBOL

Concatenating Linked Lists

The following discussion uses data names and procedure names defined elsewhere. In addition we use two additional pointer variables, ALT-FIRST-P and ALT-LAST-P.

The following COBOL code appends a second list (referenced by ALT-FIRST-P and ALT-LAST-P) to the first list (referenced by FIRST-P and LAST-P):

 
     IF LAST-P = NULL 
        SET FIRST-P            TO ALT-FIRST-P 
     ELSE 
        SET ADDRESS OF TN-NODE TO LAST-P
        SET TN-NEXT-P          TO ALT-FIRST-P.
*
     SET ALT-FIRST-P           TO NULL.
     SET LAST-P                TO ALT-LAST-P.
     SET ALT-LAST-P            TO NULL.

If the first list is empty, we can simply transfer ALT-FIRST-P to FIRST-P and ALT-LAST-P to LAST-P. Otherwise the initial situation looks like this:

[initial state]

First we attach the second list to the tail of the first list:

[connect lists]

We no longer need ALT-FIRST-P, so we nullify it:

[nullify ALT-FIRST-P]

Now we redirect LAST-P to the last node of the second list, since that is the last node of the combined list:

[redirect LAST-P]

We no longer need ALT-LAST-P, so we nullify it:

[finished]

Now all the nodes are in the first list, and the second list is empty.

Caveat

For the sake of simplicity, we have ignored certain dangers:

What if ALT-FIRST-P is already equal to FIRST-P? We would concatenate the list to itself, accidentally creating a circular list.

What if ALT-FIRST-P points to a node in the middle of the first list, or to the last node? We would concatenate the list to a piece of itself, creating a bizarre lariat-shaped list.

What if either list is already corrupt in some way? Let your imagination run riot.

At one extreme you can just assume that the requested operations are sensible. At the other extreme you can try to validate everything before you do anything.

Ideally your own code will build and maintain both lists. If so, just make sure you maintain the lists correctly. Otherwise you may need to be more paranoid.

Sometimes it is useful to include error-checking code for testing and development, when your data structures are most vulnerable to bugs. For production use you can comment it out, as long as the rest of the code doesn't depend on the presence of the error-checking code. This strategy resembles the use of the assert() macro in C.

COBOL Home

Data Structures [trap]

Pointer Traps