What's the approach for handling lists that allows for optimized traversal?

What exactly are you looking for? A data structure? An algorithm? A library?

If you need an optimized traversal, what would be wrong with …ahem… inversing a list and working with this inversed copy?

I don’t recall exactly what I discovered, but I believe it is possible to declare “optimized” lists. By default, lists consist of [variable, pointer to next variable], which can be slow to iterate over.

Optimized for what? Random access? Traversal? There is no such thing as “optimized for everything” stuff.

Well. Linked lists are done this way (this description is extremely simplified though.) This is the fastest possible data structure to iterate over. It might be slow at random access, concatenation, whatever else, but the fast iterating is the reason these lists ever exist.

You really should make up you mind about what are you after.

Sorry if this isn’t clear; I believe it’s Erlang vectors, or something like that.
O(1) vs. O(n) to traverse them.

O(1) to traverse anything is obviously impossible.

Traversal can’t be O(1) cause its like, traversal of all items. Do you want access by index (like array[12] in C syntax)? How do you want to add elements to your collection? What type of elements do you want to store? Do you want to access it concurrently from different processes? Is it write once structure? Do you want to associate elements with keys?

Describe the problem in the detail, please. Erlang and Elixir have a lot of different structures for different use-cases. If you want something similar to cpp vectors, then you want lists, tuples, binaries or :arrays, depending on what exactly you want to do with it

list = [1, 2, 3, 4, 5] Enum.at(list, 3)
O(n) to traverse

Its called “access by index”. “To traverse” means “to iterate over all elements”.

So if you want constant access by index, you need tuples, binaries or atomics, depending on your problem. You can even use integers to store byte arrays. But all these data structures are O(n) when an element is changed or added

There is also :array module for O(ln n) for access and change by index. You can also use maps for similar performance. There is also :queue module for queues, etc

Thanks everyone,
I just found what I was looking for

For iteration of n elements, linked lists are O(n), but then so is a tuple.

On real computers, the actual iteration performance of a linked-list will be dominated by the runtime layout of its cells. A large list composed of cons cells scattered irregularly around the process heap will be substantially slower to iterate than an array, as prefetch won’t hit the L1 cache as often. A list with its cons cells laid out contiguously will do much better, but still loses on L1 cache density. And even a contiguous list causes stalls as the next cell is unknown until this cell’s next pointer is visible (speculative execution helps here, but it typically helps array iteration a lot more).

Linked lists are, in theory, one of the worst data structures for modern computer architectures.

In practice, large linked lists are reasonably rare, GC compaction may bring cells closer together and its possible a few BIFs may result in contiguous cons cells anyway. If iteration is all you need, lists are still fine. Also, iterating tuples is a bit weird in Elixir. And lists are immutable and elegant.

As a side note, the code the JIT produces for the list iteration looks better than the code it produces for tuple iteration, assuming the caller also checks tuple-size before accessing the element. The lack of cross-module optimisation means the size check is done twice and more branches are also taken on the happy path.