Implementing Linked Lists in RPG
January 5, 2011 Ted Holt
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.
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.
Printing the List
Printing the list is easy. Start at the beginning (indicated by the pointer variable Top), and work node by node through the list, following the next pointers, until a node’s next is null.
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
The report looks like this:
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
Deleting the List
It is a good idea to return the memory to the system when you’re finished with it. This step is not necessary if the activation group will be destroyed, but it never hurts to be tidy. Besides, deleting the nodes in the list is not anywhere near difficult.
The delete routine is similar to the print routine. Begin at the top of the list, deleting each node and proceeding to the next node, until a node’s next pointer is null.
As I wrote in September, getting a degree in computer science was one of the best things that I ever did for myself professionally, even though my computer-oriented career has centered around business computing–what we used to call Data Processing, and later, Management Information Systems. It’s been fun to revisit programming techniques that I haven’t used in a long, long time, such as linked lists. In a future article, I will write about something even more fun–binary trees!