The C++ std::deque usually uses blocks that are big enough not to worry about memory concerns. The linked list has bad performance because you have tiny blocks

The C++ std::deque usually uses blocks that are big enough not to worry about memory concerns. The linked list has bad performance because you have tiny blocks of memory, but blocks of 256 objects are usually big enough that they are contiguous for all practical purposes (paging, allocation, and caching). Libc++, the library associated with clang and the LLVM project, uses a block of 4096 objects in its deque. This is an alternative that has been shown in the literature many times before, and it works well for certain access patterns, but is a major waste of resources for others. Yours in particular is great when you are pushing/popping both sides equally. The C++ standard deque is made for unknown but unequal directions of push/pop (while still having ~O(1) random access) with 50/50 ratio of push and pop.