> Interview Breeze

What is an immutable data structure?

Problem

Describe what an immutable data structure is. What are the benefits and limitations of an immutable data structure? When might you use an immutable data structure?

Solution

Definition

The word immutable refers to something that does not or is unable to change. In relation to data structures, immutability refers to the data structure being unable to change it's values after initialization. This is in contrast to the more common mutable data structure, which can change it's values after initialization. To illustrate the concept of immutability more concretely, we can look at a list as an example. A standard mutable list would look like so:

mutable_list = [0,1,2,3]
# since the list is mutable, we can change a value after initialization
mutable_list[1] = 9
print(mutable_list)
# [0,9,2,3]

If we were to have an immutable list (called a tuple in python), we would be unable to change any values after initialization. Look at this example:

my_tuple = (0,1,2,3)
my_tuple[1] = 9
# TypeError: 'tuple' object does not support item assignment

Advantages and disadvantages of immutable data structures

There are a number of advantages to immutable data structures, some of which are:

  1. They are inherently thread safe
  2. Many side effect related bugs are not an issue as values in the data structure cannot be changed after initialization
  3. They are often times easier to implement due to not having to deal with side effects caused by updates.
  4. Identity can be more straight forward. If the internal values of an object are the same in an immutable data structure, they can be treated as being identical to one another.

Some of the disadvantages of immutable data structures include:

  1. Any modification of an immutable data structure may require making a full copy of the whole data structure
  2. in a memory managed language, garbage collection can be an issue due to multiple allocations happening on updates to the data structure
  3. Lookups and updates can be expensive (greater than O(1) in most cases) unless you combine the immutable data structure with another data structure to speed up lookups (such as a mutable hash table)

Common use cases

There are a number of use cases for immutable data structures. For example, any time when a user would like to simplify their thread safety implementation (especially for reads), an immutable implementation of their data structure may be a good option. Another example is when a developer would like to make guarantees around the identity of objects. These are just two examples, and there are are many other examples of valid use cases where immutable data structures would be the ideal solution.