> But perhaps choosing how much of it to omit is key, too. It comes up less often, however. I can't think of a simple example.

An example of that is a linked list with no particular sort order. By not caring about maintaining an order the insertion appends or preprends a node and is O(1).

As soon as you have to maintain any additional invariant, the insertion cost goes up. Either directly or amortized.