Common Lisp中列表可实现数组无法做到的结构共享的原理及示例是什么？

什么是结构共享 #

你提到的结构共享，指的是多个不同的列表对象可以复用同一段尾部子列表的内存空间，不需要对公共部分做完整拷贝，即可形成各自独立的逻辑结构。 #

列表支持结构共享的原理 #

Common Lisp的列表本质是单链表，每个节点由cons单元实现，仅存储当前节点值（car）和下一个节点的指针（cdr）。构造新列表时，仅需要新增少量头节点，尾部直接指向已有的列表即可，不需要拷贝原有列表的任何内容。

示例代码 #

;; 定义基础公共列表
(setf base-list '(b c d))

;; 构造两个新列表，仅新增头节点，尾部复用base-list
(setf list1 (cons 'a base-list))
(setf list2 (cons 'z base-list))

此时两个新列表的逻辑值分别为：

• list1：(a b c d)
• list2：(z b c d)

你可以通过eq验证结构共享的存在：
(eq (cdr list1) (cdr list2))返回值为T，说明两个列表去掉首元素后的剩余部分是完全相同的内存对象，没有被拷贝两份。
如果要截取已有列表的子序列，也可以直接复用结构：
(setf list3 (cdr list1))得到的(b c d)和base-list也是同一内存对象，零拷贝开销。 #

数组无法实现原生结构共享的原因 #

数组是连续存储的结构，访问元素依赖「首地址+偏移量」的计算逻辑：

1. 如果你需要基于已有数组#(b c d)构造新数组#(a b c d)，必须重新分配4个元素长度的连续内存，把原有3个元素全部拷贝到新内存的对应位置，再填入新增的首元素，无法复用原有数组的存储空间。
2. 即使部分语言实现了数组视图（带偏移量的数组包装对象），也仅能实现子数组的读取复用，无法基于视图在头部新增元素形成新的原生数组，和列表的结构共享能力完全不同。

结构共享的优势 #

在不可变数据的使用场景下，结构共享可以极大降低列表拼接、前缀添加、子序列截取的内存和时间开销，且天然不会修改原有列表，适合函数式编程和多线程场景。 #

内容的提问来源于stack exchange，提问作者Pedro Delfino