I just saw a talk by the great David Nolan (@swannodette) on how software architecture, namely the MVC design pattern, is “like the great pyramids,” which take a long time and lots of manpower, and how we as software architects haven’t yet discovered the arch. The DOM, as he succinctly put it, is fundamentally about documents, not about events or views.

He introduced to me an idea that I’ve known about since Comp Sci 101, but never gave much thought to or truly understood the power of: immutable data structures.

Consider a linked list. Each node contains whatever information it needs, and then optionally has a pointer to another node:

In the example above, the node A points to node B, which in turn points to node C. If we consider the linked list as a whole, A essentially is, in order, [A B C].

But suppose we built a new node, X, which also points to B:

Now we have two values, [X B C], and our original, unmodified [A B C].

Think about this for a second. We have two lists, each containing three nodes, but the two lists combined take up only 33% more space than either one.

This may not seem all that amazing (yet), but what if, instead of linked lists, we looked at arrays? Consider an array with four elements, each which point to another array of four elements, each pointing to an array of four elements, each which point to an array containing four values:

We can traverse this tree and, with only four calculations, can find any of 256 values. (For more about this, read up on Phil Bagwell’s hash array mapped trees.)

Okay, so that’s a fast way to find some values, big deal.

But what if we wanted to modify one of those values? Applying the same idea as we did to linked lists, we can do so by modifying only the four arrays we traverse to get to the value we’re changing:

Further, since this is essentially storing only the diffs, we end up storing only a small percent more for what is essentially a completely different array of values.

React utilizes this to create a virtual DOM, making updating views blazing fast, take up less space, and easy to go back in history (undo).

This probably isn’t mind blowing for some of you, but somehow I’ve gone the last ten or so years without realizing how powerful a data structure so simple can be.