Heh. I guess I have an interview question to update. One of my quick warm-up questions is asking about what data structure to choose if inserting an element af

Heh. I guess I have an interview question to update. One of my quick warm-up questions is asking about what data structure to choose if inserting an element after an element you already have a reference to is a common operation that you want to optimize for. Of course, I don't consider there to be a right or wrong answer, but just make sure that people can intelligently discuss it. Some people start off with vec or the like, and then we discuss how fast that would be compared to a linked list. I generally stop after we get to the O(n) vs. O(1) comparison. But maybe if we have some extra time I should also talk about the tradeoff with actually traversing the list. After all, I suppose this is why things like gap buffers are popular for text editors, rather than linked lists.