It depends on the implementation. Python's deque, for example, is implemented as a two-level data structure; a circularly linked list of blocks. If you've got

It depends on the implementation. Python's deque, for example, is implemented as a two-level data structure; a circularly linked list of blocks. If you've got page-sized blocks, then your deque can be sufficiently local for most cases. It introduces a little extra logic, and you'll want to keep around a spare block to prevent thrashing memory if you repeatedly push/pop at the block boundary, but it's often worth the pain if the data structure is anywhere near a hot loop.