Structures and classes may contain pointers, or even a pointer to another instance of the same structure. In the following example:

class item { 
    public:
        int value; 
        item *next_ptr; 
};

the structure item is illustrated by Figure 20-2.

Figure 20-2. Item

The operator new allocates storage for a variable and returns a pointer. It is used to create new things out of thin air (actually out of an area of memory called the heap). Up to now we’ve used pointers solely to point to named variables. So if we used a statement like:

    int data; 
    int *number_ptr; 

    number_ptr = &data;

the thing we are pointing to has a name (data). The operator new creates a new, unnamed variable and returns a pointer to it. The “things” created by new can only be referenced through pointers, never by name.

In the following example, we use new to allocate an integer from the heap. The variable element_ptr will point to our new integer.

int *element_ptr;             // Pointer to an integer
element_ptr = new int;        // Get an integer from the heap

The operator new takes a single argument: the type of the item to be allocated. According to the C++ standard, if new runs out of memory, it throws an exception that normally aborts the program. (See Chapter 22 for information on how to handle this and avoid aborting.) On older C++ systems, when new runs out of memory, it returns a null pointer.

Suppose we are working on a complex record list that contains (among other things) a mailing list. We want to keep our storage use to a minimum, so we only want to allocate memory for a person if he or she exists. Creating an array of class person would allocate the data statically and use up too much space. So we will allocate space as needed. Our structure for a person is:

class person { 
    public:
        std::string  name;          // Name of the person
        std::string  address;       // Where he lives
        std::string  city_state_zip;// Part 2 of address
        int     age;                // His age
        float   height;             // His height in inches
}

We want to allocate space for this person. Later the pointer to this record will be put in the record list.

To create a new person, we use the following:

class person *new_ptr; 

new_ptr = new person;

The operator new can also allocate more complex data types such as arrays. Example 20-1 allocates storage for a integer array 80 elements long. The variable data_ptr points to this storage.

int main(  ) 
{ 
    int *data_ptr; 

    data_ptr = new int[80];

All we’ve done is substitute a simple type (such as person) with an array specification (int[80]).

The operator new gets memory from the heap. To return the memory to the heap you use the operator delete. The general form of the delete operator is:

delete pointer;       // Where pointer is a pointer to a simple object
pointer = NULL;

where pointer is a pointer previously allocated by new. If the new operator allocated an array, you must use the form:

delete[] pointer;       // Where pointer is a pointer to an array
pointer = NULL;

Strictly speaking, the line:

               pointer = NULL;

is unnecessary. However, it is a good idea to “null out” pointers after they are deleted. That way, you don’t try use a pointer to deleted memory, and you also help prevent any attempts to delete the same memory twice.

The following is an example using new to get storage and delete to dispose of it:

const DATA_SIZE = (16 * 1024);

void copy(  ) 
{ 
    char *data_ptr;     // Pointer to large data buffer

    data_ptr = new char[DATA_SIZE];       // Get the buffer

    /* 
     * Use the data buffer to copy a file 
     */ 
    delete[] data_ptr; 
    data_ptr = NULL;
}

But what happens if we forget to free the memory? The buffer becomes dead. That is, the memory management system thinks it’s being used, but no one is using it. (The technical term for this is a "memory leak.”) If the delete statement is removed from the function copy, each successive call eats up another 16K of memory.

The other problem that can occur is using memory that has been freed. When delete is used, the memory is returned to the memory pool and can be reused. Using a pointer after a delete call is similar to an array index out-of-bounds error. You are using memory that belongs to someone else. This can cause unexpected results or program crashes.

Suppose you are writing a program to send a list of names to another computer using a communications line. The operator types in the names during the day, and after work you dial up the other computer and send the names. The problem is, you don’t know ahead of time how many names are going to be typed. By using a linked-list data structure, you can create a list of names that can grow as more names are entered. With a linked list you can also easily insert names into the middle of the list (which would be slow and difficult with an array). Also, as you will see later, linked lists can be combined with other data structures to handle extremely complex data.

A linked list is a chain of items in which each item points to the next item in the chain. Think about the treasure hunt games you played when you were a kid. You were given a note that said, “Look in the mailbox.” You raced to the mailbox and found the next clue, “Look in the big tree in the back yard,” and so on until you found your treasure (or you got lost). In a treasure hunt each clue points to the next one.

Figure 20-3 graphically illustrates a linked list.

Figure 20-3. Linked list

The class declarations for a linked list are:

class linked_list {
    public:
        class linked_list_element { 
            public:
                int    data;             // Data in this element
            private:
                // Pointer to next element
                linked_list_element *next_ptr;
             friend class linked_list;
        };
 
    public:
        linked_list_element *first_ptr;   // First element in the list

        // Initialize the linked list
        linked_list(  ) {first_ptr = NULL;}

        // ... Other member functions
};

The variable first_ptr points to the first element of the list. In the beginning, before we insert any elements into the list (it is empty), this variable is initialized to NULL.

Figure 20-4 illustrates how a new element can be added to the beginning of a linked list. Now all we have to do is translate this into C++ code.

Figure 20-4. New element

To do this in C++, we execute the following steps:

The code for the actual program is:

void linked_list::add_list(int item) 
{ 
    // Pointer to the next item in the list
    linked_list_element *new_ptr; 

    new_ptr = new linked_list_element; 

    (*new.ptr).data = item 
    (*new_ptr).next_ptr = first_ptr; 
    first_ptr = new_ptr; 
}

Now that we can put things in a list, let’s use that ability. We’ll now write a short function to search the list until we find a key item or we run out of data. Example 20-2 contains the new find function.

#include <iostream>
#include <string>
#include "linked.h"
/********************************************************
 * find -- look for a data item in the list             *
 *                                                      *
 * Parameters                                           *
 *      name -- name to look for in the list            *
 *                                                      *
 * Returns                                              *
 *      true if name is found                           *
 *      false if name is not found                      *
 ********************************************************/
bool linked_list::find(const std::string& name)
{
    /* current structure we are looking at */
    linked_list_element *current_ptr;

    current_ptr = first_ptr;

    while ((current_ptr->data != name) &&
           (current_ptr != NULL))
        current_ptr = current_ptr->next_ptr;

    /*
     * If current_ptr is null, we fell off the end of the list and
     * didn't find the name
     */
    return (current_ptr != NULL);
}

Why does running this program sometimes result in a bus error? Other times it reports “found” (return 1) for an item that is not in the list. (See Answer 20-1 for the answer.)

In our find program we had to use the cumbersome notation (*current_ptr).data to access the data field of the structure. C++ provides a shorthand for this construct using the -> operator. The dot (.) operator means the field of a structure, and the structure pointer operator (->) indicates the field of a structure pointer.

The following two expressions are equivalent:

(*current_ptr).data != name 
current_ptr->data != name

So far we have only added new elements to the head of a linked list. Suppose we want to add elements in order. Figure 20-5 is an example of an ordered linked list.

Figure 20-5. Ordered list

Figure 20-6 shows the steps necessary to add a new element, “53”, to the list.

Figure 20-6. Adding element “53” to an ordered list

The following member function implements this algorithm. The first step is to locate the insertion point. The first_ptr points to the first element of the list. The program moves the variable before_ptr along the list until it finds the proper place for the insertion. The variable after_ptr is set to point to the next value. The new element will be inserted between these elements.

void linked_list::enter(int item):
{ 
    linked_list_item *before_ptr; // Insert after this element
    linked_list_item *after_ptr;  // Insert before this element

    /* 
     * Warning: This routine does not take 
     *   care of the case where the element is 
     *   inserted at the head of the list
     */

    after_ptr = first_ptr;
    while (true) { 
        before_ptr = after_ptr; 
        after_ptr = after_ptr->next_ptr; 

        // Did we hit the end of the list?
        if (after_ptr == NULL) 
            break; 

        // Did we find the place?
        if (item >= after_ptr->data) 
            break; 
    }

Now we know where to insert the new element. All we must do is insert it. We start at the element before the new one (before_ptr). This element should point to the new element, so:

    before_ptr->next_ptr = new_ptr;

Next is the new element (new_ptr). It needs to point to the element after it, or after_ptr. This is accomplished with the code:

    new_ptr->next_ptr = after_ptr;

The element after_ptr needs to point to the rest of the chain. Because it already does, we leave it alone. The full code for inserting the new element is:

    // Create new item
    new_ptr = new linked_list_item;
    new_ptr->data = item; 

    // Link in the new item
    before_ptr->next_ptr = new_ptr; 
    new_ptr->next_ptr = after_ptr; 
}

An element in a doubly linked list contains two links. One link points forward to the next element; the other points backward to the previous element. Doubly linked lists are useful where the program needs to go through the list both forward and backward.

The classes for a doubly linked list are:

class double_list {
    private:
        class double_list_element { 
            public:
                int data;                 // Data item
            private:
                double_list_element *next_ptr;    // Forward link
                double_list_element *previous_ptr;// Backward link
            friend class double_list;
        };
    public:
        double_list_element *head_ptr;   // Head of the list

        double_list(  ) {head_ptr = NULL;}

        // ... Other member functions

This is shown graphically in Figure 20-7.

Figure 20-7. Doubly linked list

To insert an item into the list, we first locate the insertion point:

void double_list::enter(int item) 
{ 
    double_list_element *insert_ptr; // Insert before this element

    /* 
     * Warning: This routine does not take 
     *   care of the case where the element is 
     *   inserted at the head of the list 
     *   or the end of the list 
     */ 

    insert_ptr = head_ptr; 
    while (true) { 
        insert_ptr = insert_ptr->next; 

        // Have we reached the end?
        if (insert_ptr == NULL) 
            break; 

        // Have we reached the right place?
        if (item >= insert_ptr->data) 
            break; 
    }

Notice that we do not have to keep track of the variable before_ptr. The pointer insert_ptr->previous_ptr is used to locate the previous element. To insert a new element, we must adjust two sets of pointers. First we create the new element:

// Create new element
new_ptr = new double_list_element;

Next we set up the forward pointer for the new item:

new_ptr->next_ptr = insert_ptr;

Graphically this is represented by Figure 20-8.

Next we connect the link to the previous element using the following code:

new_ptr->previous_ptr = insert_ptr->previous_ptr;

Figure 20-8. Doubly linked list insert, part 1

Graphically, this is represented in Figure 20-9.

Figure 20-9. Doubly linked list insert, part 2

The links are set up for the new element. Now all we have to do is break the old links between items 11 and 36 and connect them to the new item (27).

Getting to item 11 is a bit of a trick. We only have a pointer to item 36 (insert_ptr). However, if we follow the previous link back (insert_ptr->previous_ptr), we get the item (11) that we want. Now all we have to do is fix the next_ptr for this item.

The C++ code for this is surprisingly simple:

        insert_ptr->previous_ptr->next_ptr = new_ptr;

You can see this operation represented graphically in Figure 20-10.

We have only one remaining link to fix: the previous_ptr of the insert_ptr. In C++ the code looks like this:

        insert_ptr->previous_ptr = new_ptr;

This operation is represented graphically by Figure 20-11.

Figure 20-10. Doubly linked list insert, part 3

In summary, to insert a new item in a doubly linked list, you must set four links:

The final results are illustrated in Figure 20-11.

Figure 20-11. Doubly linked list insert, part 4

Suppose we want to create an alphabetized list of the words that appear in a file. We could use a linked list, but searching a linked list is slow because we must check each element until we find the correct insertion point. By using a data type called a tree, we can reduce the number of comparisons tremendously. A binary tree structure looks like Figure 20-12. Each box is called a node of the tree. The box at the top is the root and the boxes at the bottom are the leaves.^[1] Each node contains two pointers: a left pointer and a right pointer, which point to the left and right subtrees.

Figure 20-12. Tree search

The structure for a tree is:

class tree {
        private: 
        class node {
            public:
                string data;     // Word for this tree
            private:
                node *right;     // Tree to the right
                node *left;      // Tree to the left
            friend class tree;
        }; 
     public:
        node *root;  // Top of the tree (the root)

        tree(  ) {root = NULL;};
        // ... Other member function
};

Trees are often used for storing a symbol table (a list of variables used in a program). In this chapter we will use a tree to store a list of words and then to print the list alphabetically. The advantage of a tree over a linked list is that searching a tree takes considerably less time.

In this example, each node stores a single word. The left subtree stores all the words less than the current word, and the right subtree stores all the words greater than the current word.

For example, Figure 20-13 shows how we descend the tree to look for the word “orange.” We would start at the root, “lemon.” Because “orange” > “lemon,” we would descend the right link and go to “pear.” Because “orange” < “pear,” we descend the left link, where we find “orange.”

Figure 20-13. Tree

Recursion is extremely useful with trees. Our rules for recursion are 1) the function must make things simpler and 2) there must be some endpoint.

The algorithm for inserting a word in a tree is:

Does this algorithm satisfy our recursion rules? The function has two definite endpoints:

Otherwise, we enter the word into a subtree (which is simpler than the whole tree).

To see how this works, consider what happens when we insert the word “fig” into the tree. First we check the word “fig” against “lemon.” “Fig” is smaller, so we go to “apple.” Because “fig” is bigger, we go to “grape.” Because “fig” is smaller than “grape,” we try the left link. It is NULL, so we create a new node.

The function to enter a value into a tree is:

void tree::enter_one(node *&tree_node, const string& word) 
{ 
    int  result;        // Result of strcmp

    // See if we have reached the end
    if (tree_node == NULL) { 
        tree_node = new node; 

        tree_node->left = NULL; 
        tree_node->right = NULL; 
        tree_node->word = word; 
    } 
    if (tree_node->data == word) 
        return; 

    if (tree_node->data < word) 
        enter_one(tree_node->right, word); 
    else 
        enter_one(tree_node->left, word); 
}

The function to start this process is:

void tree::enter(char *word) {
    enter_one(root, word);
};

This function passes a pointer to the root of the tree to enter_one. If the root is NULL, enter_one creates the node. Because we are changing the value of a pointer, we must pass a reference to the pointer.

Despite the complex nature of a tree structure, it is easy to print. Again we use recursion. The printing algorithm is:

The code for printing the tree is:

void tree::print_one(node *top) 
{ 
    if (top == NULL) 
        return;                 // Short tree 

    print_one(top->left); 
    std::cout << top->word << '
';
    print_one(top->right); 
} 
void tree::print(  ) {
     print_one(root);
}

Now that we have the data structure defined, all we need to complete the program is a few more functions. The main function checks for the correct number of arguments and then calls the scanner and the print_one routine.

The scan function reads the file and breaks it into words. It uses the standard macro isalpha. The macro returns 1 if its argument is a letter and 0 otherwise. It is defined in the standard include file cctype. After a word is found, the function enter is called to put the word in the tree.

Example 20-3 is the listing of words.cpp.

/********************************************************
 * words -- scan a file and print out a list of words   *
 *              in ASCII order.                         *
 *                                                      *
 * Usage:                                               *
 *      words <file>                                    *
 ********************************************************/
#include <iostream>
#include <fstream>
#include <cctype>
#include <string>
#include <cstdlib>

class tree {
    private:
        // The basic node of a tree
        class node {
            private:
                node    *right;      // tree to the right 
                node    *left;       // tree to the left 
            public:
                std::string  word;   // word for this tree 

            friend class tree;      
        };

        // the top of the tree 
        node *root;

        // Enter a new node into a tree or sub-tree
        void enter_one(node *&node, const std::string& word);

        // Print a single node
        void print_one(node *top);
    public:
        tree(  ) { root = NULL;}

        // Add a new word to our tree
        void enter(std::string& word) {
            enter_one(root, word);
        }

        // Print the tree
        void print(  ) {
            print_one(root);
        }
};

static tree words;      // List of words we are looking for
        
/********************************************************
 * scan -- scan the file for words                      *
 *                                                      *
 * Parameters                                           *
 *      name -- name of the file to scan                *
 ********************************************************/
void scan(const char *const name)
{
    std::string new_word;    // word we are working on 
    int  ch;                 // current character 
    std::ifstream in_file;   // input file 

    in_file.open(name, std::ios::in);
    if (in_file.bad(  )) {
        std::cerr << "Error:Unable to open " << name << '
';
        exit(8);
    }
    while (true) {
        // scan past the whitespace 
        while (true) {
            ch = in_file.get(  );

            if (std::isalpha(ch) || (ch == EOF))
                break;
        }

        if (ch == EOF)
            break;

        new_word = ch;
        while (true) 
        {
            ch = in_file.get(  );
            if (!std::isalpha(ch))
                break;
            new_word += ch;
        }
        words.enter(new_word);
    }
}


int main(int argc, char *argv[])
{
    if (argc != 2) {
        std::cerr <<  "Error:Wrong number of parameters
";
        std::cerr <<  "      on the command line
";
        std::cerr <<  "Usage is:
";
        std::cerr <<  "    words 'file'
";
        exit(8);
    }
    scan(argv[1]);
    words.print(  );
    return (0);
}

/********************************************************
 * tree::enter_one -- enter a word into the tree        *
 *                                                      *
 * Parameters                                           *
 *      new_node -- current node we are looking at      *
 *      word -- word to enter                           *
 ********************************************************/
void tree::enter_one(node *&new_node, const std::string& word)
{
    // see if we have reached the end 
    if (new_node == NULL) {
        new_node = new node;

        new_node->left = NULL;
        new_node->right = NULL;
        new_node->word = word;
    }
    if (new_node->word == word)
        return;

    if (new_node->word < word)
        enter_one(new_node->right, word);
    else
        enter_one(new_node->left, word);
}

/********************************************************
 * tree::print_one -- print out the words in a tree     *
 *                                                      *
 * Parameters                                           *
 *      top -- the root of the tree to print            *
 ********************************************************/
void tree::print_one(node *top)
{
    if (top == NULL)
        return;                 // short tree 

    print_one(top->left);
    std::cout << top->word << '
';
    print_one(top->right);
}

I once made a program that read the dictionary into memory using a tree structure and then used it in a program that searched for misspelled words. Although trees are supposed to be fast, this program was so slow you would think I had used a linked list. Why?

Hint: Graphically construct a tree using the words “able,” “baker,” “cook,” “delta,” and “easy” and look at the result.

A classic problem in artificial intelligence is the game of chess. We are going to design a data structure for a chess-playing program. In chess there are several moves you can make. Your opponent has many responses, to which you have many answers, and so on, back and forth for several levels of moves.

Our data structure is beginning to look like a tree. But this is not a binary tree, because we have more than two branches for each node (Figure 20-14).

Figure 20-14. Chess tree

We are tempted to use the following data structure:

class chess { 
    public:
        class board_class board; // Current board position
        class next_class { 
            class move_class move;        // Our next move
            class chess *chess_ptr; // Pointer to the resulting position
        } next[MAX_MOVES]; 
};

The problem is that the number of moves from any given position varies dramatically. For example, in the beginning you have lots of pieces running around.^[2] Pieces such as rooks, queens, and bishops can move any number of squares in a straight line. When you reach the end game (in an evenly matched game), each side probably has only a few pawns and one major piece. The number of possible moves has been greatly reduced.

We want to be as efficient as possible in our storage because a chess program stresses the limits of our machine. We can reduce storage requirements by changing the next-move array to a linked list. The resulting structure is:

class next_class { 
    class move_class move;        // Our next move
    class next_class *chess_ptr;  // Pointer to the resulting position
}; 

struct chess { 
    class board_class board;     // Current board position
    class next_class *list_ptr;  // List of moves we can make from here
    class next_class this_move;  // The move we are making
};

Graphically, this looks like Figure 20-15.

Figure 20-15. Revised chess structure

The new version adds a little complexity, but it saves a great deal of storage. That’s because instead of having to allocate an array that contains all possible moves (whether used or not), we use a list to allocate only as many moves as we need to.

Exercise 20-1: Write a cross-reference program.

Exercise 20-2: Write a function to delete an element of a linked list.

Exercise 20-3: Write a function to delete an element of a doubly linked list.

Exercise 20-4: Write a function to delete an element of a tree.

Answer 20-1: The problem is with the statement:

while ((current_ptr->data != value) && 
       (current_ptr != NULL))

current_ptr->data is checked before we check to see whether current_ptr is a valid pointer (!= NULL). If it is NULL, we can easily check a random memory location that could contain anything. The solution is to check current_ptr before checking what it is pointing to:

while (current_ptr != NULL) { 
    if (current_ptr->data == value) 
        break;

Answer 20-2: The problem was as follows: because the first word in the dictionary was the smallest, every other word used the right-hand link. In fact, because the entire list was ordered, only the right-hand link was used. Although this was defined as a tree structure, the result was a linked list. See Figure 20-16.

Figure 20-16. Dictionary tree

Some of the more advanced books on data structures, such as Wirth’s Algorithms + Data Structures = Programs, discuss ways of preventing this by balancing a binary tree.

Trivia Answer: You give up. That’s right, the 21st move is to resign.