Lisp中的列表并不是一个原子类型;它们是从cons cells中构造的。一个cons cell是表示一个有序对的数据对象。也即,它具有两个槽,每个槽持有 或引用某些Lisp对象。其中一个槽被称为car,而别一个被称为cdr。(这些名字是惯例所为,请参考Cons Cell类型.)cdr读作“could-er.”
当我们说“这个cons cell的car是”时,我们指的是它的car槽当前所持有的任意对象,cdr亦同。
一个列表是一系列的cons cell“链接在一起,”因此每个cell指向下一个cons cell。列表中的每个元素都有一个cons cell。根据惯例,cons cell的car持有列表
元素,而cdr则指向下一个cons cell。最后一个cons cell的cdr是nil。car与cdr的这种不对称完全是一种惯例;在cons cell这个层面上,
car和cdr槽具有相同的特性。
由于nil是存放在列表中的最后一个cons cell的cdr的惯例值,我们称这种列表为真列表。
在Lisp中,我们将nil既当作符号,又当作列表;它是一个不具有任何元素的列表。为方便起见,符号nil可以被理解以nil为cdr(同样nil
是其cdr)。因此,真列表的cdr总是一个真列表。
如果列表最后一个cons cell的cdr是其他値,即不是nil也不是其他的cons cell,由于其打印表示将使用‘.’,我们称这种结构为点分列表。这里有另
外一种可能:某些cons cell的cdr可以指向列表中前面的cons cell。我们将这种结构成为circular list。
在某些情况下,列表是真列表、循环列表或点分列表并不重要,如果程序不深入查看列表的最后一个cons cell,它不用在意。然而,某些操作列表的函数要求真列表,如果是点分列表, 它将报错。而大多数尝试查找链表结尾的函数在处理循环列表时将产生无穷循环。
由于大多数cons cell都作为列表的一部分。列表结构这个短语用来指任何由cons cell构造出的结构。
任一非空真列表l的cdr是一个包含除了第一个元素的所有元素的列表。
关于cons cell的读取和打印语法以及列表的“盒子和箭头”图示,请参考See Cons Cell类型.。