Pointer-Code Diagramming

This is a method for diagramming code that deals with lots of pointer / reference manipulation, such as linked-list code. The diagram is essentially a table, where each column of the table represents a hypothetical object in memory. In each row we put some event in the code or some other note. Events might be labeling the memory something new, or telling the object there to point to some other object. Perhaps it's best to start with a concrete example. Here's a simple definition for the linked-list nodes we'll be dealing with:

class node{
public:
  int item;
  node *next;
  node(int i, node *n): item(i), next(n){}
};

Let's diagram the events in the following function, which reverses a linked list:

node *reverse(node *cur){
  node *last = NULL, *rest;
  while(cur){
    rest = cur->next;
    cur->next = last;
    last = cur;
    cur = rest;
  }
  return last;
}

The code traverses the list while changing each node to point to the node before it, instead of the one after it. Equivalently, you could imagine that what's happening is that we're taking each node from the first list and pushing it onto the front of a new list that we create.

To keep track of things while it does this, it maintains last, cur, and rest pointers, and only makes changes to cur. Since we initialize last to NULL, the first pass through the loop causes the head of the list that was passed in to point to NULL, making it the end of the new list. Note that if cur is NULL, we skip the loop entirely and return last, which is correctly set to NULL.

Here's the table corresponding to the reverse function:

    NULL      |         |
 1:           cur?             // node *reverse(node *cur){
 2: last                       // node *last = NULL, *rest;
 3: while(cur){
 4:           cur------>?      
 5:                     rest?  // rest = cur->next;
 6:   <-------                 // cur->next = last;
 7:           last             // last = cur;
 8:                     cur?   // cur = rest;
 9: }
10: return last;

Line 1 notes that, when we enter the function, all we have is a node labeled "cur". We indicate cur may be null with a "?". In line 2 we create a last pointer and initialize it to NULL. The NULL column is always at the left, while the additional columns are for each hypothetical node that might be present in the list.

To proceed, we have to first establish that cur isn't null. We put the actual code to do so in line 3. Line 4 notes that inside the loop, cur isn't null. We write "cur" again, without the question mark, and show that it's pointing to the next node, which we label simply as "?" since we have no label for it, and it might be null. In line 5, we go ahead and label it rest. In line 6, the arrow indicates that cur should now point to last, which, on the first pass through the loop, correctly sets it to null. In lines 7 and 8 we relabel cur to last, and then rest? to cur?.

The table is useful for designing new list-manipulation code, explaining it to someone else, and verifying that it works correctly. It also allows you to deal with just the important parts of list-manipulation code:

What are the labels and where are they pointing to at different points in the code?
Have we established that things are or aren't null when they should be?
What are the changes to the next pointers?

The table is useful as a way to quickly prototype and then fill in the remaining code almost mechanically. If you were writing the above table on a board or on paper, it would simply be:

NULL
          cur?             
last                       
while(cur){
          cur------>?      
                    rest?  
  <-------                 
          last             
                    cur?
}
return last;

John LeFlohic March 7, 2010 Last Updated May 3, 2010