12 Sequences, Arrays, and Vectors

Recall that the sequence type is the union of five other Lisp types: lists, double-linked lists, vectors, bit vectors, and strings. In other words, any list is a sequence, any dllist is a sequence, any vector is a sequence, any bit vector is a sequence, and any string is a sequence. The common property that all sequences have is that each is an ordered collection of elements.

An array is a single primitive object that has a slot for each elements. All the elements are accessible in constant time, but the length of an existing array cannot be changed. Strings, vectors, and bit vectors are the three types of arrays.

A list (or dllist) is a sequence of elements, but it is not a single primitive object; it is made of cons cells, one cell per element. Finding the nth element requires looking through n cons cells, so elements farther from the beginning of the list take longer to access. But it is possible to add elements to the list, or remove elements.

The following diagram shows the relationship between these types:

          ___________________________________
         |                                   |
         |          Sequence                 |
         |  ______   ______________________  |
         | |      | |                      | |
         | | List | |         Array        | |
         | |      | |  ________   _______  | |
         | |______| | |        | |       | | |
         |          | | Vector | | String| | |
         |  ______  | |________| |_______| | |
         | |      | |  __________________  | |
         | | DL-  | | |                  | | |
         | | List | | |    Bit Vector    | | |
         | |______| | |__________________| | |
         |          |______________________| |
         |___________________________________|

The elements of vectors, lists and dllists may be any Lisp objects. The elements of strings are all characters. The elements of bit vectors are the numbers 0 and 1.