Deques, Sets and Ordered Maps

Use deques for fast work at both ends, sets for instant membership checks, and ordered maps for sorted keys, with Python examples and a complexity table.

• Beginner
• 15 min read
• 4 objectives

Before this lessonLesson 6: Stacks and Queues

You already know stacks, queues and hash tables. This lesson covers three close relatives that show up constantly in real code: the deque (double-ended queue), the set, and the ordered map. None of them is new magic. Each is a familiar structure with a specific promise about which operations are fast.

Knowing these promises is what lets you replace an O(n) line of code with an O(1) one, often by changing a single word.

Why a list is a poor queue

A Python list is a dynamic array. Adding or removing at the end is O(1), but removing from the front shifts every other element one slot left, which is O(n). A queue that pops from the front a million times becomes painfully slow.

import time
from collections import deque

n = 100_000
items = list(range(n))
start = time.perf_counter()
while items:
    items.pop(0)          # O(n) each time
list_time = time.perf_counter() - start

dq = deque(range(n))
start = time.perf_counter()
while dq:
    dq.popleft()          # O(1) each time
deque_time = time.perf_counter() - start

print("deque is faster:", deque_time < list_time)

deque is faster: True

The deque: fast at both ends

A collections.deque is built from linked blocks of slots, so it can grow and shrink at either end in O(1). Use it for queues, for breadth-first search, and for "last N items" buffers. The trade-off: indexing into the middle (dq[i]) is O(n), so it is not a replacement for a list when you need random access.

from collections import deque

dq = deque(["b", "c"])
dq.appendleft("a")
dq.append("d")
print(dq)
print(dq.popleft(), dq.pop())
dq.rotate(1)
print(dq)

deque(['a', 'b', 'c', 'd'])
a d
deque(['c', 'b'])

Passing maxlen creates a bounded buffer: when it is full, adding on one side silently drops an item from the other. This is perfect for "keep the last 3 log lines" or a moving average.

from collections import deque

recent = deque(maxlen=3)
for line in ["boot", "login ada", "view orders", "logout ada", "login lin"]:
    recent.append(line)
print(list(recent))

def moving_average(values, k):
    window, total, out = deque(), 0, []
    for v in values:
        window.append(v)
        total += v
        if len(window) > k:
            total -= window.popleft()
        if len(window) == k:
            out.append(total / k)
    return out

print(moving_average([10, 20, 30, 40, 50], 3))

['view orders', 'logout ada', 'login lin']
[20.0, 30.0, 40.0]

Sets: a hash table with only keys

A set stores unique values with no order guarantee. Internally it is a hash table that keeps keys but no values, so x in s, add and remove are O(1) on average. The same check on a list is O(n).

seen = set()
emails = ["ada@x.io", "lin@x.io", "ada@x.io", "sam@x.io", "lin@x.io"]
dupes = []
for e in emails:
    if e in seen:
        dupes.append(e)
    else:
        seen.add(e)
print(sorted(seen))
print(dupes)

['ada@x.io', 'lin@x.io', 'sam@x.io']
['ada@x.io', 'lin@x.io']

Sets also support set algebra, which turns many loops into one readable line.

python_devs = {"ada", "lin", "sam", "kai"}
java_devs = {"sam", "kai", "zoe"}

print(sorted(python_devs & java_devs))   # intersection
print(sorted(python_devs | java_devs))   # union
print(sorted(python_devs - java_devs))   # difference
print(sorted(python_devs ^ java_devs))   # in exactly one
print({"ada", "lin"} <= python_devs)      # subset

['kai', 'sam']
['ada', 'kai', 'lin', 'sam', 'zoe']
['ada', 'lin']
['ada', 'lin', 'zoe']
True

Ordered maps: two different meanings

"Ordered map" means two different things, and mixing them up causes bugs.

• Insertion-ordered: keys come back in the order you added them. Python's dict has guaranteed this since Python 3.7, and JavaScript's Map does too. Lookups are still O(1) hashing.
• Sorted: keys always come back in sorted order, and you can ask for the smallest key, the next key after x, or all keys in a range. Java's TreeMap and C++'s std::map do this with a balanced tree, so operations are O(log n).

Python's standard library has no sorted map. A common approach is to keep a sorted list of keys with the bisect module, which finds positions with binary search in O(log n). Inserting still shifts elements (O(n)), which is fine for thousands of keys. For large workloads, the third-party sortedcontainers package provides SortedDict.

import bisect

class SortedMap:
    def __init__(self):
        self.keys, self.vals = [], {}
    def put(self, k, v):
        if k not in self.vals:
            bisect.insort(self.keys, k)
        self.vals[k] = v
    def floor(self, k):
        """Largest key <= k, or None."""
        i = bisect.bisect_right(self.keys, k)
        return self.keys[i - 1] if i else None
    def range(self, lo, hi):
        i = bisect.bisect_left(self.keys, lo)
        j = bisect.bisect_right(self.keys, hi)
        return [(k, self.vals[k]) for k in self.keys[i:j]]

prices = SortedMap()
for day, p in [(5, 110), (1, 100), (9, 130), (3, 105)]:
    prices.put(day, p)
print(prices.keys)
print(prices.floor(4))
print(prices.range(2, 6))

[1, 3, 5, 9]
3
[(3, 105), (5, 110)]

The floor query ("what was the price on or before day 4?") is exactly what a hash map cannot answer quickly, because hashing scatters keys with no notion of order.

Choosing the right container

Structure          Add/remove ends   Lookup by key/value   Middle access   Ordered?
list (array)       end O(1), front O(n)   x in list O(n)    O(1) index      insertion
deque              both ends O(1)     x in dq O(n)          O(n)            insertion
set                add/remove O(1)*   x in s O(1)*          n/a             no
dict               put/del O(1)*      d[k] O(1)*            n/a             insertion
sorted map (tree)  put/del O(log n)   get O(log n)          floor/range O(log n)  sorted

* average case; worst case O(n) with many hash collisions

Recap

• Use deque whenever you add or remove at the front; list.pop(0) is O(n).
• deque(maxlen=k) gives a ready-made sliding buffer.
• Sets give O(1) average membership tests plus union, intersection and difference.
• Python dicts keep insertion order; sorted maps keep key order and support floor and range queries in O(log n).
• Choose a container by the operations you perform most often.

# Write your solution here