COMP 210: Data Structures

Recursive Lists

There are several ways to think about and implement lists, including:

• Lists as arrays of contiguous elements (Example: ArrayList)
• Lists as references to chains of linked elements (Example: linked lists)
• Lists as recursive data structures

This page introduces the third way of thinking about lists.

Lists as Recursive Data Structures

The recursive definition of a list is that a list may be either:

• an empty list
• an initial element followed by the rest of the list (which is itself a list)

The initial element is often known as the head of the list. The sublist that contains everything after the head is often known as the tail. This way of defining lists is especially common in functional languages.

A recursive list is similar to a linked list, in that it consists of linked nodes. The difference is that, whereas the K_SimpleLL class, for example, represents a list as an outer shell containing the linked nodes, each node in a recursive list is itself the head of another list.

                    ________________________
                    | first                |
    Linked List  -> |   |                  |
                    |   v                  |
                    |  ---  ---  ---       |
                    |  | |->| |->| |->...  |
                    |  ---  ---  ---       |
                    |                      |
                    ------------------------

                
                      ---  ---  ---
    Recursive List -> | |->| |->| |->...
                      ---  ---  ---
                           ^    ^
                           |    |
                           |    recursive sub-sublist
                           |
                           recursive sublist

An empty list

In a recursive linked list, an empty list could be implemented as a node with null references for both the initial element and the rest of the list.

                _______________
 list ref  ---->|      |      |
                | null | null |
                |      |      |
                ---------------

A non-empty list

A non-empty recursive list contains a reference to the first element in the list and a reference to a list containing everything after the first list.

                head returns obj 1
                  |
                  |          tail returns next list ref
                __v_________  |  _____________
 list ref  ---->|     |    |  v  |     |     |
                |  *  |  --|---->| ... | ... |
                ---|--------     -------------
                   |
                   |  _________
                   -> | obj 1 |
                      ---------

Expanding that out to a list with 3 elements might look something like this:

        head1        tail1
          |           |   head2        tail2
          |           |     |           |  head3        tail3
        __v_________  |  ___v________   | ___v________   | _______________
   ---->|     |    |  v  |     |    |   v |     |    |   v |      |      |
        |  *  |  --|---->|  *  |  --|---->|  *  |  --|---->| null | null |
        ---|--------     ---|--------     ---|--------    ---------------
           |                |                |              
           |  _________     |  _________     |  _________  
           -> | obj 1 |     -> | obj 2 |     -> | obj 3 | 
              ---------        ---------        ---------