The data structure of Python deque

✅ Key points of Python deque

1. Structure

• Made of many fixed-size blocks (small arrays) (block = 64 slots)
• Blocks are connected with a doubly linked list
• Each block is a C array (continuous memory), so access inside the block is fast

2. Time complexity

• append / appendleft / pop / popleft → O(1) (only moves head/tail block)
• deque[i] → fast near the edges, slower in the middle (must walk through blocks)
• Unlike list[i], which is true O(1) random access

🔹 Simple example (assume block size = 4)

from collections import deque
dq = deque()

Insert some elements:

Get Yen's Coding Journal’s stories in your inbox
Join Medium for free to get updates from this writer.
Remember me for faster sign in
dq.extend(['A','B','C','D','E','F'])

Internal idea:

Block1: [A, B, C, D]
Block2: [E, F, _, _]

Operation 1: dq.popleft()

Remove A
Block1: [_, B, C, D]
#           ^ head  
Block2: [E, F, _, _]
#              ^ tail

👉 Just move the head pointer, no shifting needed → O(1)

Operation 2: dq[5]

Index 5 # → the 5th element
5 // 4 = 1 # → in Block2
5 % 4 = 1 # → Block2[1] = F

👉 Found F, but CPython must walk to Block2 → fast near edges, slower in the middle.

✨ One-sentence summary

• deque = blocks (small arrays) + doubly linked list
• Best for operations at both ends (O(1))
• Not good for random indexing (middle elements are slower)