The CPython deque is implemented as a doubly linked list (https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c#L33-L35).

It's noted in the code docs (https://github.com/python/cpython/blob/v3.8.1/Modules/_collectionsmodule.c#L1101-L1107) that insert is implemented in terms of rotate (i.e. insert at index n is equivalent to rotate(-n), appendLeft, rotate(n)). In general, this is O(n). While insertion at a node is O(1), traversing the list to find that node is O(n), so insertion in a deque in general is O(n)