In addition to having space to store the data corresponding to that node, a node must also contain information about how to get to the next node in the list. Each node contains some overhead to help manage and traverse the list. (In fact, in this month's example, the overhead takes up the same amount of memory as the actual data stored, so each node is twice as big as it was in Part 1, CUJ, April 1991.) A list in which each node contains only one link to the next node is called a singly-linked list. Typically, the nodes will be linked in the forward direction but they could be linked in the backward direction instead. If each node had room for two links it could simultaneously point to both its predecessor and its successor. This is called a doubly-linked list.

You can define a node to have both data and link information. The obvious data type to use is a structure. In the example, it is declared as

struct node {
   int value;     /* the node's data value */
   int fwd_ptr;/* ptr to next node in list */
};

struct node ary[MAX_NODES];

Along the way, I have been developing a new commenting style, one which I'm sure will generate even more reader mail. (Remember, nothing is ever a complete waste — it can always serve as a bad example.) I'll bravely debut it publicly here for your comment.

With regard to program readability, one of the most important thing a programmer can do is to use white space effectively. By liberally sprinkling spaces, tabs, and blank lines throughout, you can give the reader a fighting chance at seeing the overall shape of the logic and the individual source tokens used. The next problem then is program understandability — the ability of the reader to understand what the source tokens mean once he can recognize them. The key to program understandability is using meaningful (but not unwieldy) identifiers.

When writing nontrivial programs in any language, I always use comments. However, I find that comments can be distracting, particularly when placed at the end of many consecutive source lines. Some statements are quite long, and there's no room for a comment. Some programmers spend as much time worrying about their comments lining up as they do writing the code in the first place. Some comments document the very obvious. Others don't get updated when the code to which they apply gets revised.

To avoid many of these issues, I have placed very small comments at the start of source lines. Because I have rigorously adopted a tab indenting scheme, the first eight characters are otherwise wasted, so why not use them. At least then I don't have to worry about comments not lining up. Of course, I'm not really talking about detailed comments here. In fact, my comments are simply labels that refer to detail in a comment block preceding the fragment of code containing the label(s). It's like having pseudo code in the source.

Now, back to the problem. As in Part 1, the nodes will be stored in a fixed size array. However, in this version it will be an array of structures, not ints. Initially, there is no data so the list is empty. As a new node is needed, a spare entry in the array is allocated for it, and the new entry is inserted in the appropriate place in the list of used nodes. At any time, the number of nodes in use plus the number of nodes free is constant and equals the number of nodes in the underlying array.

Just how does the program know which nodes are free? Well, not only does it maintain a singly-linked list of used nodes, it has a singly-linked list of free nodes as well. Initially, all nodes are part of the free node list. To maintain these lists, there are root and tail pointers (root_node and tail_node, respectively) to the start and end of the used node list, and a root pointer (free_node) to the start of the free node list. In all cases, pointer values of EOLIST indicate end-of-list. (The only reason I have a tail pointer for the used node list is to assist adding a new node to the end of that list.)