C++ Linked List Recursion Question

Question

I'm having some trouble understanding the following block of code:

void InsertSorted(Entry * & list, Entry * newOne) {
    if (list == NULL || newOne->name < list->name) {
        newOne->next = list;
        list = newOne;
    } else {
        InsertSorted(list->next, newOne);
    }
}

I tried tracing through the code but only manage to get to the point where you get to the first if statement. Once I get to the point where I execute the first if statement I don't understand how the previous calls to InsertSorted manage to connect the front part of the list to the newly created list.

Thanks

Answer 1

To understand this function, just draw the data it gets with each call.

Suppose you had a list that went like this (supposing name is an int):

1 -> 4 -> 6 -> 7 -> 10 -> NULL

And you wanted to insert 5.

On the first call, list refers to the 1 through the original callers pointer. That is, if you do this:

InsertSorted(myList, someNode);

the list inside the function refers to myList outside the function, and changing it inside changes it outside. Now, the if condition is not passed because list is not NULL and newOne->name is not < list->name. So the function calls itself, with list's next pointer and newOne. Here's where we are now:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
^ list refers to this one

5
^ this is newOne, floating off somewhere by itself

In the next call, list refers to list->next from the last call, and that means it refers to 4. Again the if is not satisfied so we go on to the else: call the function again with list->next (remember list now refers to the 4, which makes list->next refer to the 6 in this call). Here's where we are now:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
     ^ list refers to this one through 1's next pointer

5
^ this is newOne, floating off somewhere by itself

In the next call, list refers to the next pointer of the 4, which represents the 6. Here's what the list looks like:

1 -> 4 -> 6 -> 7 -> 10 -> NULL
          ^ list refers to this one through 4's next pointer

5
^ this is newOne, floating off somewhere by itself

This time, the if is satisfied (because 5 < 6), so we

1. Make newOne->next point to list. This makes the new node which represent 5 point to the 6 for it's next node.

2. Set list to newNode. This is probably confusing, but remember that list is a reference, which means changing it changes the original. The original was list->next when list referred to the 4, so it's the same as setting the node that pointed to the 4's next pointer to point to newOne.

This means the list now looks like this:

1 -> 4 -> 5 -> 6 -> 7 -> 10 -> NULL
          ^ here's newOne

And the function doesn't do any calls, so the function terminates, and control returns to the function that called it in the first place.

And you've just inserted the new element in sorted order.

You have three corner cases that you need to consider:

1. The list is empty (list == NULL immediately)
2. The element you are inserting is smaller than all the existing elements
3. The element you are inserting is larger than all the existing elements

Let's assume you're always trying to insert 5 as a new element for these tests.

So for the first one, when list is NULL - that is, your list looks like

NULL

The if statement will be true immediately, and you set newOne->next to list (which means newOne->next is NULL), and list to newOne. The function quits, and your list looks like this:

5 -> NULL

So far, so good.

If the element you are inserting is smaller than all the other elements, say, like this:

7 -> 9 -> NULL

5
^ newOne

Then the if is also triggered immediately. You set newOne->next to list, which makes it point to the 7, and set list to newOne.

5 -> 7 -> 9 -> NULL

This is taken care of.

The final corner case is when the new element is larger than all the existing elements. Say you had

3 -> NULL

As your list. On the first pass, list would point to the 3 and the if wouldn't be triggered. So you'd call the function with list->next which points to the NULL. The if is triggered (because list == NULL) and you set newOne->next to list (which is NULL) and then you set list to newOne, which makes 3->next point to newOne, because in the first call, you passed its next pointer by reference, which means changing list changes it. Now you have:

3 -> 5 -> NULL

Which is all good. So this function appears to produce desired results for any list.

As a side note, this function is tail recursive, but might be able to be made faster by making it iterative instead of recursive. This is an excellent learning exercise though.

Also note that this is not insertion sort, because you're not taking an unsorted list and sorting it, you're just inserting new data on an existing list in a manner similar to insertion sort.

Answer 2

I don't understand how the previous calls to InsertSorted manage to connect the front part of the list to the newly created list.

"The front part of the list" is already fully connected up with itself - that's what makes it a list.

The algorithm is:

1) Find the insertion point. 2) Connect the new entry in place. Now everything is connected.

We find the end of the current list by recursion: if we're there, then we're there; otherwise, we check the next link. We "check the next link" in the same way, so if that's the end then we're done, otherwise we move on to the next one, etc.

When we get to the end, we perform the following steps:

newOne->next = list;
list = newOne;

This means:

1) tell the new entry to link up to the tail part of the list. 2) tell the head part of the list to link up to the new entry.

This works because list is a reference to a pointer.

newOne->next = list copies the pointer value from list into newOne->next. That means that the Entry that newOne points to, now has a next field that points to the same place that list points to - i.e., the next element in the list. So we have linked up the new entry to the tail part of the list.

list = newOne copies the pointer value from newOne into list. That means that the pointer list itself - which is part of the last Entry in the head part of the list - now points to the sample place that newOne points to - i.e., the new Entry. So we have linked up the head part of the list to the new entry.

Because of the reference, list is the actual pointer that's part of an Entry node in the list, and not just some random Entry* local variable that happens to point to the same place.

Answer 3

newOne->next = list;

sets the next field of the newOne list node to be the front of the current list.

list = newOne;

sets the pointer that keeps track of the front of the list (called "list") to point to the new first node in the list, newOne.

The above occurs only in the case that the list is empty. The else condition walks one node down the list, until it finds the last node in the list, as controlled by the if statement conditions.

Because the parameters are passed by reference (as indicated by the '&' field), the changes made inside the function persist everywhere in the program.

Answer 4

Basically, this code inserts the new element at the beginning of the list if that's its correct location — otherwise, it moves down and treats the next element as the "beginning".

The key is that the list pointer is passed by reference, so when we say "list = newOne;" it actually has an effect in the caller's scope. So when we call "InsertSorted(list->next, newOne)", it can actually update our list.

Answer 5

That's insertion sort, the item will be pluggued into the list in its placed based on the order. The recursion will end once you've reached the end of the list, or found the spot in the list where the item should sit.

Note that for each recursive call you advance one chain in the list, the "head" of the list pointer moves, essentially, through the list.