Yes, but when you alter 1 element of a list L, then L must be iterated (simply because it changed), so componentShouldUpdate() will return true for L. As a consequence, all elements of L will be checked. But you only changed one!
If you change the elements in a set, you need to re-evaluate how that set is rendered. Wether you leave it to the elements to decide if they are to be altered, or have that logic in the set-handling code, the book-keeping (and related CPU time) still needs to occur?
Either way, the proof is in the pudding: React is so insanely faster for this specific case than all other approaches.
Certainly the Virtual DOM is one way to let you declaratively write to the DOM and not worry about change tracking yourself. But it's not the most efficient way.
Unfortunately this sort of thing has never been implemented in JavaScript (that I can find) so currently the Virtual DOM is probably our least worst choice, at the moment.
In an ideal system, Components receive props, modify internal state, and render idempotently based on these. The PureRender mixin is a way of saying "yes, this component conforms to the above constraints".
Unfortunately, it's not always the case that the naive way of writing a Component will comply with the PureRender restrictions, so it's not enabled by default. It's not difficult, 99% of the time, to alter a Component to work properly with only minimal changes, and they aren't changes that make the Component code more confusing.
ComponentShouldUpdate is a way of applying tree-trimming logic that React could not automatically know. Business logic and the like. When a Component implements componentShouldUpdate and returns false, it will prevent any children of that component being iterated in that loop. Ideally, componentShouldUpdate should just returning a Boolean value from state, rather than calculating it each time.