How to make recursive singly linked list (C++)

Question

My book is asking me to make a recursive definition of a singly linked list. I have no idea at all how to do that. Can someone please help me out with a sample? Thanks

Answer 1

It's just like a normal linked list except the iteration is performed by recursion rather than loops.

First, a little light reading: What is recursion and when should I use it?

For example, a loop-based function to find the last node could be:

Node * getLast(Node * current)
{
    while (current->next == null)
    { // loop until no more nodes
        current = current.next;
    }
    return current; // return last node
}

While the recursive version only checks if the current node is the last and calls itself with the next node if there is a next node.

Node * getLast(Node * current)
{
    if (current->next == null)
    { // found last node. return it
        return current;
    }
    else
    { // see if next node is last node
        return getLast(current->next);
    }
}