Lisp 中的列表并非基本数据类型,它们由 cons cells 构建而成(see Cons 单元与列表类型)。Cons 单元是表示有序对的数据对象。它有两个槽位(slot),每个槽位 holds存储 或 refers to引用 某个 Lisp 对象。一个槽位称为 CAR,另一个槽位称为 CDR。(这些是传统名称;详见 Cons 单元与列表类型。)CDR 读作 “could-er”。
我们说 “这个 cons 单元的 CAR 是” 其 CAR 槽位当前存储的对象,CDR 同理。
列表是一连串链式相连的 cons 单元,每个单元指向下一个。列表中的每个元素对应一个 cons 单元。按照惯例,cons 单元的 CAR 存放列表元素,CDR 用于将列表串联起来 (CAR 与 CDR 之间的这种不对称完全是约定俗成;在 cons 单元层面,两个槽位的性质是相似的。)因此,列表中每个 cons 单元的 CDR 槽位都指向其后的下一个 cons 单元。
同样按照惯例,列表最后一个 cons 单元的 CDR 为 nil。我们把这种以 nil 结尾的结构称为 proper list正规列表5。在 Emacs Lisp 中,符号 nil 既是一个符号,也是空列表。为方便起见,符号 nil 被视为其 CAR 和 CDR 均为 nil。
因此,正规列表的 CDR 永远是正规列表。非空正规列表的 CDR 是一个去掉第一个元素后、剩余所有元素组成的正规列表。
如果列表最后一个 cons 单元的 CDR 不是 nil,我们称这种结构为 dotted list点列表,因为它的打印表示会使用点对表示法(see 点对表示法)。
还有一种可能,某个 cons 单元的 CDR 指向列表中之前的某个 cons 单元,我们称这种结构为 circular list循环列表。
在某些用途中,列表是正规、循环还是点列表并不重要。如果程序不会遍历到最后一个 cons 单元的 CDR,它就不会关心这些区别。但是,许多操作列表的函数要求输入必须是正规列表,若传入点列表会报错。大多数试图查找列表末尾的函数,在传入循环列表时会进入无限循环。你可以使用下一节介绍的函数 proper-list-p(see proper-list-p)来判断一个列表是否为正规列表。
由于绝大多数 cons 单元都用作列表的一部分,我们把所有由 cons 单元构成的结构统称为 list structure列表结构。