20.3 Linked Lists

I l @ ve RuBoard

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:

1. Create the item we are going to add.

    new_ptr = new linked_list_element; 

2. Store the item in the new element.

    (*new_ptr).data = item; 

3. Make the first element of the list point to the new element.

    (*new_ptr).next_ptr = first_ptr; 

4. The new element is now the first element.

    first_ptr = new_ptr; 

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.

Example 20-2. find/find.cpp

 #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 != 0) &&            (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 = value;  current_ptr->data = value; 

I l @ ve RuBoard