我有一個簡單的問題：將對象收集到列表中並向後遍歷此列表。看起來很容易，但是這個代碼是高負載計算的一部分。使用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