home *** CD-ROM | disk | FTP | other *** search
/ Collection of Hack-Phreak Scene Programs / cleanhpvac.zip / cleanhpvac / PASCTXT.ZIP / CHAP12.TXT < prev    next >
Text File  |  1988-01-15  |  31KB  |  719 lines

  1.  
  2.               CHAPTER 12 - Pointers and Dynamic Allocation
  3.  
  4.  
  5.              For  certain  types of programs, pointers  and  dynamic
  6.         allocation can be a tremendous advantage, but many  programs
  7.         do not need such a high degree of data structure.  For  that
  8.         reason,  it would probably be to your advantage  to  lightly
  9.         skim over these topics and come back to them later when  you
  10.         have  a substantial base of Pascal  programming  experience.
  11.         It would be good to at least skim over this material  rather
  12.         than  completely neglecting it, so you will have an idea  of
  13.         how  pointers and dynamic allocation work and that they  are
  14.         available for your use when needed.
  15.  
  16.              A complete understanding of this material will  require
  17.         deep  concentration  as  it  is  complex  and  not  at   all
  18.         intuitive.   Nevertheless, if you pay close  attention,  you
  19.         will have a good grasp of pointers and dynamic allocation in
  20.         a short time.
  21.  
  22.                 WHAT ARE POINTERS, AND WHAT GOOD ARE THEY?
  23.  
  24.              Examine the program named POINT for your first  example
  25.         of  a  program using pointers.  In the var  declaration  you
  26.         will  see  two variables named Where and Who that  have  the
  27.         symbol ^ in front of their types.  This defines them, not as
  28.         variables,  but as pointers to integer type  variables.   In
  29.         line  12 of the program, the variable Index is assigned  the
  30.         value of 17 for purposes of illustration.  The pointer named
  31.         Where  is  then assigned the address of the  variable  Index
  32.         which  means  that it does not contain the value of  17,  it
  33.         contains  the  address  of the storage  location  where  the
  34.         variable  Index  is stored.  In like manner, we  assign  the
  35.         address  of  Index to the pointer named Who.  It  should  be
  36.         obvious  to  you that Addr is a TURBO Pascal  function  that
  37.         returns the address of its argument.
  38.  
  39.                         HOW DO WE USE THE POINTERS?
  40.  
  41.              It  should  be clear to you that we now have  a  single
  42.         variable  named Index with two pointers pointing at it.   If
  43.         the  pointers are useful, we should be able to do  something
  44.         with  them  now, so we simply print out  the  same  variable
  45.         three different ways in line 15.  When we write "Where^", we
  46.         are  telling  the system that we are not interested  in  the
  47.         pointer itself but instead we are interested in the data  to
  48.         which   the  pointer  points.   This  is  referred   to   as
  49.         dereferencing  the  pointer.  Careful study  of  the  output
  50.         fields  in  line 15 will reveal that we  first  display  the
  51.         value  of Index, then the value to which the  pointer  Where
  52.         points,  and  finally  the value to which  the  pointer  Who
  53.         points.  Since both pointers point to the variable Index, we
  54.         are  essentially displaying the value of Index three  times.
  55.         You will confirm this when you compile and run this program.
  56.  
  57.  
  58.                                  Page 73
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.               CHAPTER 12 - Pointers and Dynamic Allocation
  69.  
  70.  
  71.  
  72.              In  line 17, we tell the system to assign the value  of
  73.         23  to the variable to which the pointer Where points as  an
  74.         illustration.   If  you  understood the  discussion  in  the
  75.         previous paragraph, you will understand that we are actually
  76.         assigning  the variable named Index the value of 23  because
  77.         that is where the pointer named Where is pointing.  In  line
  78.         18, we once again display the value of the variable Index  3
  79.         times  just  as  we did in line 15.  It  would  be  to  your
  80.         advantage  to compile and run this program to see  that  the
  81.         value  of 17 is output three times, then the value of 23  is
  82.         output three times.
  83.  
  84.              In  a program as simple as this, the value of  pointers
  85.         is  not  at all clear but a simple program  is  required  in
  86.         order  to  make the technique clear.   Display  the  program
  87.         named  POINT  on your monitor again because we are  not  yet
  88.         finished with it.
  89.  
  90.                             A FEW MORE POINTERS
  91.  
  92.              In  line 4, we define a new type named Int_Point  which
  93.         is  a pointer to an integer type variable.  We use this  new
  94.         type in line 9 to define three more pointers and in line 20,
  95.         we  assign  one of them the address of  the  variable  named
  96.         Index.   Since the pointers are of identical types, in  line
  97.         21 we can assign Pt2 the value of Pt1, which is actually the
  98.         address of the variable named Index.  Likewise, the  pointer
  99.         Pt3  is  assigned the value of Pt2, and we  have  all  three
  100.         pointers  pointing to the variable named Index.  If you  are
  101.         using  TURBO Pascal version 4.0, you are allowed  to  assign
  102.         pointers  like this only if they have the same  type,  which
  103.         these three do.  However, since the pointers named Where and
  104.         Who are assigned individually, they are not of the same type
  105.         according to the rules of Pascal and if line 14 were changed
  106.         to  read  "Who := Where;", a compilation error  would  occur
  107.         with  TURBO Pascal version 4.0.  This error would not  occur
  108.         with TURBO Pascal 3.0 since it is a little less stringent in
  109.         its type checking.
  110.  
  111.              Finally,  we assign the only variable in  this  program
  112.         which is named Index the value of 151 in line 23 and display
  113.         the value 151 three times as we did above.  Compile and  run
  114.         this  program again to see that it does indeed  display  the
  115.         value 151 three times.
  116.  
  117.                  THIS IS JUST FOR TURBO PASCAL VERSION 4.0
  118.  
  119.              If  you are using TURBO Pascal version 4.0, you  should
  120.         display  the  program named POINT4 on your  monitor  for  an
  121.         example  of another new extension to the Pascal  programming
  122.  
  123.  
  124.                                  Page 74
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.               CHAPTER 12 - Pointers and Dynamic Allocation
  135.  
  136.  
  137.         language by Borland.  This program is identical to the  last
  138.         except in lines 13, 14 and 20, where the symbol @ is used to
  139.         denote  the  address of the variable index rather  than  the
  140.         function  "Addr".   This is only available in  TURBO  Pascal
  141.         version  4.0  as  a convenience to you.   In  ANSI  standard
  142.         Pascal  the @ symbol is used as a synonym for the  ^  symbol
  143.         but  Borland  chose  to use it for  a  completely  different
  144.         purpose.  If you are using TURBO Pascal 3.0, you will not be
  145.         able  to compile and run this program, but nothing  is  lost
  146.         because it is identical to the previous one.
  147.  
  148.                     OUR FIRST LOOK AT DYNAMIC ALLOCATION
  149.  
  150.              If you examine the file named POINTERS, you will see  a
  151.         very trivial example of pointers and how they are used  with
  152.         dynamically  allocated variables.  In the  var  declaration,
  153.         you  will  see that the two variables have a ^ in  front  of
  154.         their  respective types once again, defining  two  pointers.
  155.         They  will  be  used  to  point  to  dynamically   allocated
  156.         variables that have not yet been defined.
  157.  
  158.              The  pointer  My_Name is a pointer to  a  20  character
  159.         string.  The pointer actually points to an address somewhere
  160.         within  the  computer memory, but we don't know  where  yet.
  161.         Actually,  there  is nothing for it to point at  because  we
  162.         have  not defined a variable.  After we assign it  something
  163.         to  point  to,  we can use the pointer to  access  the  data
  164.         stored at that address.
  165.  
  166.              Your  computer has some amount of memory  installed  in
  167.         it. If it is an IBM-PC or compatible, it can have up to 640K
  168.         of  RAM  which  is addressable  by  various  programs.   The
  169.         operating system requires about 60K of the total, and if you
  170.         are  using TURBO Pascal version 3.0, it requires about  35K,
  171.         but  if you are using version 4.0, it requires  about  110K.
  172.         The  TURBO Pascal program can use up to 64K.   Adding  those
  173.         three  numbers together results in about 159K or 234K.   Any
  174.         memory you have installed in excess of that is available for
  175.         the  stack  and  the heap.  The stack  is  a  standard  area
  176.         defined  and controlled by DOS that can grow and  shrink  as
  177.         needed.   Many books are available to define the  stack  and
  178.         its use if you are interested in more information on it.
  179.  
  180.                              WHAT IS THE HEAP?
  181.  
  182.              The  heap  is  a Pascal defined  entity  that  utilizes
  183.         otherwise   unused   memory  to  store  data.    It   begins
  184.         immediately  following  the program and grows  as  necessary
  185.         upward toward the stack which is growing downward.  As  long
  186.         as  they never meet, there is no problem.  If they  meet,  a
  187.         run-time error is generated.  The heap is therefore  outside
  188.  
  189.  
  190.                                  Page 75
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.               CHAPTER 12 - Pointers and Dynamic Allocation
  201.  
  202.  
  203.         of the 64K limitation of TURBO Pascal and many other  Pascal
  204.         compilers.
  205.  
  206.              TURBO Pascal version 4.0 does not limit us to 64K,  but
  207.         there  are other reasons for using the heap in  addition  to
  208.         the 64K limitation.  These should be evident as we learn how
  209.         the heap works.
  210.  
  211.              If  you  did not understand the  last  few  paragraphs,
  212.         don't  worry.   Simply remember that  dynamically  allocated
  213.         variables are stored on the heap and do not count in the 64K
  214.         limitation placed upon you by some compilers.
  215.  
  216.              Back  to  our  example  program,  POINTERS.   When   we
  217.         actually  begin  executing the program, we  still  have  not
  218.         defined the variables we wish to use to store data in.   The
  219.         first  executable statement in line 10 generates a  variable
  220.         for us with no name and stores it on the heap.  Since it has
  221.         no name, we cannot do anything with it, except for the  fact
  222.         that  we do have a pointer My_Name that is pointing  to  it.
  223.         By  using the pointer, we can store up to 20  characters  in
  224.         it, because that is its type, and later go back and retrieve
  225.         it.
  226.  
  227.                         WHAT IS DYNAMIC ALLOCATION?
  228.  
  229.              The  variable we have just described is  a  dynamically
  230.         allocated  variable  because  it was not defined  in  a  var
  231.         declaration,   but  with  a  "New"  procedure.   The   "New"
  232.         procedure  creates  a variable of the type  defined  by  the
  233.         pointer,  puts  it  on the heap,  and  finally  assigns  the
  234.         address  of  the  variable  to  the  pointer  itself.   Thus
  235.         My_Name contains the address of the variable generated.  The
  236.         variable  itself  is referenced by using the pointer  to  it
  237.         followed by a ^, just like in the last program, and is read,
  238.         "the variable to which the pointer points".
  239.  
  240.              The statement in line 11 assigns a place on the heap to
  241.         an  integer  type variable and puts its address  in  My_Age.
  242.         Following  the  "New"  statements  we  have  two  assignment
  243.         statements  in  which  the  two  variables  pointed  at  are
  244.         assigned values compatible with their respective types,  and
  245.         they  are both written out to the video display in much  the
  246.         same manner as we did in the program named POINT.
  247.  
  248.                  GETTING RID OF DYNAMICALLY ALLOCATED DATA
  249.  
  250.             The two statements in lines 19 and 20 are  illustrations
  251.         of  the way the dynamically allocated variables are  removed
  252.         from use.  When they are no longer needed, they are disposed
  253.  
  254.  
  255.  
  256.                                  Page 76
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.               CHAPTER 12 - Pointers and Dynamic Allocation
  267.  
  268.  
  269.         of with the Dispose procedure which frees up their space  on
  270.         the heap so it can be reused.
  271.  
  272.              In   such   a  simple  program,  pointers   cannot   be
  273.         appreciated, but it is necessary for a simple  illustration.
  274.         In  a large, very active program, it is possible  to  define
  275.         many  variables, dispose of some of them, define  more,  and
  276.         dispose of more, etc.  Each time some variables are disposed
  277.         of,  their  space  is then  made  available  for  additional
  278.         variables defined with the "New" procedure.
  279.  
  280.              The heap can be made up of any assortment of variables,
  281.         they do not have to all be the same.  One point must be kept
  282.         in  mind.   Anytime a variable is defined, it  will  have  a
  283.         pointer  pointing to it.  The pointer is the only  means  by
  284.         which  the variable can be accessed.  If the pointer to  the
  285.         variable is lost or changed, the data itself is lost for all
  286.         practical purposes.
  287.  
  288.              Compile and run this program and examine the output.
  289.  
  290.                        DYNAMICALLY STORING RECORDS;
  291.  
  292.              The next example program, DYNREC, is a repeat of one we
  293.         studied  in an earlier chapter.  For your  own  edification,
  294.         review the example program BIGREC before going ahead in this
  295.         chapter.   Assuming  that you are back in DYNREC,  you  will
  296.         notice  that this program looks very similar to the  earlier
  297.         one,  and in fact they do exactly the same thing.  The  only
  298.         difference  in  the type declaration is the  addition  of  a
  299.         pointer  Person_Id,  and in the var declaration,  the  first
  300.         four  variables  are  defined as  pointers  here,  and  were
  301.         defined as record variables in the last program.
  302.  
  303.              A  point  should  be  made  here.   Pointers  are   not
  304.         generally  used in very small programs.  This program  is  a
  305.         good bit larger than the last and should be a clue to you as
  306.         to why such a trivial program was used to introduce pointers
  307.         in  this  tutorial.   A  very  small,  concise  program  can
  308.         illustrate  a  topic  much  better  that  an  large  complex
  309.         program, but we must go on to more useful constructs of  any
  310.         new topic.
  311.  
  312.                   WE JUST BROKE THE GREAT RULE OF PASCAL
  313.  
  314.              Notice  in  the  type  declaration  that  we  used  the
  315.         identifier  Person in line 18 before we defined it  in  line
  316.         19,  which is illegal to do in Pascal.  Foreseeing the  need
  317.         to  define a pointer prior to the record, the  designers  of
  318.         Pascal  allow us to break the rule in this one  place.   The
  319.         pointer  could  have been defined after the record  in  this
  320.  
  321.  
  322.                                  Page 77
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.  
  332.               CHAPTER 12 - Pointers and Dynamic Allocation
  333.  
  334.  
  335.         particular  case,  but  it was more  convenient  to  put  it
  336.         before, and in the next example program, it will be required
  337.         to put it before the record.  We will get there soon.
  338.  
  339.              Since Friend is really 50 pointers, we have now defined
  340.         53 different pointers to records, but so far have defined no
  341.         variables other than Temp and Index.  We immediately use the
  342.         New  procedure  to dynamically allocate a record  with  Self
  343.         pointing  to it, and use the pointer so defined to fill  the
  344.         dynamically  allocated record.  Compare this to the  program
  345.         named   BIGREC and you will see that it is identical  except
  346.         for  the addition of the "New" and adding the ^ to each  use
  347.         of the pointer to designate the data pointed to.
  348.  
  349.                         THIS IS A TRICK, BE CAREFUL
  350.  
  351.              Now  go  down to line 48 where Mother  is  allocated  a
  352.         record and is then pointing to the record.  It seems an easy
  353.         thing to do then to simply assign all of the values of  self
  354.         to all the values of mother as shown in the next  statement,
  355.         but  it doesn't work.  All the statement does, is  make  the
  356.         pointer  Mother  point  to  the same  place  where  Self  is
  357.         pointing because we did a pointer assignment.  The data that
  358.         was allocated to the pointer Mother is now somewhere on  the
  359.         heap,  but we don't know where, and we cannot find  it,  use
  360.         it, or deallocate it.  This is an example of losing data  on
  361.         the  heap.   The  proper  way  is  given  in  the  next  two
  362.         statements  where  all fields of Father are defined  by  all
  363.         fields  of  Mother which is pointing at  the  original  Self
  364.         record.   Note that since Mother and Self are both  pointing
  365.         at  the same record, changing the data with  either  pointer
  366.         results in the data appearing to be changed in both  because
  367.         there is, in fact, only one field where the data is stored.
  368.  
  369.              In  order  to  Write from or Read  into  a  dynamically
  370.         assigned  record it is necessary to use a  temporary  record
  371.         since  dynamically  assigned records are not allowed  to  be
  372.         used  in  I/O statements.  This is illustrated in  lines  57
  373.         through 63 of the program where some data is written to  the
  374.         monitor.
  375.  
  376.              Finally,   the  dynamically  allocated  variables   are
  377.         disposed  of  prior  to ending the program.   For  a  simple
  378.         program such as this, it is not necessary to dispose of them
  379.         because all dynamic variables are disposed of  automatically
  380.         when  the program is terminated and we return to DOS or  the
  381.         TURBO  Pascal  integrated environment.  Notice that  if  the
  382.         "Dispose(Mother);"  statement was included in  the  program,
  383.         the data could not be found due to the lost pointer, and the
  384.         program would be unpredictable, probably leading to a system
  385.         crash.
  386.  
  387.  
  388.                                  Page 78
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.  
  397.  
  398.               CHAPTER 12 - Pointers and Dynamic Allocation
  399.  
  400.  
  401.  
  402.                        SO WHAT GOOD IS THIS ANYWAY?
  403.  
  404.              Remember  when you were initially studying  BIGREC?   I
  405.         suggested  that you see how big you could make the  constant
  406.         Number_Of_Friends  before  you ran out of memory.   At  that
  407.         time  we found that it could be made slightly  greater  than
  408.         1000   before  we  got  the  memory  overflow   message   at
  409.         compilation.  Try the same thing with DYNREC to see how many
  410.         records  it  can handle, remembering that  the  records  are
  411.         created dynamically, so you will have to run the program  to
  412.         actually run out of memory.  The final result will depend on
  413.         how  much  memory you have installed, and  how  many  memory
  414.         resident programs you are using such as "Sidekick".  If  you
  415.         have  a  full  memory of 640K, I  would  suggest  you  start
  416.         somewhere above 8000 records of Friend.
  417.  
  418.              Now  you  should  have  a  good  idea  of  why  Dynamic
  419.         Allocation can be used to greatly increase the usefulness of
  420.         your programs.  There is, however, one more important  topic
  421.         we  must  cover on dynamic allocation.  That is  the  linked
  422.         list.
  423.  
  424.                           WHAT IS A LINKED LIST?
  425.  
  426.              Understanding  and  using a linked list is by  far  the
  427.         most  baffling  topic  you will confront  in  Pascal.   Many
  428.         people  simply throw up their hands and never try to  use  a
  429.         linked list.  I will try to help you understand it by use of
  430.         an  example  and lots of explanation.  Examine  the  program
  431.         named LINKLIST for an example of a linked list.  I tried  to
  432.         keep it short so you could see the entire operation and  yet
  433.         do something meaningful.
  434.  
  435.              To begin with, notice that there are two types  defined
  436.         in  lines  4 and 6, a pointer to the record and  the  record
  437.         itself.  The record, however, has one thing about it that is
  438.         new  to  us, the last entry, Next is a  pointer  to  another
  439.         record  of this type.  This record then, has the ability  to
  440.         point to itself, which would be trivial and meaningless,  or
  441.         to another record of the same type which would be  extremely
  442.         useful  in  some cases.  In fact, this is the way  a  linked
  443.         list is used.  I must point out, that the pointer to another
  444.         record,  in this case called Next, does not have to be  last
  445.         in the list, it can be anywhere it is convenient for you.
  446.  
  447.              A  couple of pages ago, we discussed the fact  that  we
  448.         had to break the great rule of Pascal and use an  identifier
  449.         before it was defined.  This is the reason the exception  to
  450.         the  rule  was  allowed.  Since the pointer  points  to  the
  451.         record, and the record contains a reference to the  pointer,
  452.  
  453.  
  454.                                  Page 79
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.  
  462.  
  463.  
  464.               CHAPTER 12 - Pointers and Dynamic Allocation
  465.  
  466.  
  467.         one  has  to be defined after being used, and  by  rules  of
  468.         Pascal, the pointer can be defined first, provided that  the
  469.         record  is  defined  immediately following it.   That  is  a
  470.         mouthful  but  if  you  just use the  syntax  shown  in  the
  471.         example, you will not get into trouble with it.
  472.  
  473.                             STILL NO VARIABLES?
  474.  
  475.              It  may  seem  strange,  but  we  still  will  have  no
  476.         variables defined, except for our old friend Index.  In fact
  477.         for  this example, we will only define 3 pointers.   In  the
  478.         last example we defined 54 pointers, and had lots of storage
  479.         room.  Before we are finished, we will have at least a dozen
  480.         pointers but they will be stored in our records, so they too
  481.         will be dynamically allocated.
  482.  
  483.              Lets  look at the program itself now.  In line  20,  we
  484.         create  a dynamically allocated record and define it by  the
  485.         pointer  Place_In_List.   It is composed of the  three  data
  486.         fields,  and  another pointer.  We define  Start_Of_List  to
  487.         point  to  the first record created, and we  will  leave  it
  488.         unchanged throughout the program.  The pointer Start_Of_List
  489.         will  always  point to the first record in the  linked  list
  490.         which we are building up.
  491.  
  492.                    WHAT IS "nil" AND WHAT IS IT USED FOR?
  493.  
  494.              We  define the three variables in the record to be  any
  495.         name  we  desire  for illustrative  purposes,  and  set  the
  496.         pointer  in  the record to "nil".  The word nil  is  another
  497.         reserved  word that doesn't give the pointer an address  but
  498.         defines it as empty.  A pointer that is currently nil cannot
  499.         be  used to manipulate data because it has no value, but  it
  500.         can  be tested in a logical statement to see if it  is  nil.
  501.         It  is therefore a dummy assignment.  With all of that,  the
  502.         first record is completely defined.
  503.  
  504.                         DEFINING THE SECOND RECORD
  505.  
  506.              When  you  were young you may have played  a  searching
  507.         game  in  which you were given a clue telling you  where  to
  508.         find  the  next  clue.   The next clue had  a  clue  to  the
  509.         location  of  the third clue.  You kept going from  clue  to
  510.         clue  until  you found the prize.  You  simply  exercised  a
  511.         linked  list.  We will now build up the same kind of a  list
  512.         in  which each record will tell us where the next record  is
  513.         at.
  514.  
  515.              In  lines  27  through 33 we  will  define  the  second
  516.         record.   Our goal will be to store a pointer to the  second
  517.         record  in the pointer field of the first record.  In  order
  518.  
  519.  
  520.                                  Page 80
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.               CHAPTER 12 - Pointers and Dynamic Allocation
  531.  
  532.  
  533.         to  keep track of the last record, the one in which we  need
  534.         to  update  the  pointer, we will keep a pointer  to  it  in
  535.         Temp_Place.   Now  we can dynamically allocate  another  New
  536.         record  and  use  Place_In_List  to  point  to  it.    Since
  537.         Temp_Place  is now pointing at the first record, we can  use
  538.         it to store the value of the pointer which points to the new
  539.         record which we do in line 29.  The 3 data fields of the new
  540.         record are assigned nonsense data for our illustration,  and
  541.         the pointer field of the new record is assigned nil.
  542.  
  543.              Lets  review our progress to this point.  We  now  have
  544.         the  first record with a person's name and a pointer to  the
  545.         second record, and a second record with a different person's
  546.         name  and  a  pointer  assigned nil.   We  also  have  three
  547.         pointers, one pointing to the first record, one pointing  to
  548.         the  last record, and one we used just to get here since  it
  549.         is  only  a temporary pointer.  If you  understand  what  is
  550.         happening so far, lets go on to add some additional  records
  551.         to  the  list.   If  you are confused,  go  back  over  this
  552.         material again.
  553.  
  554.                              TEN MORE RECORDS
  555.  
  556.              The next section of code is contained within a for loop
  557.         so  the  statements are simply repeated ten times.   If  you
  558.         observe  carefully, you will notice that the statements  are
  559.         identical  to the second group of statements in the  program
  560.         (except  of course for the name assigned).  They operate  in
  561.         exactly  the same manner, and we end up with ten more  names
  562.         added  to  the  list.  You will now see  why  the  temporary
  563.         pointer was necessary, but pointers are cheap, so feel  free
  564.         to use them at will. A pointer only uses 4 bytes of memory.
  565.  
  566.                       FINALLY, A COMPLETE LINKED LIST
  567.  
  568.              We now have generated a linked list of twelve  entries.
  569.         We  have a pointer pointing at the first entry, and  another
  570.         pointer  pointing at the last.  The only data stored  within
  571.         the program itself are three pointers, and one integer,  all
  572.         of  the  data is on the heap.  This is one  advantage  to  a
  573.         linked  list,  it uses very little local memory, but  it  is
  574.         costly  in terms of programming.  (Keep in mind that all  of
  575.         the data must be stored somewhere in memory, and in the case
  576.         of  the linked list, it is stored on the heap.)  You  should
  577.         never  use  a linked list simply to save  memory,  but  only
  578.         because  a  certain program lends itself well to  it.   Some
  579.         sorting  routines  are  extremely fast because  of  using  a
  580.         linked  list,  and  it could be advantageous  to  use  in  a
  581.         database.
  582.  
  583.  
  584.  
  585.  
  586.                                  Page 81
  587.  
  588.  
  589.  
  590.  
  591.  
  592.  
  593.  
  594.  
  595.  
  596.               CHAPTER 12 - Pointers and Dynamic Allocation
  597.  
  598.  
  599.              Following  is  a graphical representation of  what  the
  600.         linked list looks like.
  601.  
  602.         Start_Of_List---->John
  603.                           Q
  604.                           Doe
  605.                           Next---->Mary
  606.                                    R
  607.                                    Johnson
  608.                                    Next---->William
  609.                                             S
  610.                                             Jones
  611.                                             Next---->
  612.                                                  .
  613.                                                  .
  614.                                                  .
  615.                                              ---->William
  616.                                                   S
  617.                                                   Jones
  618.                                                   Next---->nil
  619.  
  620.                       HOW DO WE GET TO THE DATA NOW?
  621.  
  622.              Since  the data is in a list, how can we get a copy  of
  623.         the  fourth entry for example?  The only way is to start  at
  624.         the beginning of the list and successively examine  pointers
  625.         until  you  reach the desired one.  Suppose you are  at  the
  626.         fourth and then wish to examine the third.  You cannot  back
  627.         up,  because  you didn't define the list that way,  you  can
  628.         only  start  at the beginning and count to the  third.   You
  629.         could  have  defined  the  record  with  two  pointers,  one
  630.         pointing forward, and one pointing backward.  This would  be
  631.         a  doubly-linked  list and you could then go  directly  from
  632.         entry four to entry three.
  633.  
  634.              Now  that  the list is defined, we will read  the  data
  635.         from the list and display it on the video monitor.  We begin
  636.         by defining the pointer, Place_In_List, as the start of  the
  637.         list.   Now you see why it was important to keep a  copy  of
  638.         where  the list started.  In the same manner as filling  the
  639.         list,  we go from record to record until we find the  record
  640.         with nil as a pointer.
  641.  
  642.              There are entire books on how to use linked lists,  and
  643.         most Pascal programmers will seldom, if ever, use them.  For
  644.         this  reason, additional detail is  considered  unnecessary,
  645.         but  to be a fully informed Pascal programmer, some  insight
  646.         is necessary.
  647.  
  648.  
  649.  
  650.  
  651.  
  652.                                  Page 82
  653.  
  654.  
  655.  
  656.  
  657.  
  658.  
  659.  
  660.  
  661.  
  662.               CHAPTER 12 - Pointers and Dynamic Allocation
  663.  
  664.  
  665.                            PROGRAMMING EXERCISE
  666.  
  667.         1.  Write  a program to store a few names dynamically,  then
  668.             display  the stored names on the monitor.  As your first
  669.             exercise in dynamic allocation, keep it very simple.
  670.  
  671.  
  672.  
  673.  
  674.  
  675.  
  676.  
  677.  
  678.  
  679.  
  680.  
  681.  
  682.  
  683.  
  684.  
  685.  
  686.  
  687.  
  688.  
  689.  
  690.  
  691.  
  692.  
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.  
  700.  
  701.  
  702.  
  703.  
  704.  
  705.  
  706.  
  707.  
  708.  
  709.  
  710.  
  711.  
  712.  
  713.  
  714.  
  715.  
  716.  
  717.  
  718.                                  Page 83
  719.