Lisp 数据结构：list、cons、car、cdr

Lisp 数据结构：list、cons、car、cdr

在 Lisp 语言中，最基本也最重要的数据结构是“链表”（list）。它不是像数组那样连续存储的块，而是由一个个小单元“拼接”而成。这些小单元叫 cons，每个 cons 能装两个东西。通过把多个 cons 连起来，就形成了我们熟悉的列表。

理解 list、cons、car 和 cdr 四个概念，就等于掌握了 Lisp 的骨架。下面手把手教你用它们操作数据。

构造一个 cons 单元

输入 (cons a b) 创建一个包含两个部分的单元：前半部分叫 car，后半部分叫 cdr。

1. 打开你的 Lisp 环境（比如 SBCL、Clozure CL 或在线 REPL）。
2. 输入 (cons 1 2) 并回车。
3. 你会看到返回结果是 (1 . 2)。这个点表示这是一个“点对”（dotted pair），也就是最原始的 cons 单元。

注意：这不是一个普通列表！普通列表的最后一个 cdr 必须是空列表 ()，而这里 cdr 是数字 2。

创建真正的列表

Lisp 中的“列表”其实是 cons 单元连成的链，最后一个单元的 cdr 指向空列表 ()。

1. 输入 (cons 1 (cons 2 (cons 3 '())))。
2. 返回结果是 (1 2 3) —— 这才是标准的列表格式。

你也可以直接写 ' (1 2 3)，这是上述表达式的简写。单引号 ' 表示“不要计算后面的内容”，直接当作数据。

背后的结构其实是：

• 第一个 cons：car = 1, cdr = (2 . (3 . ()))
• 第二个 cons：car = 2, cdr = (3 . ())
• 第三个 cons：car = 3, cdr = ()

取出列表的第一个元素：car

调用 car 获取列表或 cons 的第一个部分。

1. 定义一个变量保存列表：(defvar my-list '(a b c))。
2. 输入 (car my-list)。
3. 返回 a。

无论 my-list 是 (a b c) 还是 (a . b)，car 都只取最前面那个值。

⚠️ 如果对空列表 () 使用 car，会报错。务必确保列表非空。

获取除第一个外的剩余部分：cdr

调用 cdr 获取列表去掉第一个元素后的剩余部分。

1. 继续使用上面的 my-list。
2. 输入 (cdr my-list)。
3. 返回 (b c)。

注意：cdr 返回的是一个新列表（或 cons），不是单个元素。

再试一次：(cdr '(b c)) 返回 (c)；再对结果用 cdr：(cdr '(c)) 返回 ()。

如果原始结构是点对，比如 (cons 1 2)，那么 (cdr '(1 . 2)) 直接返回 2（不是列表）。

组合使用：遍历列表

你可以用 car 和 cdr 一步步“拆解”整个列表。

假设列表为 '(x y z)：

1. (car list) → x
2. (car (cdr list)) → y
3. (car (cdr (cdr list))) → z
4. (cdr (cdr (cdr list))) → ()

为了方便，Lisp 提供了快捷写法：

• (cadr x) 等价于 (car (cdr x))
• (caddr x) 等价于 (car (cdr (cdr x)))
• 最多支持到 cddddr（四个 d）

但初学时建议先用完整写法，避免混淆。

判断是否为列表

不是所有 cons 都是合法列表。合法列表必须满足：每个 cdr 要么是另一个 cons，要么是 ()。

1. 输入 (listp '(1 2 3)) → 返回 T（真）。
2. 输入 (listp '(1 . 2)) → 返回 NIL（假）。
3. 输入 (listp '()) → 返回 T（空列表也是列表）。

实际例子：实现自己的 length 函数

不用内置的 length，自己用 car/cdr 写一个：

(defun my-length (lst)
  (if (null lst)
      0
      (+ 1 (my-length (cdr lst)))))

执行过程：

1. 调用 (my-length '(a b c))
2. lst 非空 → 计算 (+ 1 (my-length '(b c)))
3. 递归下去，直到 (my-length '()) 返回 0
4. 最终结果：1 + 1 + 1 + 0 = 3

这里的关键是：每次用 cdr 缩短列表，用 null（等价于检查是否为 ()）判断结束条件。

常见错误与注意事项

动手练习

1. 构造一个包含三个数字的列表，使用三次 cons 和 '()。
2. 取出该列表的第二个元素，只用 car 和 cdr（不许用 cadr）。
3. 写出表达式，判断 (cons 1 (cons 2 3)) 是否为合法列表。
4. 修改 my-length 函数，让它也能安全处理点对（提示：用 consp 判断是否为 cons 单元）。

做完这些，你就真正掌握了 Lisp 的核心数据结构。