> > That's O(n), with many spurious insertions and deletions.
> 
> Any implementation is O(n).

For rotate() perhaps (but still, it can be more efficient in that it can
just move the list head once instead of repeatedly deleting and
inserting elements). But rotate_at() / rotate_after() can probably be
O(1), unless I'm missing something.

> > deques already allow rotating.
> 
> I agree that the rotation makes some sense for such collections as
> deque or OrderedDict (although it is easy implemented in user code).
> But there are no rotate_at() and rotate_after() in deque.

That's because a deque is not a mapping ;-) In other words, if a deque
was enough I'd be using a deque, not a OrderedDict.