Implementing Linked Lists in RPG

Note: The code accompanying this article is available for download here.

In Basing Pointer Variables in RPG: The Basics, I wrote about the fundamentals of using basing pointers, a concept I came to understand when I learned Pascal. In this article, I continue my discussion of the use of pointers by showing how to implement linked lists in RPG.

Before I start into the meat of the article, let me first give credit where credit is due. I had pondered the question of building linked lists in RPG for some time, but I had not devised a way that made sense. Then I happened upon Managing the Default Heap Using RPG Operations on IBM‘s Web site one day. I’m indebted to whoever wrote that code, because that short program filled in the missing pieces for me.

By the way, if you try to run that code, you’ll need to fix one syntax error, as follows:

Bad:→EVAL      %SUBST(nameVal:1&gml.name_len) = name
Good:→EVAL      %SUBST(nameVal:1:name_len) = name

What is a Linked List?

In order to understand linked lists, let’s begin with a concept with which you are already familiar. You know what a record is. A record is a group of fields containing information about one entity (a customer, a vendor, an invoice, a whatever.) You are accustomed to storing records in database files.

Imagine a different way to store records in a computer. Imagine that each record is stored in memory. Every time you create a record, you ask the computer to allocate some memory in which to store the record.

Imagine further that the records may or may not be stored contiguously. Each time you ask the computer for a record’s worth of memory, the computer finds a spot wherever it can. It’s your responsibility to keep up with these records–where each one is stored in memory and the logical sequence in which they are stored. To perform this magic, you must use pointers.

The first pointer contains the address of the first node, as records that are stored in memory are known in the computer science world. Each node contains a pointer to the next node in the list.

Suppose there are three nodes in memory–for Able, Baker, and Charley–and these nodes are stored at memory addresses 400, 750, and 520 respectively. The first pointer, the pointer to the head of the list, has the value 400. Able’s node has a pointer to 750, and Baker’s node has a pointer to 520. Charley’s node has a null pointer, to signify that there are no more nodes in the list.

Figure 1 shows one way to perceive the linked list.

Figure 1.

Creating a Node

Before you can create a node, you must define what a node looks like. In RPG, use a data structure, like this one:

D Record          ds                  qualified
D   Name                        20a
D   City                        12a
D   Next                          *

Each node has a customer name, the city in which the customer is located, and a pointer to the next node in the list.

Use the %alloc function to tell the system to give you enough memory for a node.

     D RecordSize      c                   const(%size(Record))
... more code ...
     D   ouNodeAddr                    *
/free
         ouNodeAddr = %alloc(RecordSize);

Now that you have a node, put some data into it. Here’s the entire subprocedure to create and place data into a node.

P CreateNode      b
D                 pi
D   ouNodeAddr                    *
D   inName                      20a   value
D   inCity                      16a   value
D
D* locals
D NodeAddr        s               *
D Node            ds                  likeds(Record)
D                                     based(NodeAddr)
 /free
    // create a new record in dynamic memory
    ouNodeAddr = %alloc(RecordSize);

    // load the node
    NodeAddr = ouNodeAddr;
    Node.Name = inName;
    Node.City = inCity;
    Node.Next = *null;
 /end-free
P                 e

At this point we have a node in memory with a customer name, a city, and a pointer to the next node, which is null because there is no next node. The first parameter of the subprocedure informs the caller of the address of the new node.

Building the Linked List

Now that the node has been created, it’s time to put it into the list. I have chosen to insert the nodes into the list at their alphabetical positions by customer name, in order to build a sorted list. Lists do not have to be sorted, of course.

When I insert the first node, I have no choice regarding where to put the node in the list. Since the list is empty, the new node is inserted at the beginning of the list. When I insert the second node, however, I have to make a decision. If the name in the new node is alphabetically before (“less than”) the name in first node, the new node becomes the head of the list and its next pointer is assigned the address of the first node I created. But if the name in the new node is not alphabetically before (“greater than or equal to”) the first node, the head of the list retains the pointer to the first node, and the first node’s next pointer is assigned the address of the new node. And so it goes.

I won’t print the entire insertion routine here because it is long and involved. You will find it implemented in two subprocedures–InsertNode and InsertAt–in the example program. The procedure logic can be simplified by storing the head-of-list pointer in a dummy node that precedes the list. This is the approach taken in the IBM article I mentioned above. But I chose to use the more complicated routine out of personal preference.

The following table shows the contents of the nodes of the linked list I created from file QIWS/QCUSTCDT. The head of the list (variable Top in the example program) has the value 2370 to indicate that Abraham is the first node in the list. (I chose to truncate the pointer values to the last four hexadecimal digits to make the values easier to read.) Abraham’s node points to address 21E0, Alison’s node, which points to 2230, Doe. And so it goes, until we get to Williams’ node, which has a null next pointer. This is the end of the line, folks.

     P PrintList       b
     D                 pi
     D   inTopAddr                     *
     D* locals
     D   NodeAddr      s               *
     D   Node          ds                  likeds(Record)
     D                                     based(NodeAddr)
      /free
          NodeAddr = inTopAddr;
          dow NodeAddr <> *null;
             PrintLine = Node.Name + ' ' + Node.City;
             except Print;
             NodeAddr = Node.Next;
          enddo;
      /end-free
     P                 e

Abraham  M T         Isle  
Alison   J S         Isle  
Doe      J W         Sutter
Henning  G K         Dallas
Johnson  J A         Helen 
Jones    B D         Clay  
Lee      F L         Hector
Stevens  K L         Denver
Thomas   A N         Casper
Tyron    W E         Hector
Vine     S S         Broton
Williams E D         Dallas