The Computational Cost of Fundamental Data Structures in Elixir

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 article explores the computational cost of all fundamental data structures in Elixir, based on official documentation and community benchmarks. By the end, you will have a reference guide for choosing the right structure for every situation.

1. Lists ([]) — Linked Lists

Implementation and Memory

Lists in Elixir are linked lists. Each element is stored in a [head | tail] pair, where head is the value and tail is a reference to the rest of the list. This representation is called a cons cell.

Visually, the list [1, 2, 3] is stored as [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 the list from the start to the index
Prepend (`[x	list]`)	O(1)
Append (list ++ [x])	O(n)	Traverses the entire list to the end
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 official documentation is explicit: "Because of their cons-cell representation, prepending an element to a list is always fast (constant time), while appending becomes slower as the list grows (linear time). Furthermore, getting a list's length and accessing it by index are linear-time operations."【1†L1-L3】

When to Use

Lists are ideal for:

• Collections where insertion/removal happens at the head (head/tail pattern).
• Sequential processing with Enum.reduce, Enum.map, etc.
• Implementing stacks (LIFO).
• Recursion patterns that consume the list from front to back.

Avoid lists for:

• Random index access in large collections.
• Repeatedly appending elements at the tail (this yields O(n²)).
• Frequent searches for a specific element.

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. This means 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."【1†L5-L6】

When to Use

Tuples are ideal for:

• DP (dynamic programming) with indexed access.
• Returning multiple values from a function (e.g., {:ok, value}).
• Fixed-size groupings (2 to 4 elements).
• Replacing arrays in algorithms that need O(1) access.
• Error/success tags ({:error, reason}, {:ok, result}).

Avoid tuples for:

• Variable-size collections.
• Iteration with Enum (tuples do not implement the Enumerable protocol).
• Frequent updates (each put_elem copies the entire tuple).

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)	—

For maps with ≤32 keys, operations are effectively O(n), but this effect is negligible because n is small. For larger maps, the complexity is logarithmic.

When to Use

Maps are ideal for:

• Key-value storage with dynamic keys.
• Frequency counting (Enum.frequencies/1).
• In-memory cache.
• Associative data structures.
• Configuration with arbitrary keys.

Avoid maps for:

• Collections where order matters (maps do not guarantee order for >32 keys).
• Cases where keys are strictly known at compile time (use structs).

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).
• Small lists where order matters.
• Cases where duplicate keys are allowed.

Avoid keyword lists for:

• Frequent lookups in large collections (use maps).
• Performance-critical access.

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 compile-time validation.
• Structured pattern matching.
• Replacing Erlang records.

Avoid structs for:

• Data with dynamic keys.
• Generic collections.

6. Binaries and Strings (<<>> / "")

Implementation and Memory

Strings in Elixir are UTF-8 binaries, stored as contiguous byte sequences in memory. This is different from charlists.

Complexities

Operation	Complexity	Note
Concatenation (<>)	O(n + m)	But 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.

When to Use

Binaries are ideal for:

• Text processing and parsing.
• Binary pattern matching (very efficient).
• Incremental string construction (but prefer iolists).

Avoid binaries for:

• Repeated concatenation with <> in loops (use iolists).
• Frequent index access.

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). Use iolists to build large strings efficiently.

7. Queues (:queue)

Implementation and Memory

Erlang's :queue is a double-ended queue (deque) implemented as two lists (front and rear). Removal is amortized O(1).

Complexities

Operation	Complexity
Enqueue (:queue.in/2)	O(1) amortized
Dequeue (:queue.out/1)	O(1) amortized
Length (:queue.len/1)	O(1)

When to Use

Queues are ideal for:

• FIFO processing (first-in, first-out).
• BFS (breadth-first search).
• Message buffers.
• Task scheduling.

Avoid queues for:

• Small collections (<100 items) — a list is simpler and faster.

8. Functional Arrays (:array)

Implementation and Memory

Erlang's :array is a functional tree with a leaf size of 10. Access is O(log₁₀(n)), which is significantly better than the O(n) of lists, but worse than the O(1) of tuples.

Complexities

Operation	Complexity
Access (:array.get/2)	O(log₁₀(n))
Update (:array.set/3)	O(log₁₀(n))
Size (:array.size/1)	O(1)

When to Use

Arrays are ideal for:

• Large collections with frequent random access.
• Cases where tuples are too large to copy on every update.

Avoid arrays for:

• Small collections (tuples are faster).
• Cases where O(1) is mandatory.

9. MapSet

Implementation and Memory

MapSet is a set implemented on top of a map. It offers set operations (union, intersection, difference) with logarithmic complexity.

Complexities

Operation	Complexity
Insert (MapSet.put/2)	O(log n)
Search (MapSet.member?/2)	O(log n)
Remove (MapSet.delete/2)	O(log n)
Union (MapSet.union/2)	O(n log n)
Intersection (MapSet.intersection/2)	O(n log n)

When to Use

MapSet is ideal for:

• Deduplication (Enum.uniq/1 uses MapSet internally).
• Set operations.
• Frequent membership checks.

Avoid MapSet when:

• Order matters (use :ordsets or Enum.uniq/1).
• Performance-critical with small sets (a list may suffice).

10. Ranges (1..10)

Implementation and Memory

Ranges store only two integers (start and end) and an optional step. They occupy constant memory, regardless of the sequence size.

Complexities

Operation	Complexity
Creation	O(1)
Membership (in)	O(1)
Iteration (Enum.map)	O(n)

When to Use

Ranges are ideal for:

• Integer sequences in loops and iterations.
• Cases where memory is a concern.
• Interval checks.

11. ETS (Erlang Term Storage)

Implementation and Memory

ETS is an in-memory table shareable between processes. It is the only structure in Erlang/Elixir that offers truly O(1) access for reads.

Complexities

Operation	Complexity
Read (:ets.lookup/2)	O(1)
Insert (:ets.insert/2)	O(1)
Remove (:ets.delete/2)	O(1)
Search (:ets.match/2)	O(n)

When to Use

ETS is ideal for:

• Shared cache between processes.
• Counters and metrics.
• Fast lookup tables.
• Global state that needs to be read by many processes.

Avoid ETS for:

• Data that fits comfortably in a process.
• Cases where immutability is required.

12. :gb_trees and :gb_sets

Implementation and Memory

gb_trees are general balanced trees (General Balanced Trees) by Andersson. gb_sets are ordered sets implemented on top of gb_trees.

Complexities

Operation	Complexity
Access/Insert/Remove	O(log n)
Ordered iteration	O(n)

When to Use

gb_trees/gb_sets are ideal for:

• Ordered maps (which Elixir lacks natively).
• Ordered sets.
• Range queries.

13. :ordsets

Implementation and Memory

:ordsets are ordered lists that represent sets. They are more efficient than regular lists for set operations on medium sizes.

Complexities

Operation	Complexity
Insert	O(n)
Search	O(n)
Union	O(n)
Intersection	O(n)

When to Use

:ordsets are ideal for:

• Small to medium sets (up to ~1000 elements).
• Cases where order matters.

General 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
Keyword [k: v]	O(n)	O(1)	O(n)	O(n)	Function options
Struct %M{}	O(1)	—	—	O(1)	Domain modeling
Binary <<>>	O(n)	O(n+m)	—	O(1)	Text, parsing
:queue	—	O(1)*	O(1)*	O(1)	FIFO, BFS
:array	O(log₁₀ n)	O(log₁₀ n)	O(log₁₀ n)	O(1)	Large arrays
MapSet	O(log n)	O(log n)	O(log n)	O(1)	Sets
Range	O(1)	—	—	O(1)	Integer sequences
ETS	O(1)	O(1)	O(1)	O(1)	Shared cache
:gb_trees	O(log n)	O(log n)	O(log n)	O(1)	Ordered maps
:ordsets	O(n)	O(n)	O(n)	O(n)	Small ordered sets

*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.

Conclusion

Understanding the computational cost of data structures is essential for writing efficient Elixir code. The fundamental rule is:

• Lists ([]) are linked lists: O(1) for prepend, O(n) for indexed access and append.
• Tuples ({}) are static arrays: O(1) for access, O(n) for update.
• Maps (%{}) are HAMTs: O(log n) for key operations.
• Binaries (<<>>) are contiguous byte sequences: efficient for parsing, but beware of concatenation in loops.
• ETS is the only structure with true O(1), but it is mutable and shared between processes.

Choosing the right structure can be the difference between an algorithm that runs in milliseconds and one that takes hours. In Elixir, where immutability is the rule, this choice is even more critical. Use lists for sequential flow, tuples for indexed access, maps for associations, and iolists for efficient string building.

With this guide, you have the tools to make informed decisions and avoid the pitfalls that haunt even the most advanced language models.