Ah, I was assuming foolishly that we were talking about removing or inserting only at the head or the tail. All the more reason to be more detailed in a writeup

Ah, I was assuming foolishly that we were talking about removing or inserting only at the head or the tail. All the more reason to be more detailed in a writeup than simply "Performance: O(n)" :)