7.2.4 Example: Sorted Phone Book

In this example, you will see a twist on the linked list. The linked list is still the same with two data elements and a next record. The difference here is that instead of adding each new element to the front of the linked list, the element is going to be inserted in order.

Before getting to the code, take a look at the concept and how the nodes get linked together. In the first diagram, you can see two nodes that are linked in a standard linked list.

Phone Link List with 2 Nodes

Next, you want to insert a new node that comes between two existing nodes.

Phone Link List with 3rd Node not wired up

So how do you insert the node? Notice that you need to update the existing node A and the new node B, but the node that comes after does not need to be updated.

Phone Link List with 3rd Node inserted

In this example, node A essentially is the list head and node B is the new element you need access to both of these nodes to insert the element.

Finding the correct place can be done recursively. You simple call the next element until you are no longer less than the element you want to insert:

void insertSorted(record *newRec, record * &head) {
    if (head == NULL || newRec->name < head->name) {
        // Found the place, now add it in
        newRec->next = head;
        head = newRec;
    }
    else {
        // continue down the list
        insertSorted(newRec, head->next);
    }
}

In this example, the first call would pass A as the head and B as the newRec. Since B is not less than A, the next call would be made with C as the head and B is still the newRec.

Since B is less than C, the new record next gets updated to the head (which is C), and the head is now updated from C to be B.

The head is pass-by-reference, so it recursively updates the next field of A to point to B.

Take some time with this example. What happens when the pass-by-reference is removed and why?

Try This Example