Looking at the cpython implementation of a deque, it appears that reverse() is written to be O(n) time. It seems to be just as slow in practice:
from collections import deque
import time
n = 100000
l = [i for i in range(n)]
d = deque(l)
start = time.time()
for _ in range(n):
l.reverse()
print("list reversal", time.time() - start)
start = time.time()
for _ in range(n):
d.reverse()
print("deque reversal", time.time() - start)
gives an output of:
list reversal 3.3866615295410156
deque reversal 4.0808796882629395
My question is, why isn't it O(1)? Couldn't you reverse a doubly linked list by setting a boolean to determine which side it considers the head? Is there a reason it needs to swap every item's location in memory?