Concatenating lists

In the imperative world, where we perform mutation as needed, concatenating two linked lists is easy.

Given the two lists a and b, we just traverse the first list a until we reach its last node. Then we change its next pointer to the head of list b:

Note what happened to the original list a. It changed. The original list simply does not exist anymore.

We destroyed list a when we connected its third node to list b. The preceding list mutation is also not thread-safe. As seen in the previous chapter, additional mechanism, such as locking, is needed to make sure the state is synchronized correctly.

We could do the concatenation by keeping the original list intact; we do this by copying list a into another list c and then changing the third node of the new list to point to list b.

Our list a and list b are not touched at all. We copy list a into a new list, namely list c, and change its third node to point to the head of list b.

Note that the new list, that is, list c, and...