The Computational Cost of Fundamental Data Structures in Elixir
A Complete Guide to Performance, Complexity, and the Error That Haunts AI-Generated Code
Introduction
Choosing the right data structure is one of the most impactful decisions for program performance. In Elixir, this choice is even more crucial because the language relies on immutable and persistent structures, whose performance characteristics differ significantly from the mutable structures found in imperative languages like Python, Java, or C++.
Many developers coming from those languages make the mistake of assuming that [] in Elixir is an array with O(1) access. It is not. In Elixir, [] is a linked list, and index access is O(n). The closest equivalent to an array is the tuple ({}), which offers O(1) access.
This error is so pervasive that it has become a recurring failure mode in AI-generated Elixir code. An AI, trained predominantly on imperative languages, sees dp[j] in Python and mechanically translates it to Enum.at(dp, j) in Elixir, assuming O(1) access. The result is an algorithm that passes small tests but times out at scale.
This article is the definitive guide to the computational cost of every fundamental data structure in Elixir, based on the Erlang Efficiency Guide, official documentation, and community benchmarks. It is also a guide to avoiding the pitfalls that haunt both human developers and language models.
1. Lists ([]) — Linked Lists
Implementation and Memory
Lists in Elixir are singly-linked lists. Each element is stored in a cons cell [Head | Tail], where Head is the value and Tail is a pointer to the rest of the list. This structure is immutable and persistent: operations create new lists that share structure with the old ones.
Visual representation of [1, 2, 3]:
[1 | [2 | [3 | []]]]
Each cons cell occupies heap space with two pointers: one to the value and one to the next element.
Complexities
| Operation | Complexity | Note |
|---|---|---|
Index access (Enum.at/2) |
O(n) | Traverses from the head to the index |
| Prepend (`[x | list]`) | O(1) |
Append (list ++ [x]) |
O(n) | Traverses the entire left list |
Length (length/1) |
O(n) | Traverses the entire list to count |
| Insert at head | O(1) | — |
| Insert at tail | O(n) | — |
| Remove from head | O(1) | — |
| Remove from tail | O(n) | — |
Search (Enum.member?/2) |
O(n) | — |
The Erlang Efficiency Guide is explicit: "Lists can only be built starting from the end and attaching list elements at the beginning. If you use the ++ operator like this, the list will be copied."
Best Practices
DO: Build lists by prepending and reverse at the end.
%% Efficient: O(n) total
fib(N) -> fib(N, 0, 1, [0]).
fib(0, _Current, _Next, Fibs) -> lists:reverse(Fibs);
fib(N, Current, Next, Fibs) -> fib(N - 1, Next, Current + Next, [Next | Fibs]).
DO NOT: Append to the end inside a loop.
%% Inefficient: O(n²)
fib(N) -> fib(N, 0, 1, [0]).
fib(0, _Current, _Next, Fibs) -> Fibs;
fib(N, Current, Next, Fibs) -> fib(N - 1, Next, Current + Next, Fibs ++ [Next]).
2. Tuples ({}) — Static Arrays
Implementation and Memory
Tuples are stored contiguously in memory, like C arrays. Each element sits side by side, and the tuple's size is known upfront. Accessing any element is a constant-time operation.
Complexities
| Operation | Complexity | Note |
|---|---|---|
Index access (elem/2) |
O(1) | Direct memory access |
Size (tuple_size/1) |
O(1) | Size stored in the header |
Update (put_elem/3) |
O(n) | Creates a shallow copy of the entire tuple |
| Insert/remove | O(n) | Requires recreating the entire tuple |
The official documentation confirms: "Accessing any element takes constant time, but modifying a tuple, which produces a shallow copy, takes linear time."
The Golden Rule
If you need O(1) indexed access, use tuples. If you need insertion/removal at the head, use lists. This is the most important distinction for developers coming from imperative languages.
3. Maps (%{}) — Key-Value Stores
Implementation and Memory
Maps in Elixir are implemented as Hash Array Mapped Tries (HAMT) when they have more than 32 keys. With 32 keys or fewer, they are stored as sorted lists of key-value pairs.
Complexities
| Operation | Complexity | Note |
|---|---|---|
Access (map[key]) |
O(log n) | HAMT for >32 keys |
Insert (Map.put/3) |
O(log n) | — |
Remove (Map.delete/2) |
O(log n) | — |
Size (map_size/1) |
O(1) | — |
Search (Map.has_key?/2) |
O(log n) | — |
Small maps (≤32 keys) are ordered lists, which have O(n) access but with a small constant factor. When a map reaches 32 entries, it switches to a hash trie with O(log n) lookup.
When to Use
Maps are ideal for key-value storage with dynamic keys, frequency counting, and associative data structures. Avoid maps when order matters (maps do not guarantee order for >32 keys).
4. Keyword Lists ([key: value])
Implementation and Memory
Keyword lists are simply lists of {:atom, value} tuples. They share all the properties of lists.
Complexities
| Operation | Complexity |
|---|---|
Access (Keyword.get/3) |
O(n) |
| Insert (prepend) | O(1) |
Search (Keyword.has_key?/2) |
O(n) |
| Length | O(n) |
When to Use
Keyword lists are ideal for function options (especially as the last argument) and small lists where order matters. Avoid keyword lists for frequent lookups in large collections.
5. Structs (%Module{})
Implementation and Memory
Structs are maps with fixed keys (atoms) defined at compile time. Field access (struct.field) is an O(1) map lookup on the atom key.
Complexities
| Operation | Complexity |
|---|---|
Field access (struct.field) |
O(1) |
| Update (`%{struct | field: value}`) |
| Pattern matching | O(1) for individual fields |
When to Use
Structs are ideal for domain modeling with known fields, type guarantees, and structured pattern matching.
6. Binaries and Strings (<<>> / "")
Implementation and Memory
Strings in Elixir are UTF-8 binaries, stored as contiguous byte sequences in memory.
Complexities
| Operation | Complexity | Note |
|---|---|---|
Concatenation (<>) |
O(n + m) | Optimized by the VM for append |
Index access (String.at/2) |
O(n) | Must traverse the bytes |
Size (byte_size/1) |
O(1) | — |
Character length (String.length/1) |
O(n) | Must count graphemes |
| Binary pattern matching | O(1) per segment | Extremely efficient |
The Erlang VM optimizes concatenation when the left binary has free memory after its allocation. In that case, only the right binary is copied.
Iolists
Iolists are nested lists of binaries and bytes that can be converted into a final binary with IO.iodata_to_binary/1. Building an iolist is O(1) per element, and the final conversion is O(n). The Erlang community notes: "Io-lists are extremely easy to use and appending, prefixing or inserting data is inexpensive, as they only need changes to relatively short lists, without any data copying".
Use iolists for incremental string construction. Avoid repeated <> concatenation in loops, which is O(n²).
7. Queues (:queue)
Implementation and Memory
Erlang's :queue module provides double-ended FIFO queues implemented as two lists (front and rear). Removal is amortized O(1).
Complexities
The Erlang documentation is explicit: "All operations have an amortized O(1) running time, except all/2, any/2, delete/2, delete_r/2, filter/2, filtermap/2, fold/3, join/2, len/1, member/2, split/2 that have O(n)". The reason len/1 is O(n) is that queues do not store explicit length information to minimize garbage.
When to Use
Queues are ideal for FIFO processing, BFS, message buffers, and task scheduling. For small collections (<100 items), a plain list is simpler and equally fast.
8. Functional Arrays (:array)
Implementation and Memory
Erlang's :array is a functional tree with a branching factor of 10. The community knowledge is that array provides "O(Log N), where N is the size of the array, and if I recall, the tree has a branching factor of 10 to compromise between the speed of lookups and garbage generated when modifying it".
Complexities
| Operation | Complexity |
|---|---|
| Read | O(log₁₀ n) |
| Write | O(log₁₀ n) |
When to Use
Use array when you need random access but tuples are too large to copy on every update. The community recommendation is: "If the content is less static, then look into the array module for O(log n) read and write operations".
9. gb_trees and gb_sets — Balanced Trees
Implementation and Memory
gb_trees implements Prof. Arne Andersson's General Balanced Trees. These have no storage overhead compared to unbalanced binary trees, and their performance is generally better than AVL trees.
Complexities
Both provide O(log n) operations for access, insertion, and removal. The documentation states: "Behaviour is logarithmic (as it should be)".
When to Use
Use gb_trees when you need an ordered map (which Elixir lacks natively) or when you need to efficiently find minimum/maximum elements dynamically.
10. ETS — Truly O(1) Access
Implementation and Memory
ETS (Erlang Term Storage) is the only structure in Erlang/Elixir that offers truly O(1) access for reads and writes. It is a mutable hash table shared between processes.
Complexities
The ETS documentation states that for the set table type, lookup, insert, and delete are O(1). For ordered_set, access time is proportional to the logarithm of the number of objects stored. For bag and duplicate_bag, operations are proportional to the number of duplicate keys.
The community confirms: "ETS is probably the closest approximation to O(1) read/write that you'll get in Erlang, but it has another source of overhead: data is copied in and out of the table".
When to Use
Use ETS for shared caches, counters, and lookup tables that need to be read by many processes. The trade-off is that ETS is mutable and copies data on every operation.
The Complete Summary Table
| Structure | Access | Insert | Remove | Size | Ideal For |
|---|---|---|---|---|---|
List []
|
O(n) | O(1) prepend | O(1) head | O(n) | Stacks, sequential processing |
Tuple {}
|
O(1) | O(n) | O(n) | O(1) | Arrays, DP, multiple return |
Map %{}
|
O(log n) | O(log n) | O(log n) | O(1) | Dynamic key-value |
Queue :queue
|
— | O(1)* | O(1)* | O(n) | FIFO, BFS |
Array :array
|
O(log₁₀ n) | O(log₁₀ n) | O(log₁₀ n) | O(1) | Large arrays |
| gb_trees | O(log n) | O(log n) | O(log n) | O(1) | Ordered maps |
| gb_sets | O(log n) | O(log n) | O(log n) | O(1) | Ordered sets |
| ETS | O(1) | O(1) | O(1) | O(1) | Shared cache |
| Iolist | — | O(1) | — | O(n) | String building |
*Amortized.
The Common Mistake: Confusing Lists with Arrays
The confusion between [] (list) and arrays is the most frequent mistake made by developers coming from imperative languages, and also by language models that generate Elixir code. The classic symptom is translating an imperative loop that uses dp[j] into Enum.at(dp, j) and dp[j] = value into List.replace_at(dp, j, value), assuming both operations are O(1).
They are not. Enum.at/2 and List.replace_at/3 are O(n) on lists. Using them in a nested loop turns an O(n × k) algorithm into O(n × k²).
The fix is to use tuples for indexed DP. The efficient strategy is to rebuild the entire tuple in a single pass with Enum.map/2 followed by List.to_tuple/1, which is O(k) per row, resulting in O(n × k) overall.
Example: Corrected DP with Tuples
defmodule Solution do
@mod 1_000_000_007
def build_dp(n, k) do
# Initial row: i = 0 → dp[0] = 1, dp[j] = 0 for j > 0
# Use a TUPLE, not a list!
initial_dp =
0..k
|> Enum.map(fn j -> if j == 0, do: 1, else: 0 end)
|> List.to_tuple()
final_dp =
Enum.reduce(1..n, initial_dp, fn i, dp ->
max_j = min(i, k)
# Rebuild the entire tuple in one pass — O(k)
0..k
|> Enum.map(fn j ->
cond do
j == 0 -> 0
j > max_j -> 0
true -> (j * elem(dp, j) + elem(dp, j - 1)) |> rem(@mod)
end
end)
|> List.to_tuple()
end)
elem(final_dp, k)
end
end
This is the difference between an algorithm that runs in O(n × k²) and one that runs in O(n × k). For n = 1000 and k = 1000, the difference is a billion operations versus a million operations.
The Golden Rules from the Erlang Efficiency Guide
The Erlang Efficiency Guide and community wisdom converge on a few golden rules:
Profile before optimizing. The guide states: "You should never optimize before you profiled your code and found the bottlenecks".
Prepend, don't append. Lists are optimized for head operations. Build lists by prepending and reverse at the end.
Choose the right structure. Lists for sequential access, tuples for indexed access, maps for key-value, ETS for shared O(1) access.
Understand the cost model. The Erlang Cost Model provides a concise summary of all data structure complexities.
Use iolists for strings. Binary concatenation in loops is O(n²). Iolists are O(n) total.
Conclusion
The Erlang Efficiency Guide is not a list of micro-optimizations. It is a guide to thinking structurally about your data. The choice between a list and a tuple, a map and an ETS table, a queue and a gb_tree, is not a minor detail—it determines the asymptotic complexity of your algorithm.
The most important lesson is the one that connects directly to Elixir: [] is not an array. It is a linked list. If you need O(1) indexed access, use a tuple. If you need O(log n) key-value lookup, use a map. If you need O(1) shared access, use ETS. And if you need to build a large string efficiently, use an iolist.
The Erlang VM is a marvel of engineering, but it cannot compensate for the wrong data structure. As the Efficiency Guide says: "Efficient code is not always good code from the perspective of generality, ease of understanding and maintaining. Therefore programming becomes a balance act between generality and efficiency." Master the balance, and your Elixir code will be both correct and fast.
And for AI-generated code: never trust a complexity claim without verifying the underlying data structure. The list-vs-array error is not an edge case—it is a wake-up call.
Top comments (0)