Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!njin!princeton!phoenix!kpfleger
From: kpfleger@phoenix.Princeton.EDU (Karl Robert Pfleger)
Newsgroups: comp.lang.pascal
Subject: Re: Pointers..
Message-ID: <8835@phoenix.Princeton.EDU>
Date: 1 Jun 89 11:51:55 GMT
References: <3398@westfort.UUCP>
Reply-To: kpfleger@phoenix.Princeton.EDU (Karl Robert Pfleger)
Organization: Princeton University, NJ
Lines: 79

Don't rag on the idea of storing linked lists in disk files. It is a
completely natural thing to do. After all, what is a linked list? A
sequencial list of records. This is exactly what a disk file contains.
Saving and loading linked lists is easy.

First of all, you have to get the linked list data structure right. I
don't remember any follow up articles so far point out that the
following is incomplete.

In article <3398@westfort.UUCP> westfort!dragon@tut.cis.ohio-state.edu writes:
>Type
>   boardtype=^boardrec;
>   boardrec=record
>name:string[20];
>age:integer;
>end;

This just defines a record with a pointer to it. A field of type
boardtype must be added to the record boardrec to make this a potential
linked list structure. But since we don't need to save the pointers in
the file, it would be best to define the structure as follows:

type
  boardtype=^boardrec;
  rectype=record
            name: string[20];       > or
            age: integer;           > whatever
           end;
  boardrec=record
             info: rectype;
             next: boardtype;
            end;

Now we can define a file to be a file of info. To save the linked list,
we just trace through the list saving info records. If t is a pointer and
f a file we do:

repeat
  write (f,t^.info);
  t:=t^.next;
 until t=nil; (or whatever tail node you use)

Reading in a disk file to a linked list is just as simple. The only
added complication is that we have to do a new(t^.next) call to allocate
memory for the next node in the list to be created each time.

I realize that most of you probably know this, but someone obviously
didn't and none of the follow up articles were very instructive about
what to do.  

You can also store slightly more interesting
structures (if you ever have a need to) like binary trees as long as the
structure has a specific form. As long as you know which order the data
was saved in, you can load it back. A couple possibilities for binary
trees exist.

A level order traversal:             1
                                 2       3
                               4   5   6   7
                              8 9 etc.

An inorder traversal:                8
                                 4       12
                               2   6  10    14
                              1 3 5 7 9 11 13 15

The routines for saving these work the same as the linked list, only you
use a tree traversal (whichever) to visit the nodes. The routines for
loading these things will, of course, be more complicated. The easiest
approach would be to load the file into an array an index into it
judiciously, but this could mean lots of extra memory.

     - KPfleg 
                  kpfleger@phoenix.princeton.edu
                  kpfleger@pucc.princeton.edu
                  or just kpfleger@pucc for BITNET sites

Hope someone found it interesting or helpful. I wouldn't want to cost
the net 'hundreds if not thousands of dollars' for nothing.