11

In clojure lists grow from the left and vectors grow from the right, so:

user> (conj '(1 2 3) 4)
(4 1 2 3)

user> (conj [1 2 3] 4)
[1 2 3 4]

What's the most efficient method of inserting values both into the front and the back of a sequence?

2 Answers 2

19

You need a different data structure to support fast inserting at both start and end. See https://github.com/clojure/data.finger-tree

0
1

As I understand it, a sequence is just a generic data structure so it depends on the specific implementation you are working with.

For a data structure that supports random access (e.g. a vector), it should take constant time, O(1).

For a list, I would expect inserting at the front of the list with a cons operation to take constant time, but inserting to the back of the list will take O(n) since you have to traverse the entire structure to get to the end.

There is, of course, a lot of other data structures that can theoretically be a sequence (e.g. trees) that will have their own O(n) characteristics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.