A Comprehensive Guide to Python’s Built-In Data Structures

Time complexities Of Python built-in data structures

Eyal Trabelsi
Nov 1 · 3 min read

Data structures are just specialized formats for organizing and storing data. They are a vital part of software development and choosing the right data structure is crucial.

“Bad programmers worry about the code. Good programmers worry about data structures and their relationships.” — Linus Torvalds, creator of Linux

One of the most important characters for picking the right one is its Big O notation.

What is a Big O notation? Big O notation (“O” stands for “order”) is the language to describe the performance of an algorithm and how it scales (not necessarily how fast it is).

I realize there are plenty of data structure articles out there. However, in this article, I will focus on Python implementation because:

  • There is no single place with Python data structures time complexity (almost).
  • I have somewhat different data structures.
  • The time complexity can be surprising due to implementation.

Let’s Start

1. List

A List is an ordered mutable collection of elements.

big O notation for list

2. Set

A Set is an unordered collection of distinct hashable objects.

big O notation for set

3. Dict

A Dict maps hashable values to arbitrary mutable objects.

big O notation for dict

4. Default dict

A Default dict is a dictionary that is initialized with a default value when each key is encountered for the first time.

big O notation for default dict

5. Deque

A Deque is a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”).

big O notation for deque

6. Heapq

A Heapq is a binary search tree for which every parent node has a value less than or equal to any of its children.

big O notation for heapq

7. Counter

A Counter is a dict subclass for counting hashable objects. It is an unordered collection where elements are stored as dictionary keys and their counts are stored as dictionary values.

big O notation for counter

8. Bisect

The bisect module implements an algorithm for inserting elements into a list while maintaining the list in sorted order.

big O notation for bisect

Last Words

I hope you found it interesting and useful. I am open to any kind of constructive feedback.

Better Programming

Advice for programmers.

Thanks to Zack Shapiro

Eyal Trabelsi

Written by

Better Programming

Advice for programmers.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade