Next: Dotted Pair Notation, Up: Cons Cell Type [Contents][Index]

#### 2.3.6.1 Drawing Lists as Box Diagrams

A list can be illustrated by a diagram in which the cons cells are shown as pairs of boxes, like dominoes. (The Lisp reader cannot read such an illustration; unlike the textual notation, which can be understood by both humans and computers, the box illustrations can be understood only by humans.) This picture represents the three-element list `(rose violet buttercup)`:

        --- ---      --- ---      --- ---
       |   |   |--> |   |   |--> |   |   |--> nil
        --- ---      --- ---      --- ---
         |            |            |
         |            |            |
          --> rose     --> violet   --> buttercup

In this diagram, each box represents a slot that can hold or refer to any Lisp object. Each pair of boxes represents a cons cell. Each arrow represents a reference to a Lisp object, either an atom or another cons cell.

In this example, the first box, which holds the CAR of the first cons cell, refers to or holds `rose` (a symbol). The second box, holding the CDR of the first cons cell, refers to the next pair of boxes, the second cons cell. The CAR of the second cons cell is `violet`, and its CDR is the third cons cell. The CDR of the third (and last) cons cell is `nil`.

Here is another diagram of the same list, `(rose violet buttercup)`, sketched in a different manner:

     ---------------       ----------------       -------------------
    | car   | cdr   |     | car    | cdr   |     | car       | cdr   |
    | rose  |   o-------->| violet |   o-------->| buttercup |  nil  |
    |       |       |     |        |       |     |           |       |
     ---------------       ----------------       -------------------

A list with no elements in it is the empty list; it is identical to the symbol `nil`. In other words, `nil` is both a symbol and a list.

Here is the list `(A ())`, or equivalently `(A nil)`, depicted with boxes and arrows:

        --- ---      --- ---
       |   |   |--> |   |   |--> nil
        --- ---      --- ---
         |            |
         |            |
          --> A        --> nil

Here is a more complex illustration, showing the three-element list, `((pine needles) oak maple)`, the first element of which is a two-element list:

        --- ---      --- ---      --- ---
       |   |   |--> |   |   |--> |   |   |--> nil
        --- ---      --- ---      --- ---
         |            |            |
         |            |            |
         |             --> oak      --> maple
         |
         |     --- ---      --- ---
          --> |   |   |--> |   |   |--> nil
               --- ---      --- ---
                |            |
                |            |
                 --> pine     --> needles

The same list represented in the second box notation looks like this:

     --------------       --------------       --------------
    | car   | cdr  |     | car   | cdr  |     | car   | cdr  |
    |   o   |   o------->| oak   |   o------->| maple |  nil |
    |   |   |      |     |       |      |     |       |      |
     -- | ---------       --------------       --------------
        |
        |
        |        --------------       ----------------
        |       | car   | cdr  |     | car     | cdr  |
         ------>| pine  |   o------->| needles |  nil |
                |       |      |     |         |      |
                 --------------       ----------------

Next: Dotted Pair Notation, Up: Cons Cell Type [Contents][Index]