Structures Top ListsNodes Contents

Nodes

You can download the functions defined or used in this chapter with the following commands:

    wget troll.cs.ua.edu/ACP-C/nodes.c
    wget troll.cs.ua.edu/ACP-C/nodes.h

These files will help you run the test code listed in this chapter.

The Node Structure

A list is a data structure that has some benefits over arrays, the main one being it grows with hardly any effort. As such, it is useful for storing data that can grow without bound. Lists, at their very core, are composed of chains of nodes, so we will start our investigation into lists by first exploring nodes.

A node is a simple structure that bundles together two variables. The first variable holds a value; this value may be an integer, a real number, a pointer to a string or a record, or a myriad of other types. The second variable points to the next node in the list. So, a list is merely a chain of nodes, each node holding a value. Graphically, nodes are represented as a box with two arrows. The downward pointing arrow typically leads to the value, while the rightward pointing arrow points to another node. While the right arrow is truly a pointer, as it points to another node, the down arrow may or may not be a pointer. Typically, if the value of a node is a pointer, the down arrow will point to a box of some kind (or zero). Regardless, an arrow is used to point to a value; one uses context to decide whether the value is a pointer or a basic value.

When we chain a series of nodes together, we get a list:

where items is a variable that points to the first node, v1 through v4 are the values held in the list, and null represents the null pointer signifying the end of the list. In C, zero is used to signify the null pointer.

Nodes are described with the C structure mechanism. Here is one possible description of a node.

    typedef struct node
        {
        int value;
        struct node *next;
        } Node;

The next variable is a pointer to a node structure, as expected33. The value variable, on the other hand, is given the type of values we wish to place in the list. In this case, we will use nodes to hold integer values.

Like all structures, we can allocate a node both statically and dynamically. As stated earlier, we will focus on dynamic allocation. To make our code easier to read, we will define a constructor whose task it is to dynamically allocate a node.

Node constructors, accessors, and mutators

In the previous chapter, we learned that using constructors, accessors, and mutators allow us to abstract away the internal details of structures. We can do the same for nodes. Node constructors could be defined as:

    Node *
    newEmptyNode(void)
        {
        Node *p = malloc(sizeof(Node));     //check for malloc failure omitted
        p->value = 0;                       //set to empty
        p->next = 0;                        //set to the null pointer
        return p;
        }

and:

    Node *
    newNode(int v,Node *n)
        {
        Node *p = malloc(sizeof(Node));     //check for malloc failure omitted
        p->value = v;
        p->next = n;
        return p;
        }

with accessors and mutators:

    int getNodeValue(Node *n) { return n->value; }
    Node *getNodeNext(Node *n) { return n->next; }
    void setNodeValue(Node *n,int v) { n->value = v; return; }
    void setNodeNext(Node *n,Node *p) { n->next = p; return; }

Given these constructors, accessors, and mutators, we can now assemble a chain of nodes.

Assembling nodes into a list

Let us now define a function that reads integer values from a file and stores them into a list:

    Node *
    readIntegers(FILE *fp)
        {
        int x;
        Node *items;

        items = 0; //items starts out as null

        //employ the standard reading pattern
        x = readInt(fp);
        while (!feof(fp))
            {
            items = newNode(x,items);
            x = readInt(fp);
            }
        return items;
        }

Assume the file data.txt exists with the following values:

    1 2 3
    4 5 6
    7 8

The first value read is a 1. With this value, a new node is constructed. Since items has an initial value of zero, this new node's next pointer is null. When this newly constructed node is assigned back to items, we have this situation:

As stated earlier, the value field is not an integer pointer in this case, but the down arrow points to the value for visual convenience.

Next, the value 2 is read, the while test succeeds, a new node is constructed, and that node is assigned to items. This time, the newly constructed node's next pointer points to the old value of items, which was the node holding the 1. The situation now looks like:

When new nodes are added to the items list, they are placed on the front of the growing list. So after the next integer is read and node created, we have:

Once we have collected all the integers in the file into a list, we see that the values in the list are in the opposite order as found in the file! That is, the last value read is the first value in the list34. The strange order of the values in the list may bother you, but there are many situations where the order of the values in the list do not matter. For example, if we were to sum the values in the list, does the order the values appear matter? The answer is no.

Now that we have all our values in a list, how might we display them? Here is a function that moves through the list, using the getNodeValue and getNodeNext functions to access each of the values of the list in turn.

    void
    displayList(Node *items)
        {
        while (items != 0)
            {
            printf("{%d}",getNodeValue(items));
            items = getNodeNext(items);
            }
        printf("\n");
        }

The while loop runs as long as items isn't null. Inside the loop, the value of the first node in the list is printed. Then, items is reset to point to the next node in the list and the process repeats.

Now, to test our code:

    //test 
    #include "scanner.h"
    #include "nodes.h"
    FILE *fp;
    if ((fp = fopen("data.txt","r")) == 0)
        {
        fprintf(stderr,"data.txt missing\n");
        exit(-1);
        }
    Node *items = readIntegers(fp);
    displayList(items);

Assuming data.txt exists as described above, we get the following output:

    {8}{7}{6}{5}{4}{3}{2}{1}

Note the line:

    if ((fp = fopen("data.txt","r")) == 0)

This is a common idiom for assigning a value and then testing it. The variable fp gets assigned the return value of fopen within the parentheses; after it is assigned, it is checked to see if its newly assigned value is zero (signifying that the open failed).

Our next step is to define some functions that will make it easier to manipulate lists. We do that in the next chapter.

lusth@cs.ua.edu


Structures Top ListsNodes Contents