2.1 Lists as recursive ADTs

Motivation

Lists are the first place where recursion becomes part of the data itself, not merely a programming technique. An array notation such as [3, 6, 4] shows the elements, but it hides the decomposition that drives the algorithms in this unit. A list is either empty, or it consists of one head element followed by a tail that is itself a list. After one head is handled, exactly the same problem remains on a shorter list.

This viewpoint separates two questions that programmers often mix together. The abstract data type specifies what construction and observation mean. The representation decides whether those operations copy an array, follow a pointer, or share existing storage. Client functions such as length, indexing, display, and concatenation should depend on the abstract contract, not on the fields chosen by the implementation.

The same recursive discipline appears in the accompanying recursion tutorial: identify a stopping test, give a direct answer for the end case, and make every recursive call on a genuinely smaller input. The list tail supplies that smaller input without requiring an arbitrary split.

Definitions

The public interface in the lecture can be expressed as an opaque C handle. Client code knows the declarations but cannot inspect struct listCDT:

typedef struct listCDT *listADT;
typedef int listElementT;

listADT EmptyList(void);
int ListIsEmpty(listADT list);
listADT CreateList(listElementT head, listADT tail);
listElementT ListHead(listADT list);
listADT ListTail(listADT list);

The operations have precise domains. EmptyList() returns a valid list of length zero. ListIsEmpty(list) is defined for every valid list. CreateList(head, tail) requires tail to be a valid finite list and returns a non-empty list. ListHead(list) and ListTail(list) require list to be non-empty: the empty list has neither a head nor a tail. For a constructed list, the observer laws are

Two further observations distinguish the recursive cases: ListIsEmpty(EmptyList()) returns true, whereas ListIsEmpty(CreateList(h, t)) returns false. These are value-level ADT facts; the interface promises no pointer-identity test and does not require clients to know how the empty value is encoded.

These laws also settle an important type distinction. The head is one element; the tail is another list. A head may itself be a list only when the chosen element type is a list type, as in a nested list.

This definition exposes the base and progress obligations for recursive code. The empty list is the base case. In the recursive case, passing ListTail(list) decreases length by exactly one. Testing for emptiness must happen before either observer is called.

The two standard length implementations use the same invariant:

int ListLength(listADT list) {
   if (ListIsEmpty(list)) {
      return 0;
   }
   return 1 + ListLength(ListTail(list));
}

int ListLengthIterative(listADT list) {
   int count = 0;
   for (listADT cursor = list;
        !ListIsEmpty(cursor);
        cursor = ListTail(cursor)) {
      count++;
   }
   return count;
}

The recursive version records pending additions in call frames. The iterative version records the processed-prefix length in count and the unprocessed suffix in cursor.

Both implementations can be justified without mentioning representation fields. For recursive length, the empty branch returns the value required by the length definition. In a non-empty call, assume the recursive result is the correct length of the tail; adding one then accounts for the current head and proves the returned length is correct. For the loop, let original denote the input list. At the start of every iteration,

Initially no cell has been counted. One iteration increments count and removes exactly one head from cursor, so the equality is preserved. When cursor is empty, its length is zero and the invariant says that count is the original length. The proof also explains why advancing by anything other than the current tail would need a different invariant.

Theorem / Proposition

The statement concerns structural recursion on a finite, well-formed, acyclic list. An arbitrary pointer cycle is not such a list and is outside this ADT contract.

The constant-time premise matters. It describes the linked representation, or any representation whose observers do not copy the remaining suffix. If ListTail constructs a copied array suffix, the same source-level recursion still terminates but no longer has this linear-time bound.

Proof sketch or proof idea

For the termination theorem, use list length as a non-negative integer variant. The empty-list branch returns directly. Every non-empty recursive call receives the tail, whose length is one less. A strictly decreasing sequence of non-negative integers cannot continue forever, so a call starting with length $n$ reaches length zero after exactly $n$ tail steps.

For the traversal theorem, prove the visit count by induction on $n$. A list of length zero contains no cell and the base call processes none. Assume a traversal processes each cell of every tail of length $n-1$ exactly once. A list of length $n$ processes its head once, then invokes the traversal on its tail of length $n-1$. The induction hypothesis accounts for every remaining cell once, so the total is $1+(n-1)=n$, with neither omission nor duplication.

Under the stated RAM model, there are constants $a,b>0$ such that every non-empty frame costs between $a$ and $b$, apart from its recursive call. Thus $T(n)=T(n-1)+\Theta(1)$, with $T(0)=\Theta(1)$, and summing the $n$ per-cell costs gives $T(n)=\Theta(n)$. Before the base call returns, one frame for every suffix length $n,n-1,\ldots,0$ is live. The maximum depth is $n+1=\Theta(n)$. This is a property of the straightforward implementation; the proof does not assume a compiler performs tail-call elimination.

Worked examples

CreateList(3, CreateList(4, CreateList(5, EmptyList())))

ListLength([3, 4, 5])
= 1 + ListLength([4, 5])
= 1 + (1 + ListLength([5]))
= 1 + (1 + (1 + ListLength([])))
= 1 + (1 + (1 + 0))
= 3

NthElement uses zero-based indexing and requires 0 ≤ n ≤ ListLength(list) - 1. Under that precondition every observer call is on a non-empty list, so no recovery policy has to be invented:

listElementT NthElement(listADT list, int n) {
   if (n == 0) {
      return ListHead(list);
   }
   return NthElement(ListTail(list), n - 1);
}

NthElement([6, 9, 5, 2, 3], 3)
-> NthElement([9, 5, 2, 3], 2)
-> NthElement([5, 2, 3], 1)
-> NthElement([2, 3], 0)
-> ListHead([2, 3]) = 2

Displaying a list needs a wrapper for brackets and a recursive helper for elements. The helper prints a separator only when the tail is non-empty:

void RecDisplayList(listADT list) {
   if (!ListIsEmpty(list)) {
      printf("%d", ListHead(list));
      listADT tail = ListTail(list);
      if (!ListIsEmpty(tail)) {
         printf(", ");
      }
      RecDisplayList(tail);
   }
}

void DisplayList(listADT list) {
   printf("[");
   RecDisplayList(list);
   printf("]\n");
}

The helper has a useful output contract: it writes the elements of its input in order, separated by comma-space, but writes no outer brackets. The empty input writes nothing. On a non-empty input it writes the head, writes a separator exactly when another element follows, and delegates the remaining sequence to the tail call. Induction on length proves both ordering and the absence of a trailing separator. The wrapper can therefore handle an empty or non-empty list uniformly.

Concatenation keeps the order of the first list by rebuilding its cells during the return path:

listADT ListConcat(listADT list1, listADT list2) {
   if (ListIsEmpty(list1)) {
      return list2;
   }
   return CreateList(ListHead(list1),
                     ListConcat(ListTail(list1), list2));
}

Its abstract postcondition is that every element of list1 appears first in its original order, followed by every element of list2 in its original order. The result consequently has the sum of the two input lengths. The empty branch satisfies that contract directly. A non-empty branch preserves the first head and applies the same contract to the shorter first tail; reconstruction during unwinding restores all earlier heads in order. This reasoning depends only on the ADT laws. Sharing is an implementation consequence discussed below, not part of the abstract concatenation result.

CreateList(4, ListConcat([2, 6], [5, 7]))
CreateList(4, CreateList(2, ListConcat([6], [5, 7])))
CreateList(4, CreateList(2, CreateList(6, ListConcat([], [5, 7]))))
CreateList(4, CreateList(2, CreateList(6, [5, 7])))
[4, 2, 6, 5, 7]

Representation, sharing, and ownership

An array representation may store a pointer to contiguous elements plus a count. The lecture's array-style CreateList allocates a larger array and copies the complete tail, so creating a head in front of an $n$-element tail takes $\Theta(n)$ time and space. An array tail may be represented as a view, but then the backing allocation and its lifetime must be tracked separately.

A recursive linked representation mirrors the ADT directly:

struct listCDT {
   listElementT head;
   listADT tail;
};

With EmptyList() represented by NULL, a non-empty CreateList allocates one cell, stores the head and existing tail handle, and takes constant time. ListHead, ListTail, and ListIsEmpty are also constant-time observers.

Sharing changes the ownership obligation, not the abstract list value. Under this interface, lists should be treated as immutable: changing a shared cell could silently change several logical lists. Every allocated cell must remain alive while any list handle can reach it. The lecture interface specifies no destructor, reference counting, or mutation policy, so this note does not invent one.

Interface boundary. C passes the listADT handle by value. Any future operation intended to replace the caller's head handle would therefore have to return the new handle or receive caller-visible indirection such as a listADT *. The source decks do not define mutation or deletion operations; none are assumed here.

Common mistakes

• Treating ListTail(list) as an element rather than a list.
• Calling ListHead or ListTail before ruling out the empty list.
• Using an invalid or negative index with NthElement and then trying to hide the contract violation with a successful process exit.
• Writing a recursive call on the original list, so the length measure does not decrease.
• Claiming that every recursive traversal is linear without checking the cost of ListTail in the chosen representation.
• Assuming concatenation copies both inputs; the linked implementation rebuilds the first spine and shares the second.
• Freeing a shared tail while another list handle can still reach it.
• Confusing a returned list handle with an in-place update of the caller's handle.

Summary

A list has a recursive contract: empty, or one head followed by a list-valued tail. That contract supplies both the end case and the smaller recursive input. For finite, well-formed, acyclic lists, structural recursion on successive tails terminates; under constant-time observers, a full straightforward traversal takes linear time and linear call-stack depth. NthElement, display, and concatenation are direct applications of the same pattern. The ADT fixes their meanings, while array or linked representation choices determine copying, sharing, cost, and lifetime obligations.

Exercises

1. Write the recursive idea for DisplayList: print the head, then display the tail if it is not empty.
2. Explain why ListConcat(list1, list2) should return list2 when list1 is empty.
3. Compare the cost of CreateList under an array representation and under a linked representation.

Solutions