Note that std::deque is not really implemented as a linked list, as it would prevent O(1) random access. The classical implementation is as a dynamic array of pointers to fixed size chunks.