lisp - 循环列表有什么用处(在 Lisp 或 Scheme 中)？

Question

我注意到 Scheme 和 Lisp(我猜)支持循环列表，并且我在 C/C++ 中使用循环列表来“简化”元素的插入和删除，但它们有什么用？

Scheme 确保它们可以被构建和处理，但是为了什么？

是否有需要循环或尾循环的“ killer 级”数据结构？

Answer 1

说它支持“循环列表”有点过分了。您可以在 Lisp 中构建各种循环数据结构。就像在许多编程语言中一样。 Lisp 在这方面并没有太多特别之处。拿起你典型的“算法和数据结构”一书，实现任何循环数据结构:图形、环……一些 Lisp 提供的是可以打印和读取循环数据结构。对此的支持是因为在典型的 Lisp 编程领域中，循环数据结构很常见:解析器、关系表达式、单词网络、计划……

数据结构包含循环是很常见的。真正的“循环列表”并不经常使用。例如，考虑一个运行任务并在一段时间后切换到下一个任务的任务调度程序。任务列表可以是循环的，以便在“最后”任务之后调度程序执行“第一个”任务。事实上，没有“最后”和“第一个”之分——它只是一个循环的任务列表，调度程序无休止地运行它们。您还可以在窗口系统中拥有一个窗口列表，并使用一些键盘命令切换到下一个窗口。窗口列表可以是圆形的。

当您需要廉价的 next 操作并且数据结构的大小事先未知时，列表很有用。您始终可以将另一个节点添加到列表中或从列表中删除一个节点。列表的通常实现使得获取下一个节点和添加/删除项目变得便宜。从数组中获取下一个元素也相对简单(增加索引，在最后一个索引处转到第一个索引)，但添加/删除元素通常需要更昂贵的移位操作。

此外，由于构建循环数据结构很容易，因此可以在交互式编程中这样做。如果您随后使用内置例程打印循环数据结构，那么打印机是否可以处理它是个好主意，否则它可能会永远打印循环列表...