COMP 210: Data Structures
Recursive Lists
There are several ways to think about and implement lists, including:
- Lists as arrays of contiguous elements
- Lists as chains of linked elements
- Lists as recursive data structures
This page introduces the third way of thinking about lists.
Lists as Recursive Data Structures
One way to think about or define a list is as a recursive, linked data structure. 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 but the head element is sometimes known as the tail. This way of defining lists is especially common in functional languages,
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:
head tail
| | head2 tail2
| | | | head3
__v_________ | ___v________ | ___v________ _______________
---->| | | v | | | v | | | | | |
| * | --|---->| * | --|---->| * | --|--->| null | null |
---|-------- ---|-------- ---|-------- ---------------
| | |
| _________ | _________ | _________
-> | obj 1 | -> | obj 2 | -> | obj 3 |
--------- --------- ---------