Python collections: Counter, defaultdict, deque, namedtuple

Quick Answer

The collections module replaces the awkward parts of dict and list. Counter counts items without KeyError handling, defaultdict removes the 'if key not in d' line, deque gives O(1) removal from the front where list.pop(0) is O(n), and namedtuple gives tuples readable field names. The main trap is defaultdict: reading a missing key creates it, so a plain lookup can quietly grow your dictionary while you are debugging.

What plain dict and list leave you doing by hand

Almost every Python program eventually writes the same three or four blocks of boilerplate. You count things, so you write a check for whether the key exists before incrementing. You group things, so you write a check for whether the list exists before appending. You use a list as a queue, so you call pop(0) and never think about it again.

None of that is wrong. It is just code you have to read, review and get right every time. The collections module in the standard library ships specialised container types that make those patterns one line, and in the case of deque, dramatically faster.

Here is the boilerplate everyone writes at least once:

words = ['pune', 'delhi', 'pune']
rows = [('Asha', 88), ('Ravi', 71), ('Asha', 94)]

counts = {}
for word in words:
    if word not in counts:
        counts[word] = 0
    counts[word] += 1

groups = {}
for name, score in rows:
    if name not in groups:
        groups[name] = []
    groups[name].append(score)

Both loops are correct and both disappear entirely with Counter and defaultdict. The reason to learn these types is not that they are clever. It is that in an interview or a code review, the version with the manual existence check reads as someone who has not opened the standard library, and the queue built on a list is an actual performance bug rather than a style preference.

Everything in this post is in the standard library. There is nothing to install and nothing to configure. You import it and use it.

Counter: counting without the KeyError dance

Counter is a dict subclass built for tallying. You hand it any iterable and it counts the items. Because it is a dict, everything you already know about dicts still works on it.

from collections import Counter

votes = ['pune', 'delhi', 'pune', 'mumbai', 'pune', 'delhi']
tally = Counter(votes)

print(tally)                  # Counter({'pune': 3, 'delhi': 2, 'mumbai': 1})
print(tally['chennai'])       # 0
print('chennai' in tally)     # False - reading did not add the key
print(tally.most_common(2))   # [('pune', 3), ('delhi', 2)]

The important behaviour is the tally['chennai'] lookup. A missing key returns 0 instead of raising KeyError, and it does not insert the key. That makes tally[x] += 1 safe on any key, and it is also the behaviour that defaultdict does not have, which is the subject of the next section.

most_common() with no argument returns every item sorted by count, highest first. With an argument it returns that many. This is the single most useful method in the class and it is why "find the top three most frequent characters" is a two line answer rather than a sorting exercise.

Counter arithmetic has one behaviour that catches people. The - operator drops any count that ends up zero or negative, because a Counter is modelled as a multiset. If you actually want the negatives, use subtract(), which mutates in place and keeps them.

from collections import Counter

a = Counter(a=3, b=1)
b = Counter(a=1, b=2)

print(a - b)      # Counter({'a': 2}) and b's -1 was dropped

a.subtract(b)
print(a)          # Counter({'a': 2, 'b': -1})

One limit worth knowing: the items you count must be hashable. Counting lists or dicts raises TypeError. Convert them to tuples or to a string key first.

defaultdict: convenience that silently creates keys

defaultdict takes a callable, the "default factory". When you access a key that is missing, it calls that factory, stores the result under the key, and returns it. Grouping becomes one line:

from collections import defaultdict

marks = defaultdict(list)
for name, score in [('Asha', 88), ('Ravi', 71), ('Asha', 94)]:
    marks[name].append(score)

print(marks['Asha'])    # [88, 94]

Read that description again, because it contains the trap. Accessing a missing key writes to the dictionary. Reading is no longer a read. That is unusual in Python and it produces bugs that look impossible:

from collections import defaultdict

marks = defaultdict(list)

if marks['Kiran']:          # just checking, surely?
    print('has marks')

print(len(marks))           # 1
print(dict(marks))          # {'Kiran': []}

Now every loop over marks includes a student who has no marks, your count of students is wrong, and the JSON you send to the frontend has an empty array in it. Worse, this can happen in a debugger or a log line: printing d[k] to see what is there is enough to create it.

The fix is to use methods that do not go through the factory. d.get(key) returns None without inserting, key in d tests membership without inserting, and dict(d) gives you a plain dict for returning or serialising. If you want the read to fail loudly instead, that is a signal you wanted a normal dict all along.

if marks.get('Kiran'):      # safe
    ...
if 'Kiran' in marks:        # safe
    ...

The other common factories are defaultdict(int) for counting, though Counter is better at that, and defaultdict(set) for grouping unique values. You can also pass a lambda for a custom default, for example defaultdict(lambda: 'unknown').

deque: the fix for list.pop(0)

A Python list stores its elements in one contiguous block. Appending to the end is cheap. Removing from the front is not: every remaining element has to shift down one slot, so list.pop(0) costs time proportional to the length of the list.

That matters because the most common use of a queue in placement preparation is BFS. If your queue holds n nodes and you pop from the front n times, you have quietly turned an O(n) traversal into O(n squared) work. Nothing errors. The code passes small test cases and times out on the large one.

deque is a doubly linked structure of blocks, so pushing and popping at either end is a constant time operation:

from collections import deque

queue = deque(['a', 'b', 'c'])
queue.append('d')          # add at the right
queue.appendleft('z')      # add at the left
print(queue.popleft())     # 'z'
print(queue.pop())         # 'd'

A correct BFS is then just a matter of swapping the container. The rest of the code is identical:

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

The maxlen argument gives you a fixed size sliding window for free. Once the deque is full, adding at one end discards from the other, which is exactly what you want for "keep the last 50 log lines" or "last 10 searched items":

recent = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    recent.append(x)
print(recent)     # deque([3, 4, 5], maxlen=3)

What you give up is random access. Indexing near either end is fast, but reaching into the middle costs time proportional to the distance, and a deque does not support slicing at all, so dq[1:3] raises TypeError. If your code sorts, slices or indexes randomly, keep the list.

namedtuple, OrderedDict, and when not to use any of this

namedtuple builds a tuple subclass with named fields. It fixes the code where you return (name, city, marks) and every caller has to remember that index 2 is the marks.

from collections import namedtuple

Student = namedtuple('Student', ['name', 'city', 'marks'])
s = Student('Asha', 'Pune', 88)

print(s.city)                       # Pune
print(s[1])                         # Pune - still a tuple
print(s._asdict())                  # {'name': 'Asha', 'city': 'Pune', 'marks': 88}
print(s._replace(marks=91))         # a new Student, the original is unchanged
print(s == ('Asha', 'Pune', 88))    # True

The last line is the surprise. A namedtuple compares equal to a plain tuple with the same values, and it also compares equal to a different namedtuple class with the same values, because tuple equality only looks at contents. If you are relying on equality to mean "same kind of thing", it does not.

Because it is a tuple, it is immutable. That is a feature when you want a safe record, and a problem when you actually want to change fields, at which point a dataclass is the better tool. A rough rule: fewer than about five fields and no mutation, use namedtuple; anything with defaults, methods or validation, use a dataclass.

OrderedDict is the one you probably do not need any more. Since Python 3.7 the language guarantees that a plain dict preserves insertion order, which was the entire reason people reached for OrderedDict. What it still gives you is order sensitive equality and two ordering methods:

from collections import OrderedDict

a = OrderedDict([('x', 1), ('y', 2)])
b = OrderedDict([('y', 2), ('x', 1)])
print(a == b)                  # False - order is part of equality

print({'x': 1, 'y': 2} == {'y': 2, 'x': 1})   # True - plain dicts ignore order

a.move_to_end('x')
print(a.popitem(last=False))   # ('y', 2) - pop from the front

Those methods make an LRU cache easy to write by hand, which is the main remaining reason to use it. For everything else, a dict is fine.

Finally, know when to stop. Do not return a defaultdict or a Counter from a public function unless the caller expects it, because their surprising behaviour becomes someone else's bug; convert with dict() first. Do not use a deque as a general purpose list. And if a plain dict with three explicit lines is clearer to the person reviewing your pull request, that is a legitimate reason to keep the plain dict.

Frequently Asked Questions