Splitting a Linked List

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 splits a linked list (referenced by FIRST-P and LAST-P) into two lists, beginning with the node to which CURR-P points. The latter portion of the original list will be referenced by ALT-FIRST-P and ALT-LAST-P. 

 
     IF CURR-P = NULL
     OR FIRST-P = NULL
        SET ALT-FIRST-P       TO NULL
        SET ALT-LAST-P        TO NULL
     ELSE
        SET ALT-FIRST-P       TO CURR-P
        SET ALT-LAST-P        TO LAST-P
        IF FIRST-P = ALT-FIRST-P
           SET FIRST-P        TO NULL
           SET LAST-P         TO NULL
        ELSE
           PERFORM 9200-FIND-PREV-NODE
           SET CURR-P         TO NULL
           IF PREV-P = NULL
              DISPLAY 'ERROR!  BEGINNING NODE IS NOT ON THE ORIGINAL LIST'
              SET ALT-FIRST-P TO NULL
              SET ALT-LAST-P  TO NULL
           ELSE
              SET LAST-P      TO PREV-P
              SET ADDRESS OF TN-NODE TO LAST-P
              SET TN-NEXT-P   TO NULL
              SET PREV-P      TO NULL.
If the original list is empty, or if CURR-P is NULL, then we force the new list to be empty. Otherwise the initial situation might look like this:

[initial state]

We already know where the ends of the new list will be, so we assign values to ALT-FIRST-P and ALT-LAST-P:

[point to new ends]

If the head of the new list is also the head of the original list, then we are transferring all the nodes to the new list, so we make the original list empty. Otherwise we perform 9200-FIND-PREV-NODE, which searches the list to find the previous node.

[find previous node]

Note the (rather primitive) error handling when PREV-P is NULL. In this case the beginning of the new list doesn't even belong to the original list. Usually we should treat this situation as a fatal error, because it indicates a major flaw somewhere else in the code.

Having found the previous node, we have no further use for CURR-P, so we nullify it (and ignore it from now on). Now we redirect LAST-P to that previous node, which becomes the last node of the first list:

[redirect LAST-P]

Finally we point that node to NULL. We no longer need PREV-P, so we nullify it as well. Now the two lists are cleanly separated:

[finished]

[home]COBOL Home [crane]Data Structures