Mutable vs Immutable datastructures are part of most of the programming languages so it is important to know how they behave, their strong and weak points.
This blog is divided into two parts and it will talk about difference between the two parts. First part majorly deals with the benefits and drawbacks of immutability. Lets start Mutable vs Immutable datastructures
Immutable are objects which cannot be modified after they are created. For example some of primitive data structure like integer, float, Boolean are immutable in almost all of the language. Strings are immutable in many languages (Not in C++ though). Non primitive data types such as arrays are generally mutable. Let’s discuss some pros and cons of immutability.
Benefits of Immutability:
In a multi threaded environment using immutable object can lead to thread safe code. As the variable once created cannot be changed so chances of mutation are very low.
Object once created cannot be modified, so easy to predict its state.
Testing Becomes easy
As there are no side effects so testing becomes easy.
Comparing two immutable objects are very cheap operation. One can simply compare the objects address and then tell whether they are equal or not.
Draw back of Immutability:
Immutability works fine with primitive object. In case of non-primitive data structure like array it becomes overhead to copy data from one location to another location.
For example: Adding an element of 10^5 elements array would take large amount of time. We need to create a new instance by copying the existing values and add new value to it. This will certainly be both more memory intensive and more computationally challenging than mutating existing array.
There is not full proof solution for this but we can implement a strategy called “structural sharing”, which yields much less memory overhead than expected.
So after using the structure sharing and trie data structure we can reduce the update in the array from linear time (copying array from one location to another) to somewhere between linear time to constant time.
In the next blog we will see how we will use structure sharing to minimise memory and computation footprint while retaining the property of immutability.
Read about Best practics in programming.