Deleting from a Linked List

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

The following COBOL code deletes the node to which CURR-P points (we should have already verified that CURR-P is not NULL): 

 
     IF CURR-P = FIRST-P
        SET ADDRESS OF TN-NODE        TO CURR-P
        SET FIRST-P                   TO TN-NEXT-P
        IF FIRST-P = NULL
           SET LAST-P TO NULL
        END-IF
     ELSE
        PERFORM 9200-FIND-PREV-NODE
        IF PREV-P = NULL
           DISPLAY 'INTERNAL ERROR! CURRENT NODE IS NOT ON THE LIST'
        ELSE
           SET ADDRESS OF ALT-TN-NODE TO PREV-P
           SET ADDRESS OF TN-NODE     TO CURR-P
           SET ALT-TN-NEXT-P          TO TN-NEXT-P
           IF CURR-P = LAST-P
              SET LAST-P              TO PREV-P.
*
     SET ADDRESS OF TN-NODE           TO CURR-P.
     SET TN-NEXT-P                    TO NULL.
     SET PREV-P                       TO NULL.
     SET DEAD-P                       TO CURR-P.
     SET CURR-P                       TO NULL.
     PERFORM 9100-FREE-TN.
The initial situation may look like this:

[before deletion]

Whatever points to the current node must be made to point to its successor instead. If the current node is the first in the list, we redirect FIRST-P. Otherwise we perform 9200-FIND-PREV-NODE, which searches the list to find the previous node. It returns a pointer to the previous node in PREV-P.

Note the (rather primitive) error-handling when PREV-P is NULL. In this case the so-called current node isn't on the list; hence we cannot delete it. In most cases we should treat this situation as a fatal error, because it indicates a major logical flaw somewhere else in the code.

If we ignore this unhappy possibility, and ignore the chance that we are deleting the first node, we have the following picture:

[found previous node]

In the example illustrated, the previous node turned out to be the first node in the list, but this fact is not important.

Next we point the previous node to the current node's successor, which becomes its successor:

[point previous to successor]

If we delete the last node in the list, we must update LAST-P to point to what becomes the last node (or to NULL, if the list becomes empty). This step is easy to forget.

Next we disconnect the node we are deleting, by pointing it to NULL:

[disconnect node]

Finally we nullify various dangling pointers. In the example code we deallocate the deleted node. In some cases we might do something else with the deleted node, such as add it to a different list.

[nullify pointers]

[home]COBOL Home [crane]Data Structures