Learn Pascal in a Three Days (2nd Ed.)
(Publisher: Wordware Publishing, Inc.)
Author(s):
ISBN: 1556225679
Publication Date: 07/01/97

Passing Pointers as Parameters

You may pass pointers as parameters to functions and procedures in the same way you do with static variables. You can pass pointers either as value or variable parameters. Remember that both actual and formal parameters must be of the same type; in case of record pointers, they must point to the same record type.

11-3 Linked Lists

A linked list is a collection of data items called nodes. Each node contains a pointer to the next one. The linked list may be used to store any data type, but is usually used to hold records. In the following diagram a linked list is demonstrated.

As you can see in the diagram, each node in the linked list contains two items, the data and a pointer to the next node. The pointer in the last node points to the constant NIL, which indicates the end of the list.

List Declaration

The following is a declaration of a linked list that contains an integer data field:

TYPE
         ListPointer = ^ListRecord;
         ListRecord = RECORD
                                 DataField:INTEGER;
                                 NextField:ListPointer;
                     END;

Each node in the linked list (ListRecord), has the structure of a record. It contains a data field (DataField), which holds the actual data, and a pointer field (NextField), also referred to as link field, which keeps track of the order of the list. Notice that the pointer definition (ListPointer) precedes the record definition (ListRecord). This is actually the only situation in which you can use an identifier before it is defined. You can declare a linked list in which to store records in the same way; however, it is best to start with simple ones.

Building a List

To build a linked list, you need to declare two pointers. One to point to the first node (e.g., “FirstPointer”), and another to use temporarily in the construction process (e.g., “ToolPointer”). Both pointers are obviously of the type “ListPointer.”

VAR
         FirstPointer, ToolPointer :ListPointer;

These are the steps to build the list:

1.  Initialize an empty list by assigning the “FirstPointer” the NIL value.

         FirstPointer:= NIL;

2.  Create a node using the temporary pointer.

         NEW(ToolPointer);

3.  Read the integer from the keyboard (or any other medium) and store it into the data field of this node.

         READLN(ToolPointer^.DataField);

4.  Add the node to list by setting the pointer field so that it points to the same location as the “FirstPointer.”

         ToolPointer^.NextField:= FirstPointer;

5.  Redirect the “FirstPointer” to the new node (which is the beginning of the list).

FirstPointer := ToolPointer;

Repeat the preceding steps until all the data are read. The last data item you read will be in the first node of the linked list.

The same procedure, except for the first step, is used to add new nodes to an existing list (as you do not need to create an empty list).

The following is the procedure segment that creates the list:

FirstPointer:= NIL;
WHILE { Boolean Expression } DO
        BEGIN
               NEW(ToolPointer);
               READLN(ToolPointer^.DataField);
               ToolPointer^.NextField := FirstPointer;
               FirstPointer := ToolPointer;
        END;

Reading a List

To read a linked list, you need two pointers. The “FirstPointer” which points to the first node on the list, and the “CurrentPointer” which moves from one node to the other across the entire list.

The following are the steps to read and display the contents of a list:

1.  Make the “CurrentPointer” point to the first node by assigning it the same direction as the “FirstPointer”:

         CurrentPointer:= FirstPointer;

2.  Use the “CurrentPointer” to access and display the contents of the data field:

         WRITELN(CurrentPointer^.DataField);

3.  Move the “CurrentPointer” to the next node, by assigning it the direction of the pointer field (NextField) of the same node:

         CurrentPointer:= CurrentPointer^.NextField;

4.  Repeat steps “2” and “3” until you get to the last node. This occurs when the following condition is TRUE:

         CurrentPointer = NIL

The following is a program segment to read a list:

VAR
CurrentPointer:ListPointer;
BEGIN
 CurrentPointer:= FirstPointer;
 WHILE CurrentPointer <> NIL DO
  BEGIN
   WRITELN(CurrentPointer^.DataField);
   CurrentPointer:= CurrentPointer^.NextField
  END;
  WRITELN
END