Linear time complexity describes work that grows proportionally with input size. In Elixir, list operations commonly have O(n) complexity because lists are singly linked and must be traversed. section 2.4.4
Recognize linear behavior in common list operations:
- length/1 traverses the entire list. section 2.4.4
- Enum.at/2 walks from the beginning to the requested position. section 2.4.4
- Replacing or inserting at an arbitrary position, appending, and concatenating lists generally require O(n) work. section 2.4.4
Choosing a collection
Use lists for dynamic, variable-sized collections and sequential processing. When direct access matters, prefer tuples, maps, or a higher-level data structure instead of repeatedly traversing a list. section 2.4.4
iex(3)> Enum.at(prime_numbers, 3) 7
Observe positional access with Enum.at/2; reaching the fourth element illustrates traversal from the list's beginning. section 2.4.4
