Linked lists with recursions

Topics To Cover

Recursive structure of a list
Printing a list recursively
Computing the length of a list recursively
Adding an item in the back of a list.
Deleting a list recursively.

Recursive structure of a list

It turns out that a lot of linked list operations are very easily accomplished with recursion. The reason for this is that there is an essentially recursive way of looking at lists. Recall that "a list" in our program is really a pointer to the first node in a linked list.

Suppose LIST is a variable of type Node* in our program, and suppose that it points to the list 87, 42, 53, 4 as illustrated in the following picture:

LIST is an pointer of type Node* and therefore we say that it represents a list.
However, by that same argument the next-field of the node with data-value 87 (colored blue above) also represents a list.
- Note that LIST->next is of type Node*.
- In particular, LIST->next represents a list containing 42, 53, 4, i.e. everything but the first element of the list that LIST is.

Recursive structure of a list:
A list that LIST represents = (the first data, i.e., LIST->data) + (the list that LIST->next represents)

Printing a list

To write a recursive function to print out a linked list, we can start with the template below, and then fill in the two comment lines.

Base case
First we have to answer the question, "What should happen in the base case?" Another way of putting that is, "What should happen when we try to print an empty list?"

And the answer is, nothing! So we can leave that part blank in the code.

Recursive case
The second question is, "What do we do for each node in the list?"

That's easy too — you print out the node's data field in step 1!


void printlist(Node* L) 
{
  if (L == NULL) {
    // base case:
    //    depends on what you're doing
  } else {
    // recursive case:
    // step 1: Do something with L->data before the recursion

    // step 2: Recursion
    printlist(L->next);

    // step 3: Do something with L->data after the recursion
  }
}

This gives us the complete function:


void printlist(Node* L) {
  if (L == NULL) {
    // printing an empty list - nothing to do here!
  } else {
    cout << L->data << " ";
    printlist(L->next);
  }
}

See what I mean when I said that recursion can be really "natural" with linked lists?

Length()?

You can apply the same idea to get the length of a list. See the practice problems below.

add2back(d, L)

We may want to add a node at the back of a list. For this, we can think of the following function:


Node* add2back(int d, Node* L);

As with add2front() the function returns the pointer to the head (first) node of the updated list.

Iterative add2back()

One can implement add2back(d, L) as follows:

If the list is empty, return a new list containing a node with valud d.
Otherwise, go to the last node, and update its next to point to the new node.


Node* add2back(int d, Node* L)
{
  if (L == NULL)
  { 
    return new Node{d, NULL};
  }
  else
  { 
    // non-empty L case
    Node* last = L;
    while(last->next != NULL)
      last = last->next;

    // update last->next
    last->next = new Node{d, NULL};

    // The head of the list didn't change 
    return L;
  }
}

Statement `return new Node{d, NULL};`

This single line of code:


return new Node{d, NULL};

is a cool way to create, initialize, and return a node. This means the following:


Node* T = new Node;
T->data = d;
T->next = NULL;
return T;

Recursive add2back()

Adding to the back of list L is actually the same as adding to the back of list L->next Moreover, if L is empty, you are creating a new list containing a node with value d.


Node* add2back(int d, Node* L)
{    
  // base case: 
  //  L is an empty list 
  //  Note: if L is lastnode->next, L will also be NULL
  if (L == NULL)        
    return new Node{d, NULL};

  // recursive case:
  //  Tell the child list to add a node 
  //  Make sure that L->next is correct (especially when L is the lastnode)
  L->next = add2back(d, L->next);
  return L;                       
}

Deleting a list recursively

One place recursion really "shines" with linked lists is in deleting a list. The logic goes like this:

If the list is empty, there's nothing to delete.
Otherwise, do:
1. Use recursion to delete the child list first.
2. Then delete the head node.
Note the first node should be the last thing you delete (otherwise the next pointer in the first node, which has already been deleted, will be used; it will crash your program).

This leads to the following simple recursive function to delete a linked list:


void deletelist(Node* L)
{
  // Base case: if the list is empty, there is nothing to delete
  if (L == NULL) 
    return;  

  // Use recursion to delete all the second-to-last nodes
  deletelist(L->next);    
  delete L;               // Then delete the first node
}

Let me again emphasize that the purpose of recursion is not just to have shorter, more "elegant" functions (although that's nice), it's to get comfortable with multiple ways of programming so that you have more options available when solving a new problem.

Sometimes recursion seems "better" for the problem at hand, and sometimes a loop is a more natural solution. But remember that, since you're more used to writing loops now, you won't get a good feel for this until you've written many small recursive functions.

Mandatory Practice Problems

Write a recursive function to compute the length of a list:


int length(Node* );

Solution (drag your mouse):

int length(Node* L)
{
  // BASE CASE
  if (L == 0)
    return 0;

  // RECURSIVE CASE
  return 1 + length(L->next); 
}

Write a recursive function to check if the values in a list are in order.
```
bool inorder(Node* );
```
For example, if the list looks like
```
10 20 30 40 50
```
The function will return true. On the other hand, if the list looks like
```
10 20 30 50 40
```
The function will return false.
Solution