Recursive Implementation of Linked Lists

A linked list is a naturally recursive structure.
- The linked list is a pointer to a node.
- Each node contains a pointer to a node.
- Ergo, each node contains a linked list.
However, the sublists do not have a size data member, so they are not exactly LinkedList objects.

Implement member functions in two parts.

The first function is public and non-recursive.

    Type Function(parameters)
    {
    //  Do special things...

    //  Call second function, passing head of list

        Function(head, parameters);

    //  Do more special things...
    }

The second function is private and recursive.

    Type Function(LinkedListNode* node, parameters)
    {
        if (condition)
        {

        //  Handle non-recursive case...

        }
        else
        {

        //  Handle recursive case...

            return Function(node->next, parameters);
        }
    }

Example - recurlinkedlist.h

Return to Lectures page

This page was last modified on Apr 6, 2001

URL: http://people.hsc.edu/faculty-staff/robbk/Coms262/Lectures/RecursiveLinkedLists.html