1 基本概念与结构
1.1 列表与点对（Cons Cell）的关系
列表在Lisp中的底层实现基于“点对”（Cons Cell），这是一种小型的数据容器，包含两个字段，通常称为“车”（car）和“尾”（cdr）。每一个元素在链中由点对承载。
1.1.1 点对的定义：(cons x y)
点对通过 cons 函数创建，接收两个参数x和y，返回一个由两者构成的二元组。例如 (cons 1 2) 表示一个car为1、cdr为2的点对，书写为 (1 . 2)。点对本身可以嵌套，通过cdr指向另一个点对，从而构造更长链。
1.1.2 列表作为点对的链：nil 作为终止符
一个正规列表（Proper List）是由一系列点对组成的链表，每个点对的car保存元素，cdr指向下一个点对或空列表 nil。nil 既是空列表，也用作链的终止标记（类似空指针）。例如列表 (1 2 3) 底层表示为 (1 . (2 . (3 . nil)))。
1.2 列表的表示法
1.2.1 全括号表示法
最常用的书写形式是括号包围、元素空格分隔：(1 2 3)。这是Lisp阅读器（Reader）的默认语法，内部自动转换为点对链。
1.2.2 点对表示法（点对与列表的等价转换）
任何以点对书写的结构都可以转换为等价的列表形式。规则是：若一对括号内只有一个点号分隔car和cdr，且cdr不是点对或nil，则必须写成点对；若cdr是点对或nil，则可省略点号和额外括号。例如 (1 . (2 . 3)) 等价于 (1 2 . 3)（非正规列表），而 (1 . (2 . nil)) 等价于 (1 2)（正规列表）。这种转换有助于理解列表的底层结构。
1.3 列表的类型与特征
1.3.1 空列表 nil
nil 既是空列表，也是逻辑假。它没有任何元素，可以用 () 或 nil 表示。在点对链中作为终止符。
1.3.2 正规列表（Proper List）
正规列表的最后一个点对的cdr必须为 nil。例如 (a b c) 是正规的，因为最后一个点对为 (c . nil)。所有元素从左到右依次排列，可通过 car cdr 遍历。
1.3.3 非正规列表（Dotted List）
非正规列表的最后一个点对的cdr不是 nil，而是一个非列表值。例如 (a b . c)，其结构为 (a . (b . c))，末尾的cdr是符号c。非正规列表不具备链式终止符，不能通过标准列表操作（如 length）正常处理，通常只用于特定场景如关联列表的底层表示。
2 列表的创建与基本操作
2.1 列表的构造函数
2.1.1 list 函数
list 接收多个参数，返回一个包含这些参数的正规列表。例如 (list 1 2 3) → (1 2 3)。所有参数求值后放入列表。
2.1.2 quote（'）简写
通过 quote 或其简写单引号 ' 可以直接创建字面列表。例如 '(1 2 3) 等价于 (quote (1 2 3))，禁止对内部表达式求值。这是S-表达式的基本构造方式。
2.1.3 cons 构造
cons 将一个新元素添加到既有列表的前部。(cons 'x '(a b)) → (x a b)。构造过程就是创建一个新的点对，car为新元素，cdr为原列表。
2.2 列表的访问与分解
2.2.1 car 和 cdr
car 返回列表的第一个元素，cdr 返回除第一个元素以外的子列表。对空列表调用会引发错误。例如 (car '(a b c)) → a，(cdr '(a b c)) → (b c)。
2.2.2 first、second、third 等扩展
Common Lisp等方言提供了 first 到 tenth 等便捷函数，等价于嵌套 car 和 cdr。例如 (third '(a b c d)) 等价于 (car (cdr (cdr '(a b c d)))) → c。
2.2.3 nth 与 nthcdr
nth 返回指定索引（0为起始）的元素：(nth 2 '(a b c d)) → c。nthcdr 返回从指定索引开始的子列表：(nthcdr 2 '(a b c d)) → (c d)。
2.3 列表的修改（破坏性操作）
2.3.1 setcar 与 setcdr
setcar 修改点对的car字段，setcdr 修改cdr字段。例如 (setq lst '(1 2 3)) (setcar lst 0) 将列表变为 (0 2 3)。这些操作直接改变原列表结构，需要谨慎使用。
2.3.2 rplaca 与 rplacd
rplaca 和 rplacd 是名称更古老的变体，功能与 setcar、setcdr 相同。通常在现代方言中倾向于使用 setf 配合 car / cdr 来赋值。
2.3.3 注意事项：共享结构与副作用
破坏性操作可能导致多个变量共享同一列表时产生意外影响。例如 (setq a '(1 2 3)) (setq b a) (setcar a 0) 会同时改变b的值，因为b和a指向同一个点对。编程时应明确区分破坏性与非破坏性操作，如使用 copy-list 提前复制。
3 列表的常用函数与算法
3.1 列表长度与边界检测
3.1.1 length
length 返回列表中元素的个数（正规列表）。对非正规列表会报错。(length '(a b c)) → 3。
3.1.2 null 与 atom、listp
null 检查参数是否为 nil，即空列表；atom 检查参数是否为原子（非点对或nil）；listp 检查参数是否为列表（包括nil）。例如 (null nil) → t，(atom 'a) → t，(listp '(1 2)) → t。
3.1.3 endp
endp 专门用于检查列表是否为空，对非列表参数会报错。常用于递归遍历中的终止条件：(endp '(a b)) → nil。
3.2 列表的连接与分割
3.2.1 append 与 nconc
append 非破坏性地连接多个列表，返回新列表。(append '(1 2) '(3 4)) → (1 2 3 4)。nconc 破坏性地连接，将最后一个cdr指向下一个列表，原始列表被修改。
3.2.2 reverse 与 nreverse
reverse 返回原列表的反序副本，不修改原列表。nreverse 破坏性地反转（通常通过原地逆转指针实现），效率更高但会改变输入。
3.2.3 subseq 或 butlast 相关
subseq 取子序列（起始索引与可选结束索引），butlast 返回除最后一个元素之外的列表。例如 (subseq '(a b c d) 1 3) → (b c)，(butlast '(a b c)) → (a b)。
3.3 列表的搜索与映射
3.3.1 member、assoc 与 find
member 测试元素是否在列表中，返回从匹配位置开始的子列表；assoc 用于关联列表（由点对组成的列表），按键查找对应的点对；find 更通用，接受测试函数。例如 (member 'b '(a b c)) → (b c)。
3.3.2 mapcar、maplist、mapcan
mapcar 逐个对元素应用函数，返回结果列表。maplist 对每条cdr链应用函数。mapcan 类似于 mapcar 但结果列表通过 nconc 拼接（破坏性）。例如 (mapcar #'1+ '(1 2 3)) → (2 3 4)。
3.3.3 reduce 与排序（sort）
reduce 将二元函数累积应用于列表元素，例如 (reduce #'+ '(1 2 3)) → 6。sort 按比较函数对列表原地排序，返回排序后的列表（破坏性）。如 (sort '(3 1 2) #'<) → (1 2 3)。
3.4 列表的递归操作
3.4.1 递归遍历列表（深度优先）
经典递归模式：(defun traverse (lst) (if (null lst) nil (cons (process (car lst)) (traverse (cdr lst)))))。深度优先适用于嵌套列表：先处理car，再递归cdr。
3.4.2 递归构造列表
用 cons 在递归中逐步构建结果，如 (defun copy-tree (tree) (if (atom tree) tree (cons (copy-tree (car tree)) (copy-tree (cdr tree)))))。
3.4.3 树形列表（嵌套列表）处理
嵌套列表本质是一棵树，递归处理时需区分原子与列表。常见操作如 flatten：(defun flatten (lst) (cond ((null lst) nil) ((atom lst) (list lst)) (t (append (flatten (car lst)) (flatten (cdr lst))))))。
4 列表在Lisp中的特殊地位
4.1 代码即数据：列表作为S-表达式
4.1.1 宏与列表的互动
宏接受S-表达式（列表）形式的代码，在编译期进行变换后再执行。例如 (defmacro when (test &body body) (if ,test (progn ,@body)))` 利用列表拼接构建新表达式。列表提供了代码操作的灵活性。
4.1.2 自省与eval
eval 可以接受一个列表并将其作为代码执行。例如 (eval '(+ 1 2)) → 3。结合 quote 可动态构造程序，这是Lisp元编程的基础。
4.2 列表与函数式编程风格
4.2.1 递归替代循环
Lisp程序员常用递归遍历列表而非显式循环，尤其是Scheme等方言。例如用递归计算列表长度：(defun my-length (lst) (if (null lst) 0 (1+ (my-length (cdr lst)))))。
4.2.2 高阶函数操作列表
mapcar、filter（通常自定义或用 remove-if-not）、reduce 等将函数作为参数处理列表，符合函数式编程的“免副作用”理念。
4.3 列表与传统编程语言的数组对比
4.3.1 动态长度与不可变性偏好
列表长度可在运行时动态扩展，而数组通常固定大小。Lisp的纯函数式风格倾向于使用非破坏性操作（如 append）来避免副作用，即使牺牲性能。
4.3.2 性能考量（链式访问 vs 随机访问）
列表是单向链表，访问第n个元素需遍历n步（O(n)），而数组支持O(1)随机访问。列表的优势在于前部插入/删除（O(1)）和共享结构。对于大量数值计算，Lisp方言通常提供向量或数组作为替代。
5 列表的演进与变种
5.1 常见方言中的列表差异
5.1.1 Common Lisp
Common Lisp拥有最丰富的列表函数库，区分破坏性与非破坏性操作（如 nreverse vs reverse），并提供 loop 宏等迭代构造。列表是采用点对链的标准实现。
5.1.2 Scheme
Scheme的列表也是点对链，但语言更强调函数式纯度，破坏性操作（如 set-car!）命名规范但使用较少。Scheme的尾递归优化使得列表递归更高效。
5.1.3 Emacs Lisp
Emacs Lisp的列表行为与Common Lisp相似，但缺乏某些函数（如 mapcan 需要手动实现）。由于Emacs主要处理文本，列表广泛用于表示缓冲区内容、键绑定等。
5.1.4 Clojure（持久化列表与向量）
Clojure运行在JVM上，默认使用持久化数据结构。其列表（list）也是链表，但支持结构共享以提升效率。Clojure的向量（vector）更常用，提供O(log32 n)的随机访问。
5.2 列表的替代数据结构
5.2.1 向量（Vector）与数组（Array）
向量提供快速随机访问，可动态调整（如Common Lisp的 adjust-array）。在需要频繁索引或大量密集计算时，向量是列表的优选替代。
5.2.2 可变序列、队列与栈
列表本身可充当栈（push/pop）和队列（enqueue/dequeue 通常用 append 或 nconc，但效率不如专用实现）。更多方言提供 deque 或基于向量的队列。
5.2.3 惰性列表（Stream）
惰性列表（也称为流，Stream）只在需要时才计算元素。Scheme的 delay / force 或Common Lisp的 series 库支持惰性。Clojure的 lazy-seq 自动延迟。惰性列表允许表示无限序列，如自然数列表。