Deleting an Entire Linked List

(The following discussion uses data names and procedure names defined elsewhere.)

The following COBOL code deletes an entire list: 

 
     PERFORM UNTIL FIRST-P = NULL
        SET DEAD-P             TO FIRST-P
        SET ADDRESS OF TN-NODE TO DEAD-P
        SET FIRST-P            TO TN-NEXT-P
        SET TN-NEXT-P          TO NULL
        PERFORM 9100-FREE-TN
     END-PERFORM.
*
     SET LAST-P                TO NULL.
We start by pointing DEAD-P at the head of the list:

[point to head]

Next we redirect FIRST-P to the second node:

[point to 2nd node]

Next we disconnect the first node by pointing it to NULL;

[point first node to NULL]

Now we can deallocate what used to be the first node. We had to wait until we had redirected FIRST-P. If we had deallocated the node first, we wouldn't be able to find the second node, because our only pointer to it would be in a deallocated node -- and hence inaccessible.

(In some systems you can get away with such a blunder, but it's a bad habit to get into.)

[deallocate node]

If there was only one node in the list, then FIRST-P is now NULL, and the UNTIL clause breaks the loop. Otherwise we start over, pointing DEAD-P at what is now the first node:

[start over]

...and so forth.

If we maintain a pointer to the last node (as in the example), we must remember to nullify it. In fact we could have nullified it at the outset, since we didn't otherwise use it.

Using a free list

If you maintain a free list, you don't have to deallocate each node separately. Just transfer the entire list to the free list.

If you maintain pointers to the last node of your lists, this operation is highly efficient: all you do is swap a few pointers, no matter how long the list is. Even if you must traverse a list to find the end, such a traversal is faster than repeatedly detaching nodes from one list and attaching them to another.

[home]COBOL Home [crane]Data Structures