Thinking Recursively with Java

10.1. Representing Strings as Linked Lists

From your first days as a Java programmer, you have almost certainly had the opportunity to work with the String class, which is defined in the java.lang package but also supported at the language level through the existence of string constants and the concatenation operator. Java's String class is a wonderful tool, primarily because its definition allows you to think about strings as abstract entities without having to be aware of their internal representation. Most other languages, including popular object-oriented languages like C++, force programmers to know much more about the underlying representation of string data, which inevitably makes strings more difficult to use.

As it happens, strings in Java are represented internally as arrays of characters, just as they are in most languages. That design decision, however, was not the only possible choice. Because strings in Java are defined by their abstract behavior and not their representation, the designers of the java.lang package could have chosen other representations as long as those representations could provide the same functionality. This section considers the possibility of representing strings as a linked list of characters, not because such a representation makes sense from a pragmatic point of view, but because linked lists provide a simple illustration of a recursive data structure.

A linked list is a data structure that represents an ordered list of elements (just as ...