我有一个简单的问题：将对象收集到列表中并向后遍历此列表。看起来很容易，但是这个代码是高负载计算的一部分。使用conses很自然，因为它需要O（1）添加新元素和顺序访问。但是如果我需要一个有效的双向链表来双向轻松地遍历它，我该怎么办？使用（反向）？它需要O（n）的内存和时间，所以实际上在我的情况下它会占用O（n^2）（这非常糟糕）。使用（上一个）或（追加）？同样的故事：O（n）。我不明白在哪里可以找到（源代码除外）任何有关标准库函数计算复杂性的信息。它依赖于实现吗？我需要做些什么来实现各种标准数据结构？有没有关于有效使用conses的指南？lisp中的数据结构
如果您使用Common Lisp，则可以使用矢量。矢量可以有一个填充指针和/或可以调整。因此，您可以使用矢量推送将元素添加到矢量。填充指针会增长。如果矢量是可调整的，那么如果需要的话它也会变大。由于矢量是一维数组，因此您可以根据需要使用索引访问元素。
查看MAKE-ARRAY创建这样一个向量的选项。
VECTOR-PUSH和VECTOR-PUSH-EXTEND是添加元素的函数。
正如我所见**：可调**只允许**调整阵列**。当** vector-push **达到数组边界时，它会返回** NIL **而不是自动分配额外的空间。 – lumberjack 2011-04-23 18:40:24
好的。现在我明白了。 ** VECTOR-PUSH-EXTEND **在恒定的时间和空间中扩展矢量。谢谢。 – lumberjack 2011-04-23 19:54:07
如果您先执行(reverse)一次，然后按顺序遍历反向列表，则总数应该是O（2n）时间（O（n）为设置，然后是另一个O（n）遍历）和O（n）存储器。
一个双向链表不是非常复杂。如你所知，一个清单是由汽车指向对象的cons cell组成的，而cdr指向列表中的下一个cons cell。
一种方式做一个双向链表是不是有CDR点到另一个缺点细胞，其CDR点到列表中的下一个cons单元，其车点到以前的利弊细胞在列表。然后你使用cddr向前移动，cdar移回。
我不知道，标准库函数有任何保障的复杂性。除非规范说明，否则将由实现定义。
[纯功能数据结构]（http://www.amazon.com/dp/0521663504/）可能是一个很好的阅读。 – 2011-04-23 13:27:03