Programmer 7500/MAX_PROGRAMMERS.iso/PASCAL/LINKTU.ZIP/LTUT2.PAS

Pascal/Delphi Source File | 1993-01-04 | 31.5 KB | 775 lines

{
                      FUNCTIONS AND PROCEDURES
                     FOR CREATING AND ACCESSING
                      LINKED LISTS IN HEAPSPACE

                     GARRY J. VASS  [72307,3311]


This file is a stand-alone TPascal program that attempts to provide
a step-by-step demo of the creation and management of a linked list
in heapspace.  Comments, revisions, corrections, questions, and
suggestions should be passed on to my SIG at the POLICE STATION BSS
(201-866-7902).



INTRODUCTION
------------

  Why bother with linked lists?  Why not just stick everything in an
   array and keep track it that way?  Link lists are undoubtedly one
   of the most arcane things Turbo has to offer; consider the problems
   in learning linked lists:

               1.  The variables do not really have names in any
                   familar context;
               2.  Lists involve odd notation;
               3.  Lists reside in an unfamilar place, heapspace.
               4.  Lists need pointer variables, and those look
                   cumbersome.
               5.  Lists require odd procedures like GETMEM, NEW,
                   and MEMAVAIL.
               6.  The TURBO documentation on this subject seems
                   vague and inconsistent.  It does not provide
                   an adequate conceptual foundation.

    On the other hand, consider some of the advantages of lists:

               1.  The total data area available to your application
                   is limited only by the amount of RAM available
                   when your program starts.  With arrays, your
                   application is limited by the size of the
                   data segment.
               2.  The sort time is reduced to that required for a
                   single pass of the data (no nested FOR constructs,
                   or bubble sorts, etc).
               3.  List members can be deleted much more easily than
                   array elements.  Imagine trying to delete the
                   70th element of an array with 300 plus elements.
               4.  The device drivers, memory control blocks, etc.,
                   used by DOS are chained together using linked list-like
                   constructs and are easier to understand and process
                   in a linked list context.


    So, on balance, lists have a useful place in any programmer's
    bag of trick,s and, with an equitable foundation, they are actually
    quite simple.

    A pointer, for example, is roughly analogous to an array index.  It
    has a value in its own right, but actually refers to an address
    (or offset) in memory of what is really needed.  An array index,
    however, contains only a part of what is needed to access the
    data (we rely upon the compiler to fill in the segment and base
    address of the array).  A pointer variable contains a full
    absolute address (segment and offset) in two words.  A pointer
    is declared in a way that seems to violate Turbo's syntax rules in
    that a reference is made to something not yet declared.  For example,

                      TYPE
                          LIST_POINTER = ^LISTREC;
                          (... more type declarations ...)
                      VAR
                          MYPOINTER : LIST_POINTER;

     When the compiler reaches this statement, it trusts that something
     called LISTREC will be defined in the next statement.  The english
     translation for this example is "Variables of type LIST_POINTER
     will contain two word, segment/offset addresses corresponding
     to the locations of variables of the type LISTREC.  Variables
     of the type LISTREC will not reside in the data segment like
     static variables.  Rather, they will reside in heapspace.  MYPOINTER
     is a variable that can contain any segment/offset address, but will
     contain the address of a specific member of a list (of type LISTREC)."

    To get the next element in an array, we usually just add one to the
    index.  To get the next element in a linked list, we need to know
    its address.  To accomplish this then, each member of a linked list
    must have some address information, namely the address of the
    next member.  For this reason, a RECORD structure is frequently used
    to define list members, such as:

                 TYPE
                     ANYSTRING    =  STRING[255];
                     LIST_POINTER = ^LISTREC;
                     LISTREC = RECORD
                                     POINTER_TO_NEXT_MEMBER: LIST_POINTER;
                                     MEMBER_DATA           : ANYSTRING;
                               END;
                 VAR
                    MYPOINTER : LIST_POINTER;
                    ROOT      : LIST_POINTER;
                    LIST      : LISTREC;

    This translates into, "each member of my linked list will occupy
    260 bytes of memory:

              POINTER_TO_NEXT_MEMBER      4 bytes
              MEMBER_DATA
                  (Turbo's length byte)   1 byte
                  (String part)         255 bytes

    Further, each member will reside in contiguous heapspace, and each
    member will contain the address of the next member.  The variable,
    ROOT, will be used to hold the address of the first member added to
    the list ('list entry point').  With the value of ROOT, the first
    list member can be accessed.  Once the first record is accessed, the
    pointer to the next record can be obtained.  When that record is
    obtained, the pointer to the third record can be found, and so on".

    ROOT, then, corresponds roughly to the first element of an array.
    To learn the last element in an array, we frequently use a counter
    in a context like "FOR I := 1 TO NAME_COUNT DO ...".  In linked
    lists, the last member is signified by all zeros in the
    POINTER_TO_NEXT_MEMBER element.  Turbo uses a pre-defined constant
    called, "NIL" for this.  Using the above example, compare these
    constructs:

      last element of array               last member of a list

      I := I + 1;                         MYPOINTER := MYPOINTER^.POINTER_TO_NEXT_MEMBER;
      IF I = NAME_COUNT THEN              IF MYPOINTER = NIL THEN
         BEGIN                               BEGIN
             (last element is reached)           (last member is reached)

    The translation for the statements on the right is "MYPOINTER is currently
    pointing to a list member.  Take the value of the POINTER_TO_NEXT_MEMBER element
    from this record and put it in MYPOINTER.  If this is NIL, then..."

    With these concepts, we can now transverse a linked list in a line-by-line
    analogy to array processing:

        array logic                            linked list logic

        I := 1;                                MYPOINTER := ROOT;
        REPEAT                                 REPEAT
            WRITELN(NAMES[I]);                      WRITELN(MYPOINTER^.MEMBER_DATA);
            I := SUCC(I);                           MYPOINTER := MYPOINTER^.POINTER TO NEXT MEMBER;
        UNTIL I > NAME_COUNT;                  UNTIL MYPOINTER = NIL;

    To add an element/member:

        array logic                   linked list logic

  NAME_COUNT := SUCC(NAME_COUNT);     NEW(MYPOINTER);
  NAMES[NAME_COUNT] := 'Mr. Kahn';    MYPOINTER^.MEMBER_DATA := 'Mr. Kahn';
                                      MYPOINTER^.POINTER_TO_NEXT_MEMBER := NIL;
                                      (logic for setting pointer
                                       in previous record goes here).

  Beyond these examples, the analogies tend to break down.  The logic for
  sorting an array tends to involve a physical rearrangement of the data
  through an iterative process.  A linked list is usually sorted as
  it is created by reassigning the pointers.  The upper bound of an
  array is bound to a constant.  The capacity of a list is tied to
  available heapspace.

  To maximize the value of this program, I suggest that it be run
  in its native form (i.e., as you found it - which is hopefully
  not altered) several times and observe the dynamics/interaction
  of the generic routines.  Then copy this program into your own
  file and modify the list building routines to create various
  situations, such as a stack/heap collisions, duplicate records,
  multiple lists, different sort key types, and so on.  It is also
  important to note that several particularly elegant uses of
  pointer variables that are not list related can be found on "GO BOR"
  (try MAPMEM.PAS by TurboPower for a flagship example).

TREATMENT
---------

   The linked list used here is composed of three elements.  The first
   is an index (or sort key).  The values in this element determine
   how the list is to be sorted.  I have used an integer type here,
   but this element can just as easily be redefined as a string type.
   In addition to being the sort key for the list, the index element
   is also used as a search argument in the lookup function.  The
   next element is the so-called "data part", which contains all the
   relevant information associated with the index value.  Naturally, this
   element can also be redefined to meet specific applications.  The last
   element is a pointer variable that can hold one of two values:

           1.  the NIL value, a special value indicating that
               this record is the last item in the list.  NIL
               is represented internally by four zero filled
               bytes; or
           2.  a pointer to the location of the next item in the
               list.  These four bytes are represented internally
               (as are all pointers) as:

                      -  low order offset;
                      -  high order offset;
                      -  low order segment;
                      -  high order segment;

               It is IMPORTANT to note that the physical location
               of a pointer or list member has NOTHING to do with
               its sorted (or logical) location in the list.

               Physical addresses are assigned at the next available
               heapspace location in the order that you ask for them.
               This means that the root record (or logical entry point)
               of a list could be located at a higher physical address than
               any of the other members in the same list.

   Most of the procedures and functions given below deal with the
   assignment of these pointers.  Filling the index and data parts
   is up to you.  To build a list of names and ages
   with age as the index, for example, the following code could be
   used:
              list.index_part := 28;   (* age *)
              list.data_part  := 'Sally Maxwell';
              add_member(list);
              list.index_part := 27;   (* age *)
              list.data_part  := 'Jane Robinson';
              add_member(list);
              etc, etc, etc....

   The add_member procedure finds the appropriate place in the
   list, plugs your record there, and figures out to modify the
   pointers.

   Once the list has been constucted, several things can be
   done:

         1.  Look up a member of the list based upon the
             the index value (procedure lookup_member).
         2.  Delete a member of the list based upon
             the index value (procedure delete_member).
         3.  Process the entire list in sorted order
             (procedure process_list).
         4.  Dispose of the entire list (procedure dispose_list).

  When reading through linked list code, one encounters odd notation
  such as the carat, ^.  I use the following translations:


      P^              That which is pointed to by P.
      P^ := X         That which is pointed to by P is X.
      P^.A            The A element of the record pointed
                      to by P.
      P^ := P^.M^     P now points to same thing as the M pointer
                      element of the record being pointed to by P.
      NEW(W)          Create a new record in heapspace.  Assignments
                      for the record elements to go in this area will
                      soon follow, and will be issued in the form...

                               W^.INDEX :=
                               W^.DATA  :=
}
PROGRAM LINKED_LISTS;
CONST
     FOREVER:BOOLEAN = FALSE;  { FOR CREATING STACK/HEAP COLLISIONS }
TYPE
    ANYSTRING = STRING[255];
    LISTPTR =  ^LISTREC;
    LISTREC =   RECORD
                      NEXT_POINTER : LISTPTR;
                      INDEX_PART   : INTEGER;
                      DATA_PART    : ANYSTRING;
                END;
VAR
{  Define a global variable to hold the root address,
   or entry point of the list.  The concept of a root
   variable means "this variable holds the logical
   entry point into the list".}
   ROOT: LISTPTR;

{  Define a global variable to enable the construction
   of the list.}
   LIST: LISTREC;

{  Extra pointer for general use }
   TEMPTR:LISTPTR;

   ANYINTEGER:INTEGER;
   ANYCH:CHAR;


{--------------------- GENERAL SUPPORT ROUTINES  ----------------------}
{ These routines are not of immediate interest and are included in compressed format.}
FUNCTION HEXBYTE(N:INTEGER):ANYSTRING;CONST H:ANYSTRING='0123456789ABCDEF';BEGIN HEXBYTE:=H[((LO(N)DIV 16)MOD 16)+1]+
H[(LO(N)MOD 16)+1];END;FUNCTION HEXWORD(N:INTEGER):ANYSTRING;BEGIN HEXWORD:=HEXBYTE(HI(N))+HEXBYTE(LO(N));END;
FUNCTION CONV(I:INTEGER):REAL;BEGIN CONV:=256.0*HI(I)+LO(I);END;PROCEDURE PAUSE;VAR CH:CHAR;BEGIN WRITELN;
WRITELN('-- PAUSING FOR KEYBOARD INPUT...');READ(KBD,CH);WRITELN;END;
{--------------------- END OF GENERAL SUPPORT ROUTINES  ----------------}


{  Linked lists reside in heapspace, an area of unused memory
   at the low end of the stack/data segment.  The beginning of
   available heapspace changes according to two factors:

              1.  how much is on the stack; and
              2.  how much heapspace has already been grabbed.

   Our friends at Borland were thoughtful enough to provide
   a pre-defined variable that points to the beginning of heapspace,
   this variable is called, "HEAPPTR", and is configured with four bytes
   just like the pointer layout described above.  You can use the
   VALUEOF(HeapPtr) function at various points in the program to
   examine Turbo's behavior in setting and assigning this rather
   ephermeral item.  Unfortunately the standard variable, StackPtr,
   as described in the documentation, is more elusive and not
   compatable with VALUEOF.

   When heapspace is requested (with the NEW procedure), the HEAPPTR
   variable will be reset to the next available location in
   memory so that it will always point to the beginning of
   available heapspace.  If enough heapspace is requested,
   this variable will ultimately be equal to, or greater than
   the stack pointer.  This situation creates a run-time
   "stack/heap collision" and the program dies.  To avoid
   this, the MEMAVAIL function should be used before the
   NEW procedure to assure that enough heapspace is available.
}

{-------------------  LINKED LIST SUPPORT  ---------------------

These routines help show what is happening as the list is being
constructed.  They are not needed for an application.
                                                                }
PROCEDURE SNAPMEM(X, Y:INTEGER);     { PUTS AVAILABLE HEAPSPACE }
BEGIN                                { AT COLUMN X, ROW Y       }
     GOTOXY(X, Y);
     CLREOL;
     WRITELN('HEAP SPACE = ',CONV(MEMAVAIL)*16.0:8:0);
END;

FUNCTION VALUEOF(P:LISTPTR):ANYSTRING;  { RETURNS A STRING IN   }
                                        { SEGMENT:OFFSET FORMAT }
                                        { WHICH CONTAINS VALUE  }
BEGIN                                   { OF A POINTER VARIABLE }
     VALUEOF := HEXBYTE(MEM[SEG(P):OFS(P) + 3]) +
                HEXBYTE(MEM[SEG(P):OFS(P) + 2]) +':'+
                HEXBYTE(MEM[SEG(P):OFS(P) + 1]) +
                HEXBYTE(MEM[SEG(P):OFS(P) + 0]);
END;

PROCEDURE GIVESTATS;   { REPORTS STATISTICS FOR DEMO PROGRAM }
BEGIN
     WRITELN('HEAP SPACE NOW BEGINS AT ',VALUEOF(HEAPPTR),
            ' AND EXTENDS FOR ',CONV(MEMAVAIL) * 16.0:8:0,' BYTES');
     PAUSE;
END;

PROCEDURE SNAP_MEMBER(POINTER:LISTPTR);   {  PRINTS THE LIST MEMBER }
BEGIN                                     {  BEING POINTED TO BY "POINTER"}
     IF POINTER = NIL THEN
        BEGIN
             WRITELN('-----------  EMPTY LIST  -------------');
             EXIT;
        END;
    WRITELN('---------------  LIST MEMBER INFORMATION  ------------');
    WRITELN('THE INDEX OF THIS RECORD IS ', POINTER^.INDEX_PART);
    WRITELN('THE DATA IN THIS RECORD IS  ', POINTER^.DATA_PART);
    WRITELN('MEMORY LOCATION OF THIS RECORD IS ',VALUEOF(POINTER));
    WRITELN('THIS RECORD IS POINTING TO A RECORD AT ',VALUEOF(POINTER^.NEXT_POINTER));
    PAUSE;
END;
{---------------------  END OF LINKED LIST SUPPORT  ---------------------}


{---------------------  GENERIC LINKED LIST ROUTINES  --------------------}

{  When adding a member to a linked list, four situations can occur.

   1.  The list is empty/uninitialized.
   2.  The new record must be added to a place
       before the existing root record.
   3.  The new record must be inserted somewhere
       in the middle of the list.
   4.  The new record must be inserted
       at the end of the list.

  The add_member procedure below recognizes each of these four
  situations and adjusts the list accordingly.

}

PROCEDURE ADD_MEMBER (TARGET:LISTREC);   { ADDS THE TARGET RECORD TO }
VAR                                      { LINKED LIST               }
     MOVING_POINTER          : LISTPTR;
     POINTER_TO_PRIOR_RECORD : LISTPTR;
BEGIN

     {Assure that sufficient memory is available for the target member}
     IF ((CONV(MEMAVAIL) * 16.0) < CONV(SIZEOF(TARGET))) THEN
        BEGIN
             WRITELN('---------- NO MORE MEMORY ---------------');
             EXIT;
        END;

     WRITELN;
     WRITELN('-------------  ADDING A RECORD TO THE LIST  ----------');
     WRITELN;
     WRITELN('INDEX VALUE IS ',TARGET.INDEX_PART,' DATA IS ',TARGET.DATA_PART);


{ Logic for adding the first record to a list }
     IF ROOT = NIL THEN
        BEGIN
             { Allocate some memory for the root pointer }
             NEW(ROOT);
             { Assign NIL to the last record in the list }
             TARGET.NEXT_POINTER := NIL;
             { Root points to the record in TARGET }
             ROOT^ := TARGET;
             WRITELN('THIS RECORD INITIALIZED THE LIST AT ',VALUEOF(ROOT));
             GIVESTATS;
             EXIT;
        END;


{ Logic for adding a record "in front of" the current root }
     IF (TARGET.INDEX_PART) <= (ROOT^.INDEX_PART) THEN
        BEGIN
             { Set pointer in new record to point to the root }
             TARGET.NEXT_POINTER := ROOT;
             { Allocate some memory for a new root pointer }
             NEW(ROOT);
             { Root points to the record in TARGET }
             ROOT^ := TARGET;
             WRITELN('THIS RECORD BECAME THE NEW ROOT AT    ',VALUEOF(ROOT));
             WRITELN('THIS RECORD POINTS TO THE OLD ROOT AT ',VALUEOF(ROOT^.NEXT_POINTER));
             GIVESTATS;
             EXIT;
        END;

{ Logic for adding a record to "the middle of" a list }
     MOVING_POINTER := ROOT;
     REPEAT
           POINTER_TO_PRIOR_RECORD  := MOVING_POINTER;
           MOVING_POINTER  := MOVING_POINTER^.NEXT_POINTER;
           IF (MOVING_POINTER <> NIL) THEN
               IF ((TARGET.INDEX_PART) <= (MOVING_POINTER^.INDEX_PART))
                   THEN
                        BEGIN
                             NEW(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER);
                             TARGET.NEXT_POINTER := MOVING_POINTER;
                             POINTER_TO_PRIOR_RECORD^.NEXT_POINTER^ := TARGET;
                             WRITELN('THIS RECORD WAS INSERTED INTO THE MIDDLE OF THE LIST ',
                                     'AT ',VALUEOF(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER));
                             GIVESTATS;
                             EXIT;
                        END;
     UNTIL MOVING_POINTER = NIL;

     {APPEND TO END OF LIST }
     NEW(MOVING_POINTER);
     TARGET.NEXT_POINTER := NIL;
     POINTER_TO_PRIOR_RECORD^.NEXT_POINTER := MOVING_POINTER;
     MOVING_POINTER^ := TARGET;
     WRITELN('THIS RECORD WAS ADDED TO THE END OF THE LIST AT ',VALUEOF(POINTER_TO_PRIOR_RECORD^.NEXT_POINTER));
     GIVESTATS;
END;

FUNCTION LAST_MEMBER:LISTPTR;   { RETURNS POINTER TO LAST LIST MEMBER }
VAR P:LISTPTR;
BEGIN
     P := ROOT;
     IF P = NIL THEN
        BEGIN
             LAST_MEMBER := NIL;
             EXIT;
        END;
     REPEAT
           IF P^.NEXT_POINTER <> NIL THEN P := P^.NEXT_POINTER;
     UNTIL P^.NEXT_POINTER = NIL;
     LAST_MEMBER := P;
END;

PROCEDURE ROTATE_LIST_LEFT;      { ROTATES ENTIRE LIST LEFT, ROOT BECOMES }
VAR P1:LISTPTR;                  { TAIL, TAIL BECOMES PENULTIMATE, ETC.   }
    P2:LISTPTR;
    TR:LISTPTR;
    R1:LISTREC;
BEGIN
     IF (ROOT = NIL) OR (ROOT^.NEXT_POINTER = NIL) THEN EXIT;
     R1.DATA_PART    := ROOT^.DATA_PART;
     R1.INDEX_PART   := ROOT^.INDEX_PART;
     R1.NEXT_POINTER := NIL;
     TR := ROOT^.NEXT_POINTER;
     DISPOSE(ROOT);
     ROOT := TR;
     NEW (P1);
     P1^ := R1;
     P2 := LAST_MEMBER;
     P2^.NEXT_POINTER := P1;
END;

PROCEDURE MAKE_NEW_HEAD(P:LISTPTR);  { FIXES LIST SO THAT RECORD WITH POINTER }
BEGIN                                { "P" IS THE ROOT RECORD.  ASSUMES "P"   }
     IF (ROOT = NIL) OR              { EXISTS.                                }
        (ROOT^.NEXT_POINTER = NIL) THEN EXIT;
     REPEAT
           ROTATE_LIST_LEFT;
     UNTIL ROOT = P;
END;

FUNCTION LIST_COUNT:INTEGER;     { RETURNS LIST MEMBER COUNT }
VAR
   P:LISTPTR;
   I:INTEGER;
BEGIN
     IF ROOT = NIL THEN
        BEGIN
             LIST_COUNT := 0;
             EXIT;
        END;
     I := 0;
     P := ROOT;
     REPEAT
           I := SUCC(I);
           P := P^.NEXT_POINTER;
     UNTIL P = NIL;
     LIST_COUNT := I;
END;

FUNCTION PENULTIMATE:LISTPTR;           { RETURNS PENULTIMATE LIST MEMBER  }
VAR                                     { OR NIL IF NO PENULTIMATE         }
    P1:LISTPTR;
    P2:LISTPTR;
BEGIN
     IF ROOT = NIL THEN
        BEGIN
             PENULTIMATE := NIL;
             EXIT;
        END;
     IF LIST_COUNT <= 2 THEN
        BEGIN
             PENULTIMATE := ROOT;
             EXIT;
        END;
     P1 := ROOT;
     P2 := ROOT^.NEXT_POINTER;
     REPEAT
           P1 := P2;
           P2 := P2^.NEXT_POINTER;
     UNTIL P2 = LAST_MEMBER;
     PENULTIMATE := P1;
END;

PROCEDURE KILL_MEMBER(P:LISTPTR);   { DELETES LIST MEMBER POINTED TO      }
VAR P1:LISTPTR;                     { BY "P".  EXITS IF THE LIST CONTAINS }
    P2:LISTPTR;                     { LESS THAN TWO MEMBERS.              }
BEGIN
     IF ROOT = NIL THEN EXIT;
     IF ROOT^.NEXT_POINTER = NIL THEN EXIT;
     IF P = ROOT THEN
        BEGIN
             P1 := ROOT^.NEXT_POINTER;
             DISPOSE(P);
             ROOT := P1;
             EXIT;
        END;
     IF P = LAST_MEMBER THEN
        BEGIN
             P1 := PENULTIMATE;
             DISPOSE(P);
             P1^.NEXT_POINTER := NIL;
             EXIT;
       END;
     P1 := ROOT;
     REPEAT
           P2 := P1;
           IF P1^.NEXT_POINTER <> NIL THEN P1 := P1^.NEXT_POINTER;
     UNTIL (P1 = NIL) OR
           (P1 = P);
     IF P1 = NIL THEN EXIT;
     P2^.NEXT_POINTER := P1^.NEXT_POINTER;
     DISPOSE(P1);
END;

FUNCTION LOOKUP_MEMBER(IND:INTEGER):LISTPTR;  { RETURNS THE POINTER      }
VAR                                           { CONTAINING THE RECORD    }
   MOVING_POINTER:LISTPTR;                    { WHOSE INDEX VALUE IS     }
BEGIN                                         { EQUAL TO "IND".  IF NO   }
     MOVING_POINTER := ROOT;                  { RECORD EXISTS, RETURNS   }
     REPEAT                                   { NIL.                     }
           IF MOVING_POINTER^.INDEX_PART = IND THEN
              BEGIN
                   LOOKUP_MEMBER := MOVING_POINTER;
                   EXIT;
              END;
           MOVING_POINTER := MOVING_POINTER^.NEXT_POINTER;
    UNTIL MOVING_POINTER = NIL;
    LOOKUP_MEMBER := NIL;
END;

{------------------  END OF GENERIC LIST PROCEDURES  -------------}


{---------------  PRESENTATION PROCEDURES AND ENGINE  ----------}

PROCEDURE PROCESS_LIST;                  { WALKS THROUGH THE LIST, }
                                         { FROM ROOT TO NIL.       }

{ IMPORTANT NOTE ABOUT LIST PROCESSING!!!!

       Once a list has been created you can still have a stack/heap
       collision where the stack is the culprit!  Remember that each
       call to a function or procedure moves the stack downward
       closer to your list.  For this reason, extra care must be
       taken to assure that the routines for list processing programs
       are sufficiently "shallow" (not nested too deep, not overly
       recursive, etc). }
VAR
   MOVING_POINTER:LISTPTR;
BEGIN
     CLRSCR;
     {                                       }
     { YOUR LIST PROCESSING ROUTINES GO HERE }
     {                                       }
     IF ROOT = NIL THEN
        BEGIN
             WRITELN('--------------  EMPTY LIST  -------------');
             EXIT;
        END;
     WRITELN;
     WRITELN('      ----------------  CURRENT LIST CONTENTS  -------------- ');
     WRITELN;
     WRITELN('INDEX         DATA               LOCATION OF RECORD           LOCATION OF NEXT');
     WRITELN('VALUE        VALUE                  IN MEMORY                RECORD IN MEMORY');
     WRITELN('-----  --------------------         ---------                ----------------');
     MOVING_POINTER := ROOT;
     REPEAT
          {  LIST PROCESSING CODE GOES HERE }
          WRITELN(MOVING_POINTER^.INDEX_PART:5,
                  MOVING_POINTER^.DATA_PART :20,
                  VALUEOF(MOVING_POINTER):20,
                  VALUEOF(MOVING_POINTER^.NEXT_POINTER):30);
          MOVING_POINTER := MOVING_POINTER^.NEXT_POINTER;
     UNTIL MOVING_POINTER = NIL;
     WRITELN;
     WRITELN('THE LIST COUNT IS ',LIST_COUNT);
     IF ROOT = NIL THEN WRITELN('----- EMPTY LIST ----')
                   ELSE WRITELN('THE ROOT MEMBER IS ',ROOT^.DATA_PART);
     MOVING_POINTER := PENULTIMATE;
     IF MOVING_POINTER <> NIL
        THEN WRITELN('THE PENULTIMATE MEMBER IS ',MOVING_POINTER^.DATA_PART)
        ELSE WRITELN('THERE IS NO PENULTIMATE MEMBER');
     MOVING_POINTER := LAST_MEMBER;
     WRITELN('THE LAST MEMBER IS ',MOVING_POINTER^.DATA_PART);
     PAUSE;
END;

PROCEDURE BUILD_A_LIST;
BEGIN
     {                                     }
     { YOUR LIST BUILDING LOGIC GOES HERE  }
     {                                     }
     LIST.INDEX_PART :=  25; LIST.DATA_PART  := 'George Wilson  '; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  21; LIST.DATA_PART  := 'Walter Thompson'; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  28; LIST.DATA_PART  := 'James McCoy    '; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  22; LIST.DATA_PART  := 'Robert Henton  '; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  31; LIST.DATA_PART  := 'Dennis Campbell'; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  20; LIST.DATA_PART  := 'Jack Farrell   '; ADD_MEMBER(LIST); PROCESS_LIST;
     LIST.INDEX_PART :=  24; LIST.DATA_PART  := 'Herbert Walker '; ADD_MEMBER(LIST); PROCESS_LIST;
END;

{-----------------  BEGINNING OF MAINLINE  ------------------------}
{------------------------  DEMO  ----------------------------------}
BEGIN
     CLRSCR;
     WRITELN('PROGRAM IS LOADED AT ',HEXWORD(CSEG));
     WRITELN('DATA SEGMENT IS AT ',HEXWORD(DSEG));
     WRITELN('STACK SEGMENT IS AT ',HEXWORD(SSEG));
     WRITELN('HEAP SPACE BEGINS AT ',VALUEOF(HEAPPTR),
             ' AND EXTENDS FOR ',    CONV(MEMAVAIL) * 16.0:8:0,
             ' BYTES');
     WRITELN('LINKED LIST RECORD SIZE IS ',SIZEOF(LIST),' BYTES');
     PAUSE;
     ROOT := NIL;

     WRITELN('BEGIN BUILDING A LINKED LIST');
     PAUSE;
     BUILD_A_LIST;

     REPEAT
           WRITELN('DO YOU WANT TO ROTATE THE LIST (Y/N)?');
           GOTOXY(50, WHEREY - 1);
           READ(KBD,ANYCH);
           IF UPCASE(ANYCH) = 'Y' THEN
              BEGIN
                   ROTATE_LIST_LEFT;
                   PROCESS_LIST;
              END;
     UNTIL UPCASE(ANYCH) <> 'Y';
     WRITELN;
     WRITELN('NOW SEARCH FOR LIST MEMBERS');
     PAUSE;
     REPEAT
          PROCESS_LIST;
          WRITELN('PLEASE ENTER AN AGE TO SEARCH FOR (OR ZERO TO QUIT):  ');
          GOTOXY(55, WHEREY - 1);
          READLN(ANYINTEGER);
          IF ANYINTEGER <> 0 THEN
                 BEGIN
                      WRITELN;
                      TEMPTR := LOOKUP_MEMBER(ANYINTEGER);
                      IF TEMPTR = NIL THEN
                                          BEGIN
                                               WRITELN('NO ONE OF AGE ',ANYINTEGER);
                                               PAUSE;
                                          END
                                      ELSE SNAP_MEMBER(TEMPTR);
                 END;
     UNTIL ANYINTEGER = 0;

     WRITELN('NOW DELETE LIST MEMBERS');
     PAUSE;
     REPEAT
          PROCESS_LIST;
          WRITELN('PLEASE ENTER AN AGE TO DELETE (OR ZERO TO QUIT):  ');
          GOTOXY(55, WHEREY - 1);
          READLN(ANYINTEGER);
          IF ANYINTEGER <> 0 THEN
                 BEGIN
                      WRITELN;
                      TEMPTR := LOOKUP_MEMBER(ANYINTEGER);
                      IF TEMPTR = NIL THEN
                                          BEGIN
                                               WRITELN('NO ONE OF AGE ',ANYINTEGER);
                                               PAUSE;
                                          END
                                      ELSE KILL_MEMBER(LOOKUP_MEMBER(ANYINTEGER));
                 END;
     UNTIL (ANYINTEGER = 0) OR (ROOT = NIL);
     PROCESS_LIST;
END.

{-----------------------  END OF MAINLINE  ---------------------------}

APPLICATIONS:

With no effort at all, you can use these procedures to develop an improved
DOS sort filter.  Consider the following list record:

      LISTREC = RECORD
                      INDEX_PART : ANYSTRING;  { Load this according  }
                                               { to your specs        }

                      DATA_PART  : ANYSTRING;  { Line from ASCII file }
                      NEXT_PART  : POINTER;
                END;

With the numerous directory procedures available at "GO BOR", you can
develop customized directory sort programs.  A sort by file size, for
example, might have the following records:

         DIRREC  = RECORD
                         ATTRIBUTE     : BYTE;
                         NAME          : ANYSTRING;
                         EXTENSION     : ANYSTRING;
                         DATE          : DATEREC;  { or whatever you want }
                         TIME          : TIMEREC;  { "      "     "   "   }
                         FST_CLUSTER   : INTEGER;
                   END;

         LISTREC = RECORD
                         INDEX_PART : REAL;    { Holds file size }
                         DATA_PART  : DIRREC;
                         NEXT_PART  : POINTER;
                   END;