Data Structures in Python: A Complete Developer Guide
A practical reference for Lists, Linked Lists, Stacks, Queues, Dictionaries, Trees, and Graphs in Python, with Big O complexity for every operation.
Every technical interview asks about data structures. Every performance problem in production can be traced back to a poor choice of data structure. Yet most developers learn Python syntax without ever sitting down to understand why a list lookup is O(1) while inserting at the front is O(n).
This guide covers the eight data structures that come up most often in real Python codebases and interviews. For each one you will see the Python implementation, the common operations, and the Big O cost of each operation so you can reason about performance from first principles.
The wrong structure doesn't break your code — it makes it slow. The same script can take 2 ms with a set or 20 seconds with a list on a large input.
02
Interviews
Data structures appear in almost every technical screen. Talking about trade-offs in English — 'O(1) amortised, O(n) worst case' — is what gets you past the interviewer.
03
Python built-ins
Python ships excellent structures out of the box. Knowing what happens under the hood lets you pick the right tool and explain your choice to teammates.
Lists
The basics
Python lists are dynamic arrays. Under the hood they allocate a contiguous block of memory and store references to objects. When the block is full, Python allocates a larger block and copies everything over. This resizing happens rarely enough that appending is O(1) amortised.
Because items are stored at fixed offsets from the start of the block, random access by index is O(1). Searching for a value requires scanning the whole list in the worst case: O(n).
Python 3 — Interactive
>>> # Creating and accessing a list
>>> fruits = ["apple", "banana", "cherry"]
>>> print(fruits[0]) # apple — O(1) index access
apple
>>> print(fruits[-1]) # cherry — negative indices count from end
cherry
>>> # Appending is O(1) amortised
>>> fruits.append("date")
>>> print(len(fruits)) # 4
4
>>> # Inserting at the front is O(n) — every element shifts right
>>> fruits.insert(0, "avocado")
>>> print(fruits)
['avocado', 'apple', 'banana', 'cherry', 'date']
Slicing and searching
Slicing creates a new list containing a copy of the selected elements. It runs in O(k) where k is the size of the slice. The in operator does a linear scan: O(n). If you need fast membership tests, use a set or dict instead.
Python 3 — Interactive
>>> numbers = [10, 20, 30, 40, 50]
>>> # Slicing: list[start:stop:step]
>>> print(numbers[1:4]) # [20, 30, 40]
[20, 30, 40]
>>> print(numbers[::2]) # [10, 30, 50] every other item
[10, 30, 50] every other item
>>> print(numbers[::-1]) # [50, 40, 30, 20, 10] reversed
[50, 40, 30, 20, 10] reversed
>>> # Linear search — O(n)
>>> print(30 in numbers) # True
True
>>> print(99 in numbers) # False
False
>>> # index() raises ValueError if not found
>>> idx = numbers.index(30)
>>> print(idx) # 2
2
List complexity at a glance
Operation
Big O
Access by index
O(1)
Append
O(1) amortised
Insert at front
O(n)
Delete by index
O(n)
Search (in)
O(n)
Length (len)
O(1)
Linked lists
A linked list stores elements in nodes, where each node holds a value and a pointer to the next node. Unlike a Python list, the nodes are scattered in memory rather than stored in a contiguous block. This makes insertion and deletion at the head O(1) but random access O(n) because you must walk the chain from the beginning.
Python does not have a built-in linked list, but collections.deque is implemented as a doubly linked list of fixed-size blocks, giving O(1) appends and pops at both ends.
For most practical purposes, collections.deque is the right choice when you need efficient operations at both ends of a sequence. It is a doubly linked list under the hood, so appending and popping from either end is O(1).
Python 3 — Interactive
>>> from collections import deque
>>> d = deque([1, 2, 3])
>>> d.appendleft(0) # O(1) — insert at front
>>> d.append(4) # O(1) — insert at back
>>> print(d) # deque([0, 1, 2, 3, 4])
deque([0, 1, 2, 3, 4])
>>> d.popleft() # O(1) — remove from front
>>> d.pop() # O(1) — remove from back
>>> print(d) # deque([1, 2, 3])
deque([1, 2, 3])
A stack is a Last-In, First-Out (LIFO) structure. The last element you push onto the stack is the first one you pop off. Classic use cases include undo/redo history, call stacks, expression parsing, and depth-first traversal.
In Python the simplest stack is just a list: append pushes and pop removes from the end, both O(1). If you need thread safety or want to signal intent more clearly, use collections.deque.
Python 3 — Interactive
>>> # Stack using a plain list
>>> stack: list[str] = []
>>> stack.append("open file") # push
>>> stack.append("edit line 10") # push
>>> stack.append("save") # push
>>> print(stack)
['open file', 'edit line 10', 'save']
>>> last = stack.pop() # pop — O(1)
>>> print(last) # save
save
>>> print(stack)
['open file', 'edit line 10']
Real-world example: balanced brackets
Checking whether brackets are balanced is a classic stack problem. You push every opening bracket and pop when you see a closing one. If the stack is empty at the end and nothing was mismatched, the string is valid.
Python 3 — Interactive
>>> def is_balanced(s: str) -> bool:
... stack: list[str] = []
... pairs = {")": "(", "]": "[", "}": "{"}
... for ch in s:
... if ch in "([{":
... stack.append(ch)
... elif ch in ")]}":
... if not stack or stack[-1] != pairs[ch]:
... return False
... stack.pop()
... return len(stack) == 0
>>> print(is_balanced("([{}])")) # True
True
>>> print(is_balanced("([)]")) # False
False
>>> print(is_balanced("{[}")) # False
False
Queues
A queue is a First-In, First-Out (FIFO) structure. The first element you enqueue is the first one you dequeue. Use cases include task scheduling, BFS graph traversal, and any pipeline where order of arrival matters.
Do not use a plain list as a queue: list.pop(0) is O(n) because every element shifts left. Use collections.deque instead, where popleft is O(1). For producer/consumer concurrency, queue.Queue from the standard library adds thread safety.
Breadth-first search is the canonical queue algorithm. You start at a node, enqueue its neighbours, then process each neighbour in order. This guarantees you visit nodes in order of their distance from the start.
A hash table maps keys to values using a hash function to compute an array index. Python's dict and set are both hash tables. Average-case lookup, insertion, and deletion are O(1). Worst case is O(n) if many keys hash to the same bucket, but Python's implementation makes this extremely unlikely in practice.
Since Python 3.7, dictionaries preserve insertion order, so you can iterate keys in the order they were added.
Python 3 — Interactive
>>> # dict: key -> value hash table
>>> word_count: dict[str, int] = {}
>>> words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
>>> for word in words:
... word_count[word] = word_count.get(word, 0) + 1
>>> print(word_count)
{'apple': 3, 'banana': 2, 'cherry': 1}
>>> # O(1) lookup
>>> print(word_count["apple"]) # 3
3
>>> print("grape" in word_count) # False
False
Sets for fast membership tests
When you only need to know whether a value exists, a set is the right tool. It uses the same hash table mechanism as a dict but stores only keys, not key-value pairs. Membership testing is O(1) versus O(n) for a list.
A tree is a hierarchical data structure where each node has zero or more children and exactly one parent (except the root, which has none). Trees are used everywhere: file systems, HTML DOM, compilers, database indexes (B-trees), and decision trees in machine learning.
The most common variant in interviews is the Binary Search Tree (BST): each node has at most two children, and the left subtree contains only values smaller than the node while the right subtree contains only larger values. This property makes search O(log n) on a balanced tree.
Python 3 — Interactive
>>> class TreeNode:
... def __init__(self, value: int) -> None:
... self.value = value
... self.left: "TreeNode | None" = None
... self.right: "TreeNode | None" = None
>>> class BinarySearchTree:
... def __init__(self) -> None:
... self.root: TreeNode | None = None
... def insert(self, value: int) -> None:
... if self.root is None:
... self.root = TreeNode(value)
... else:
... self._insert(self.root, value)
... def _insert(self, node: TreeNode, value: int) -> None:
... if value < node.value:
... if node.left is None:
... node.left = TreeNode(value)
... else:
... self._insert(node.left, value)
... else:
... if node.right is None:
... node.right = TreeNode(value)
... else:
... self._insert(node.right, value)
... def search(self, value: int) -> bool:
... return self._search(self.root, value)
... def _search(self, node: "TreeNode | None", value: int) -> bool:
... if node is None:
... return False
... if value == node.value:
... return True
... if value < node.value:
... return self._search(node.left, value)
... return self._search(node.right, value)
>>> bst = BinarySearchTree()
>>> for v in [5, 3, 7, 1, 4, 6, 8]:
... bst.insert(v)
>>> print(bst.search(4)) # True
True
>>> print(bst.search(99)) # False
False
Tree traversal
There are three classic depth-first traversal orders. In-order traversal of a BST always yields values in sorted order, which is useful for tasks like producing a sorted list from a BST.
Python 3 — Interactive
>>> def inorder(node: "TreeNode | None") -> list[int]:
... """Left, root, right — yields sorted values for a BST."""
... if node is None:
... return []
... return inorder(node.left) + [node.value] + inorder(node.right)
>>> def preorder(node: "TreeNode | None") -> list[int]:
... """Root, left, right — useful for copying a tree."""
... if node is None:
... return []
... return [node.value] + preorder(node.left) + preorder(node.right)
>>> def postorder(node: "TreeNode | None") -> list[int]:
... """Left, right, root — useful for deleting a tree."""
... if node is None:
... return []
... return postorder(node.left) + postorder(node.right) + [node.value]
>>> # Using the BST from the previous example
>>> print(inorder(bst.root)) # [1, 3, 4, 5, 6, 7, 8]
[1, 3, 4, 5, 6, 7, 8]
>>> print(preorder(bst.root)) # [5, 3, 1, 4, 7, 6, 8]
[5, 3, 1, 4, 7, 6, 8]
>>> print(postorder(bst.root)) # [1, 4, 3, 6, 8, 7, 5]
[1, 4, 3, 6, 8, 7, 5]
Graphs
A graph is a set of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and nodes with no connections at all. Graphs model relationships: social networks, road maps, dependency graphs, state machines.
The two most common representations are the adjacency list (a dict mapping each node to its neighbours) and the adjacency matrix (a 2D array where matrix[i][j] is 1 if there is an edge from i to j). Adjacency lists are almost always the right choice in Python because they use less memory for sparse graphs.
DFS explores as far as possible along each branch before backtracking. It is naturally recursive and uses the call stack (or an explicit stack) to remember where to backtrack to. DFS is used for cycle detection, topological sort, and finding connected components.
Python 3 — Interactive
>>> def dfs(
>>> graph: dict[str, list[str]],
>>> start: str,
>>> visited: set[str] | None = None,
>>> ) -> list[str]:
... if visited is None:
... visited = set()
... visited.add(start)
... result = [start]
... for neighbour in graph[start]:
... if neighbour not in visited:
... result.extend(dfs(graph, neighbour, visited))
... return result
>>> print(dfs(graph, "Alice"))
['Alice', 'Bob', 'Dave', 'Carol']
Big O complexity reference
Big O notation describes how the runtime or memory usage of an algorithm grows as the input size n increases. It captures the worst-case growth rate, ignoring constant factors and lower-order terms. This table covers the complexities that come up most often when discussing data structures.
Notation
Name
Example
O(1)
Constant
Dict lookup, list index access
O(log n)
Logarithmic
Binary search, balanced BST search
O(n)
Linear
Linear scan, list insert at front
O(n log n)
Linearithmic
Merge sort, heap sort
O(n²)
Quadratic
Bubble sort, nested loops over n
O(2ⁿ)
Exponential
Brute-force subset enumeration
Structure comparison
Structure
Access
Search
Insert
Delete
List
O(1)
O(n)
O(n)*
O(n)
Deque
O(n)
O(n)
O(1)**
O(1)**
Dict
O(1)
O(1)
O(1)
O(1)
Set
-
O(1)
O(1)
O(1)
BST (balanced)
O(log n)
O(log n)
O(log n)
O(log n)
* O(1) amortised at the tail. ** O(1) at both ends only.
Data structures are tested in almost every technical interview for software engineering roles. If you are preparing for interviews, the technical interview questions guide covers the most common patterns in English so you can discuss your approach clearly with the interviewer.
Roxana Lafuente is a software engineer with 8+ years of experience. At the beginning of her career, even though she had already passed the First Certificate in English, she still froze every time she had to speak up in the daily standup. That was a gap nobody was fixing. After 2,000+ standups, she figured out what actually builds fluency: practice that looks like your real work. She built Lingua-e so other developers wouldn't have to take the long road to feel confident working in an international development environment.