Programming in Emacs Lisp
9. How Lists are Implemented
In Lisp, atoms are recorded in a straightforward fashion; if the
implementation is not straightforward in practice, it is, nonetheless,
straightforward in theory. The atom `rose', for example, is
recorded as the four contiguous letters `r', `o', `s',
`e'. A list, on the other hand, is kept differently. The mechanism
is equally simple, but it takes a moment to get used to the idea. A
list is kept using a series of pairs of pointers. In the series, the
first pointer in each pair points to an atom or to another list, and the
second pointer in each pair points to the next pair, or to the symbol
nil, which marks the end of the list.
A pointer itself is quite simply the electronic address of what is
pointed to. Hence, a list is kept as a series of electronic addresses.