Map [1]
Access: O(log n) Search: O(log n) Insertion: O(n) for < 32 elements, O(log n) for >= 32 elements [2] Deletion: O(n) for < 32 elements, O(log n) for >= 32 elements Caveats:
- With fewer than 32 elements, a Map is a list of tuples sorted by keys
- With 32 and more elements, a Map is a Hash Array Mapped Trie (HAMT)
- Maps are unordered, allow any key type, but disallow duplicate keys
List [3]
Access: O(n) Search: O(n) Insertion: O(1) for prepending, otherwise O(n) Deletion: O(1) if first element, otherwise O(n) Caveats:
- Lists are not arrays as in other languages, but single-linked lists
Keyword [4]
Access: O(n) Search: O(n) Insertion: O(n) Deletion: O(n)
Tuple [5]
Access: O(1) Search: O(n) Insertion: O(n) Deletion: O(n) Caveats:
- Tuples are better for reading, whereas Lists are better for traversals
- Avoid using tuples as a collection
- (i.e. avoid Tuple.append/2, Tuple.insert_at/2, or Tuple.delete_at/2)
(erlang) array [6]
Access: O(log n) [7] Search: O(log n) Insertion: O(log n) Deletion: O(log n) Caveats:
- An array is a trie of small tuples, with a smaller memory overhead to Lists
- Deletion is actually a replace with the default value and creates sparse arrays
- For real deletion, use sparse_to_list/1, which has O(n) complexity
MapSet [8]
Same complexities as 'Map'
Partial overview of complexities Discussion of :array Does Elixir have persistent data structures? Way to get O(1) access/set Sequences by sasajuric