c++recursionsingly-linked-list

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


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


Solution

  • 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)
        { // 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)
        { // see if next node is last node
            return getLast(current->next);
        }
        else
        { // found last node. return it
            return current;
        }
    }
    

    Note that both approaches require that the list at current not be empty.