7.2.3 Linked List and Recursion

In the last example, you saw how a linked list is created and traversed using a standard while loop. Recall that you can start by accessing the first element and then repeat until your next element is null, which is the end of the list, or the tail.

Here is the example using the item struct:

item *nextItem = head;

while(nextItem != NULL){
    cout << nextItem->data << endl;
    nextItem = nextItem->next;
}

Printing the data this way ends up being a Last-In, First-Out order, like you see in a stack. In order to print in a First-In,First-Out order, you would have to repeatedly loop through the list, stopping one element short each time. This would be terribly inefficient and not an easy code to follow. Fortunately, recursion can help us out.

Using Recursion to Traverse

It turns out, a recursive solution can be used to traverse either backward or forwards relatively easily.

Let’s start with the Last-In, First-Out loop you saw above:

void printStack(item *head){
    if (head != NULL){
        cout << head->data<<endl;
        printStack(head->next);
    }
}

Last-in, First-out:

Notice that the data prints, then the next element is called recursively. The recursive stack continues until it gets to the tail, then backtracks to the start.

What happens if you flip the two lines inside the conditional block? If you flip those two lines, you will recursively call the next element until there are no more elements, then you will work your way back and print starting with the tail of the linked list.

void printQueue(item *head){
    if (head != NULL){
        printQueue(head->next);
        cout << head->data<<endl;
    }
}

First-in, First-out:

In this example, you will notice that the recursive calls progress to the end. Once they get to the tail, it backtracks to the start, but as it backtracks, it needs to execute the print statement for each line. The result is a First-In, First-Out traversal.

Essentially, the while loop was simple to traverse from the head to the tail, but very challenging to traverse from the tail to the head.

Using recursion, it was simple to traverse, either way, just switch the order of two lines.

Try This Example