3 ms·

How does a dequeue improve the situation with cache locality versus a linked list?

• blibble 4y ago
  it's typically implemented as an array (e.g. circular buffer)
• zwkrt 4y ago
  Mosty dequeues are implemented under the hood with arrays. A linked list usually requires a heap allocation for each element. This is speaking in generalities though, since you could have an “alternatively implemented dequeue or a linked list entirely on the stack.
• klyrs 4y ago
  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.
• Shorel 4y ago
  It is usually implemented as linked arrays. For example, arrays of 16 or 64 elements, if it grows over that size, new arrays or vectors are used underneath. Two consecutive elements are probably in the same array, and that helps with cache locality.