Data structures in lisp

Question

I have a simple problem: to collect objects into a list and traverse this list backwards. Seems pretty easy but this code is a part of high-loaded computation. It is pretty natural to use conses because it takes O(1) on adding a new element and on sequential access. But what do i have to do if I need an effective double-linked list for traversing it easily in both directions? Use (reverse)? It takes O(n) memory and time, so actually it will take O(n^2) in my case (which is really bad). Use (last) or (append)? The same story: O(n). I do not really understand where to find (except the source code) any info on computational complexity of standard library functions. Is it implementation dependent? And what do I have to do for implementation of various standard data structures? Is there any guides on using conses effectively?

Answer 1

If you use Common Lisp, you can use vectors instead. Vectors can have a fill-pointer and/or can be adjustable. So you can use vector-push to add elements to a vector. The fill-pointer will grow. If the vector is adjustable, then it will also made larger if necessary. Since vectors are one-dimensional arrays you can access the elements with an index as you like.

See the options to MAKE-ARRAY to create such a vector.

VECTOR-PUSH and VECTOR-PUSH-EXTEND are the functions to add elements.

Answer 2

If you do the (reverse) once and then traverse the reversed list in sequential order, the total should just be O(2n) time (O(n) for the setup, and then another O(n) to traverse) and O(n) memory.

A doubly-linked list is not terribly complicated. As you know, a list is made of cons cells where the car points to the object than the cdr points to the next cons cell in the list.

One way to do a doubly-linked list is to instead have the cdr point to another cons cell whose cdr points to the next cons cell in the list and whose car points to the previous cons cell in the list. Then you use cddr to move forward and cdar to move back.

I don't know that the standard library functions have any guaranteed complexity. Unless the specification specifies, it would be implementation-defined.