According to this documentation, the rotate method of collections.deque has a linear time complexity. That is, for a collections.deque object d, d.rotate(k), takes O(k) time. Why is this the case?
collections.deque is an implementation of a doubly linked list. Shouldn't it be possible to move the first k elements of the deque to the end of the deque just by changing a constant number of references (assuming k is no larger than n, the total number of elements in the deque)? If that is possible, d.rotate(k) can be done in constant time, O(1), so why isn't d.rotate(k) done in O(1)?
P.S. The assumption that k <= n is reasonable because that is the case in the most common usages.