TOPIC 16.3.1
Analysis of Exercise 16-8

// Function that inserts a new node into the linked list
// sorted by population.
1: void insert_node(char name[NAME_LENGTH], long popul)
2: {
3:   county_node *new_rec_ptr; // Declare temporary pointer for the new node.
4:   county_node *before_ptr;  // More temporary pointers.
5:   county_node *after_ptr;

6:   new_rec_ptr = new county_node; // Allocate memory for a new node and
                                 // initialize pointer to point to it.

7:   strcpy(new_rec_ptr->county_name, name);  // Initialize the new node
8:   new_rec_ptr->population = popul;         // with data.

9:   if(popul > head_ptr->population)    // If the population of the new
10:    {                                  // county is greater than that of the
11:     make_node_new_head(new_rec_ptr);  // head of the list, make new node
12:    }                                  // the head.
13:   else                                // Else, determine where the new node
14:    {                                  // should be inserted.
15:     position_insertion_point(popul); // Move current_ptr to node before
                                     // insertion point.
16:     before_ptr = current_ptr;      // Use pointers to keep track of nodes
17:     after_ptr = current_ptr->next; // on each side of the insertion point.

18:     before_ptr->next = new_rec_ptr; // Insert node in list.
19:     new_rec_ptr->next = after_ptr;
20:    }
21: }

// Function that positions current_ptr at the node before the position
// where the new node should be inserted.
22: void position_insertion_point(long popul)
23: {
24:  long temp_popul;
25:  county_node *temp_ptr;

26:  if(head_ptr->next != NULL) // If more than one node exists, search the
27:   {                         // list for the correct insertion point.
28:    current_ptr = head_ptr;
29:    temp_ptr = current_ptr->next;
30:    temp_popul = temp_ptr->population;
   // Loop until the population of the node following current_ptr has
   // less population than the current node.
31:    while((current_ptr->next !=NULL) && (popul < temp_popul))
32:     {
33:      current_ptr = temp_ptr;
34:      temp_ptr = current_ptr->next;
35:      temp_popul = temp_ptr->population;
36:     }
37:   }
38:  else  // If only one node exists in the list, current_ptr is the same
39:   {    // as head_ptr. New node will be added to the end of the list.
40:    current_ptr = head_ptr;
41:   }
42: }

Understanding what the insertion function should do is the key to understanding the code. Lines 6 - 8 accomplish the first step, creating the new node and store the new data in the node. The program then checks in lines 9 - 12 the special case of the new node needing to become the head of the linked list. It check to see if the population of the new node is greater than that of the head of the list. If this is the case, the function make_node_new_head is call which make the new node the head of the list. If this was not the case position_insertion_point is called and is passed the population of the new county. The position_insertion_point function then transverses the list in lines 31 - 37 comparing the population of each node to the new node to determine where the new node needs to be inserted. Once the position has been found the pointers of the link list are updated in lines 16 - 19 and the new node has then been successfully inserted into the correct position within the linked list.