# 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](https://codehs.com/uploads/c21f573993569ed29683595e46f7a668)

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

![Phone Link List with 3rd Node not wired up](https://codehs.com/uploads/785aaa450d1b308f771decfd81c4232b)

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.<br>

![Phone Link List with 3rd Node inserted](https://codehs.com/uploads/ed2a3a123f0fc87b7bd9e979d1f47536)

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](https://replit.com/@Poston/724-Sorted-Phone-Book#main.cpp)