Deleting a linked list
using an iterative procedure

     I use linked lists frequently and it is neccesary to dispose of them to avoid writing a program that leaks memory. Previously I posted code to delete a linked list recursively but this is the wrong solution for a linear data structure such as a linked list (trees should be deleted recursively but an interative procedure is the right solution for a linked list). The code below crawls along the linked list, beginning from the head, and uses a temp var to hold the value of the 'next link' of the current node in the list. This is required because disposing of the node would also get rid of the pointer to the next element on the linked list. By crawling along the list and storing the nextlink pointer before destroying each node, the list can be destroyed iteratively without piling up recursive function calls, something undesirable in a long linked list, and which can actually crash a computer (a well balanced binary tree could destroy millions of items with less than a dozen recursive calls stacked up at any one time while a linked list would pile up millions of recursive calls and crash the computer). Destroying the list iteratively solves this problem. The code assumes that a permanent head exists and concludes by setting the next link pointer of the head to nil. (For more discussion of linked lists follow the link to the index and the pages on linked lists...)

procedure DeleteLinkedList;
var h, tmp :link;
begin
    h := head^.nextlink;
    if h <> nil then begin
      repeat
            tmp := h^.nextlink;
            Dispose(h);
            h := tmp;
      until h = nil;
    end;
    head^.nextlink := nil;
end;