4 ms·
Why is removing the first element repeatedly O(N^2) while removing the last one O(N)? Is it because its cheaper for the browser to remove things from the end of
by romellem 5y ago
Why is removing the first element repeatedly O(N^2) while removing the last one O(N)? Is it because its cheaper for the browser to remove things from the end of a NodeList rather than the front? (similar to how .pop() is cheaper than .shift() for larger arrays?)
- chrismorgan 5y agoOn reflection, “many” wasn’t the best word to use; “some” would be better. In the past, I believe that most or all browser implementations used array-like structures to do various things like this, and so removing the first element entailed shifting all the remaining elements, whereas popping from the end doesn’t require shifting any elements. More recently, I believe that most or all browser implementations have shifted to linked-list-like structures, with bad patterns like this being a cited reason. (I don’t know the full story by any means, but I’m inclined to be disappointed by the switch, because for most access patterns arrays aren’t a problem at all, and use less memory, sometimes even being a smidgeon faster. But although I suspect they’d have better typical performance and certainly better memory size, they have vastly worse worst-case performance, being approximately O(n) instead of O(1) for some operations.) Remember also when talking of NodeList like this that it’s a type for JavaScript to consume; what browsers use internally for representing their DOM is an implementation detail. A leaky one, certainly, in performance details like this and types like HTMLCollection and NodeList (especially live NodeLists), but an implementation detail nonetheless.