Note that the correct way to dispose of linear structure like a linked list is to use an interative procedure, not recursion (which would be the correct way to dispose of a tree, not a linear list.

The previous section demonstrated using a linked list to implement a LIFO stack, and in this section a generic method for destoying a linked list using the dispose procedure will be demonstrated, using a recursive procedural call.

You can download the source as a text file by clicking here -> linked_list_dispose_recursive.txt

You can imagine how a LIFO stack might be used to implement an undo function in a program (last in first off).  A program might also have a function to 'Discard all changes' (in otherwords we would clear the undo list) and in this case we would want to destroy a LIFO stack.

we will create a procedure and call it DestroyLIFOStack and pass it the head pointer pointing to the first item on the bottom of the stack.  When the procedure returns we will remember to set head equal to nil.

DestroyLIFOStack(head);

head:=nil;

The destruction of a linked list of any kind lends itself well to the use of a recursive procedural call.  A recursive call is a call by a function of procedure to itself, rather than to another function or procedure.  If a function called 'ADDit' calls itself (ADDit) it is making a recursive call, and you can think of these calls as piling up on a stack.

The last item in a linked list should be pointing to nil.  The second last item on a linked list would then be pointing to the last item which is pointing to nothing.  If we go down into a linked list until we reach the second last item we have a pointer then pointing to a record which is itself pointing to nothing.  When we call dispose we do not dispose of a pointer, but rather we dispose of whatever the pointer was pointing towards, in this example a record with an integer and a pointer to the next record.  This two field record will be destroyed when we call dispose.

Now if we find the second last record in a linked list we can then call dispose and destroy the last record which, like the '12' record above, is pointing to nil.  We could then move backwards to the third last record, and destroy the second last record, and keep moving backwards until we reach the first record, pointed to by head, destroy that record, set head to nil and we are done disposing of the linked list.

When you make a call to a function or procedure when the call returns computer code always continues on the next line of code.  For example in the following example if we call the procedure ADDit when the call returns execution begins again on the next line (i:=i+1).

Addit;

i:=i+1;

The following procedure for destroying a linked list makes use of this principle by making recursive calls to itself until it finds the pointer pointing to the last record which is a record pointing to nothing.  At this point the if statement does not execute (a record with a null pointer was found) and the code skips down to the dispose statement, and disposes of this last record, and then executes the procedure.  However this was a recursive procedure so all of the stacked up calls then begin to return one by one.  IN effect we have crawled downt he list stacking up procedural calls to the procedure itself.  Now each one of these stacked up calls must return, and we begin to fall back down the list again.  Each time the procedural call returns it falls down to the line with the dispose statement.  So we climbed the list in the first line of code, stacking up recursive calls, and now as they return we will fall back down the list, disposing of each record on the way until we reach the bottom, dispose of the first record, return from the procedure to the initial call at which time we must point head to nil, and the linked list has been destroyed.

The code for destroying the linked list looks like this (in this case we will be destroying our LIFOStack but the principle holds for all linked lists).

procedure TForm1.DestroyLIFOStack(apointer:link);

begin

If apointer^.nextlink<>nil then DestroyLIFOStack(apointer^.nextlink);

dispose(apointer);

end;

The first line of code states that if the nextlink of the record pointed to by apointer is not a null pointer then make a recursive call to the procedure passing  the nextlink pointed to by apointer (which it is established is not a null pointer).  Here we begin to climb up the list looking for the second last record.  Let us suppose we find the second last record (for the record pointed to by the next link on the record being pointed to is null) then we do not make another recursive procedure call but rather drop down to the next line of code, and destroy the last record.  It is then that the recursive (stacked up) procedure calls begin to return one.  The second last record destroyed the last record and exited the function (after being called by the third last record).  Now the third last record returns and drops down to the dispose line and destroys the second last record.  It was in turn called by the fourth last record, which now destroys the third last and so on down the line, until the record pointed to by the head pointer (the first item on the linked list is destroyed.  The procedure finally exits, and we remember to set the head to nil.

We can diagram this using a linked list with four items, as follows.  The key is simply whatever value is being stored in the record (or multiple values, whatever the case might be).  

          (call next)

head ­> | key | next | ­>  (call next)

                                    | key | next | ­>  (dispose next)

                                                          | key | next | ­> | key | next | ­>nil

                          (dispose next)

                          | key | next | ­> | key | next |

        (dispose next)

        | key | next | ­> | key | next |

(dispose)

head ­> | key | next |

return from procedure

set head to nil

Related pages:

Inserting, sorting, and disposing of elements on linked list

Implementing a LIFO stack using a linked list

Using an array to index and quickly search large linked lists - using the divide and conquer strategy that people use when looking up things in phone books. Even very large lists can be quickly searched using this type of strategy.