Lingua-e
Python tutorial

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.

In this guide
  1. Why data structures matter
  2. Lists
  3. Linked lists
  4. Stacks
  5. Queues
  6. Dictionaries
  7. Trees
  8. Graphs
  9. Big O complexity reference

Why data structures matter

01
Performance
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 list showing elements apple, banana, cherry with positive indexes 0 1 2 and negative indexes -3 -2 -1
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

OperationBig O
Access by indexO(1)
AppendO(1) amortised
Insert at frontO(n)
Delete by indexO(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.

Linked list with three nodes: 10, 20, 30, each holding a value and a pointer to the next node, ending in None
Python 3 — Interactive
>>> class Node:
...     def __init__(self, value: int) -> None:
...         self.value = value
...         self.next: "Node | None" = None


>>> class LinkedList:
...     def __init__(self) -> None:
...         self.head: Node | None = None

...     def prepend(self, value: int) -> None:
...         """Insert at head — O(1)."""
...         node = Node(value)
...         node.next = self.head
...         self.head = node

...     def to_list(self) -> list[int]:
...         result = []
...         current = self.head
...         while current:
...             result.append(current.value)
...             current = current.next
...         return result


>>> ll = LinkedList()
>>> ll.prepend(3)
>>> ll.prepend(2)
>>> ll.prepend(1)
>>> print(ll.to_list())  # [1, 2, 3]
[1, 2, 3]

Using collections.deque

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).

Deque with elements 1 through 5; appendleft and popleft operate on the left end, append and pop on the right
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])
Want to implement each structure from scratch with guided exercises? The full course walks through every data structure step by step.Take the course →

Stacks

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.

Stack with three elements 10, 20, 30 stacked vertically; 30 is at the top; push adds to the top, pop removes from the top (LIFO)
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.

Queue with four elements 10, 20, 30, 40; dequeue removes from the front (left), enqueue adds to the rear (right) (FIFO)
Python 3 — Interactive
>>> from collections import deque

>>> queue: deque[str] = deque()

>>> # Enqueue (add to back)
>>> queue.append("task-1")
>>> queue.append("task-2")
>>> queue.append("task-3")

>>> print(queue)
deque(['task-1', 'task-2', 'task-3'])

>>> # Dequeue (remove from front) — O(1)
>>> next_task = queue.popleft()
>>> print(next_task)  # task-1
task-1
>>> print(queue)
deque(['task-2', 'task-3'])

BFS with a queue

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.

Python 3 — Interactive
>>> from collections import deque

>>> graph = {
>>>     "A": ["B", "C"],
>>>     "B": ["D", "E"],
>>>     "C": ["F"],
>>>     "D": [],
>>>     "E": [],
>>>     "F": [],
>>> }


>>> def bfs(start: str) -> list[str]:
...     visited: list[str] = []
...     queue: deque[str] = deque([start])
...     seen: set[str] = {start}

...     while queue:
...         node = queue.popleft()
...         visited.append(node)
...         for neighbour in graph[node]:
...             if neighbour not in seen:
...                 seen.add(neighbour)
...                 queue.append(neighbour)

...     return visited


>>> print(bfs("A"))  # ['A', 'B', 'C', 'D', 'E', 'F']
['A', 'B', 'C', 'D', 'E', 'F']

Dictionaries

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 dictionary with three key-value pairs: name maps to Alice, age maps to 30, role maps to dev
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.

Python 3 — Interactive
>>> # set: unordered, no duplicates, O(1) membership
>>> visited_urls: set[str] = set()

>>> urls = [
>>>     "https://lingua-e.com",
>>>     "https://lingua-e.com/tutorials",
>>>     "https://lingua-e.com",        # duplicate — ignored
>>> ]

>>> for url in urls:
...     visited_urls.add(url)

>>> print(visited_urls)
{'https://lingua-e.com', 'https://lingua-e.com/tutorials'}

>>> # O(1) lookup
>>> print("https://lingua-e.com" in visited_urls)  # True
True
>>> print("https://example.com" in visited_urls)   # False
False

Dict / set complexity at a glance

OperationBig O
Get itemO(1) avg
Set itemO(1) avg
Delete itemO(1) avg
Membership (in)O(1) avg
IterationO(n)
Trees and graphs are the structures interviewers test most. The full course covers every traversal and search algorithm with real interview problems.Take the course →

Trees

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.

Binary search tree with root node 5; left subtree rooted at 3 with children 1 and 4; right subtree rooted at 8 with children 7 and 9
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.

Undirected graph with five nodes A, B, C, D, E and edges connecting them: A-B, A-C, B-C, B-D, C-E, D-E
Python 3 — Interactive
>>> # Adjacency list representation
>>> graph: dict[str, list[str]] = {
>>>     "Alice":   ["Bob", "Carol"],
>>>     "Bob":     ["Alice", "Dave"],
>>>     "Carol":   ["Alice"],
>>>     "Dave":    ["Bob"],
>>> }

>>> # Add an edge
>>> graph["Carol"].append("Dave")
>>> graph["Dave"].append("Carol")

>>> # Check neighbours
>>> print(graph["Alice"])   # ['Bob', 'Carol']
['Bob', 'Carol']
>>> print("Dave" in graph["Bob"])  # True
True

Depth-first search

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.

NotationNameExample
O(1)ConstantDict lookup, list index access
O(log n)LogarithmicBinary search, balanced BST search
O(n)LinearLinear scan, list insert at front
O(n log n)LinearithmicMerge sort, heap sort
O(n²)QuadraticBubble sort, nested loops over n
O(2ⁿ)ExponentialBrute-force subset enumeration

Structure comparison

StructureAccessSearchInsertDelete
ListO(1)O(n)O(n)*O(n)
DequeO(n)O(n)O(1)**O(1)**
DictO(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.

The full course includes a complete Big O cheat sheet and timed practice problems so you can build speed before your interview.Take the course →
Aprende Estructuras de Datos en Python desde Cero — Udemy course
Take it further

Aprende Estructuras de Datos en Python desde Cero

Go from zero to confident: implement every structure from scratch, analyse the complexity of each operation, and solve the interview problems that come up most in Python engineering roles.

5.0 ★by Roxana Lafuente
View on Udemy →
Roxana Lafuente

Written by

Roxana Lafuente

Lingua-e's founder

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.

Frequently asked questions

← Tutorials