Estructuras de datos en Python: una guía completa para developers
Una referencia práctica para Listas, Listas enlazadas, Stacks, Queues, Diccionarios, Árboles y Grafos en Python, con la complejidad Big O de cada operación.
Toda entrevista técnica pregunta sobre estructuras de datos. Todo problema de rendimiento en producción se puede rastrear hasta una mala elección de estructura de datos. Sin embargo, la mayoría de los developers aprenden la sintaxis de Python sin sentarse a entender por qué el acceso a una lista es O(1) mientras que insertar al principio es O(n).
Esta guía cubre las ocho estructuras de datos que aparecen con más frecuencia en codebases reales de Python y en entrevistas. Para cada una verás la implementación en Python, las operaciones comunes y el costo Big O de cada operación para que puedas razonar sobre el rendimiento desde los primeros principios.
La estructura incorrecta no rompe tu código: lo hace lento. El mismo script puede tardar 2 ms con un set o 20 segundos con una lista si la entrada es grande.
02
Entrevistas
Las estructuras aparecen en casi toda entrevista técnica. Hablar sobre trade-offs en inglés, 'O(1) amortizado, O(n) peor caso', es lo que te permite pasar el filtro.
03
Python integrado
Python incluye excelentes estructuras por defecto. Entender qué sucede internamente te permite elegir la herramienta correcta y explicar tu decisión al equipo.
Listas
Los conceptos básicos
Las listas de Python son arrays dinámicos. Internamente asignan un bloque de memoria contigua y almacenan referencias a objetos. Cuando el bloque se llena, Python asigna un bloque más grande y copia todo. Este redimensionamiento ocurre con tan poca frecuencia que agregar al final es O(1) amortizado.
Como los elementos se almacenan en offsets fijos desde el inicio del bloque, el acceso aleatorio por índice es O(1). Buscar un valor requiere escanear toda la lista en el peor caso: O(n).
Python 3 — Interactive
>>> # Crear y acceder a una lista
>>> fruits = ["apple", "banana", "cherry"]
>>> print(fruits[0]) # apple — O(1) acceso por índice
apple
>>> print(fruits[-1]) # cherry — índices negativos cuentan desde el final
cherry
>>> # Agregar al final es O(1) amortizado
>>> fruits.append("date")
>>> print(len(fruits)) # 4
4
>>> # Insertar al principio es O(n) — cada elemento se desplaza a la derecha
>>> fruits.insert(0, "avocado")
>>> print(fruits)
['avocado', 'apple', 'banana', 'cherry', 'date']
Slicing y búsqueda
El slicing crea una nueva lista con una copia de los elementos seleccionados. Se ejecuta en O(k) donde k es el tamaño del slice. El operador in hace un escaneo lineal: O(n). Si necesitás tests de pertenencia rápidos, usá un set o un dict.
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] de a uno por medio
[10, 30, 50] de a uno por medio
>>> print(numbers[::-1]) # [50, 40, 30, 20, 10] invertida
[50, 40, 30, 20, 10] invertida
>>> # Búsqueda lineal — O(n)
>>> print(30 in numbers) # True
True
>>> print(99 in numbers) # False
False
>>> # index() lanza ValueError si no encuentra el valor
>>> idx = numbers.index(30)
>>> print(idx) # 2
2
Complejidad de listas de un vistazo
Operación
Big O
Acceso por índice
O(1)
Agregar al final
O(1) amortizado
Insertar al principio
O(n)
Eliminar por índice
O(n)
Búsqueda (in)
O(n)
Longitud (len)
O(1)
Listas enlazadas
Una lista enlazada almacena elementos en nodos, donde cada nodo guarda un valor y un puntero al siguiente. A diferencia de las listas de Python, los nodos están dispersos en memoria en lugar de almacenarse en un bloque contiguo. Esto hace que la inserción y eliminación al principio sea O(1), pero el acceso aleatorio es O(n) porque hay que recorrer la cadena desde el inicio.
Python no tiene una lista enlazada integrada, pero collections.deque está implementada como una lista doblemente enlazada de bloques de tamaño fijo, dando O(1) para agregar y quitar en ambos extremos.
Para la mayoría de los usos prácticos, collections.deque es la elección correcta cuando necesitás operaciones eficientes en ambos extremos de una secuencia. Internamente es una lista doblemente enlazada, por lo que agregar y quitar de cualquier extremo es O(1).
Python 3 — Interactive
>>> from collections import deque
>>> d = deque([1, 2, 3])
>>> d.appendleft(0) # O(1) — insertar al principio
>>> d.append(4) # O(1) — insertar al final
>>> print(d) # deque([0, 1, 2, 3, 4])
deque([0, 1, 2, 3, 4])
>>> d.popleft() # O(1) — quitar del principio
>>> d.pop() # O(1) — quitar del final
>>> print(d) # deque([1, 2, 3])
deque([1, 2, 3])
Un stack es una estructura Last-In, First-Out (LIFO). El último elemento que apilás es el primero que sacás. Los casos de uso clásicos incluyen historial de deshacer/rehacer, call stacks, parseo de expresiones y recorrido en profundidad (DFS).
En Python el stack más simple es una lista: append apila y pop quita del final, ambos O(1). Si necesitás thread safety o querés señalar la intención más claramente, usá collections.deque.
Python 3 — Interactive
>>> # Stack usando una lista simple
>>> 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']
Ejemplo real: brackets balanceados
Verificar si los brackets están balanceados es un problema clásico de stack. Apilás cada bracket de apertura y lo sacás cuando encontrás uno de cierre. Si el stack está vacío al final y nada estaba desalineado, el string es válido.
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
Una queue es una estructura First-In, First-Out (FIFO). El primer elemento que encolas es el primero que desencolas. Los casos de uso incluyen programación de tareas, recorrido BFS de grafos y cualquier pipeline donde importa el orden de llegada.
No uses una lista como queue: list.pop(0) es O(n) porque cada elemento se desplaza a la izquierda. Usá collections.deque en cambio, donde popleft es O(1). Para concurrencia productor/consumidor, queue.Queue de la librería estándar agrega thread safety.
La búsqueda en anchura (BFS) es el algoritmo canónico de queue. Empezás en un nodo, encolás sus vecinos y luego procesás cada vecino en orden. Esto garantiza visitar los nodos en orden de distancia desde el inicio.
Una tabla hash mapea claves a valores usando una función hash para calcular un índice de array. Los dict y set de Python son tablas hash. El caso promedio para búsqueda, inserción y eliminación es O(1). El peor caso es O(n) si muchas claves producen el mismo bucket, pero la implementación de Python hace que esto sea extremadamente improbable en la práctica.
Desde Python 3.7, los diccionarios preservan el orden de inserción, por lo que podés iterar las claves en el orden en que fueron agregadas.
Python 3 — Interactive
>>> # dict: tabla hash de clave -> valor
>>> 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) para búsqueda
>>> print(word_count["apple"]) # 3
3
>>> print("grape" in word_count) # False
False
Sets para tests de pertenencia rápidos
Cuando solo necesitás saber si un valor existe, un set es la herramienta correcta. Usa el mismo mecanismo de tabla hash que un dict pero almacena solo claves, no pares clave-valor. El test de pertenencia es O(1) versus O(n) para una lista.
Python 3 — Interactive
>>> # set: sin orden, sin duplicados, pertenencia O(1)
>>> visited_urls: set[str] = set()
>>> urls = [
>>> "https://lingua-e.com",
>>> "https://lingua-e.com/tutoriales",
>>> "https://lingua-e.com", # duplicado — se ignora
>>> ]
>>> for url in urls:
... visited_urls.add(url)
>>> print(visited_urls)
{'https://lingua-e.com', 'https://lingua-e.com/tutoriales'}
>>> # O(1) para búsqueda
>>> print("https://lingua-e.com" in visited_urls) # True
True
>>> print("https://example.com" in visited_urls) # False
False
Un árbol es una estructura de datos jerárquica donde cada nodo tiene cero o más hijos y exactamente un padre (excepto la raíz, que no tiene ninguno). Los árboles están en todos lados: sistemas de archivos, DOM de HTML, compiladores, índices de bases de datos (B-trees) y árboles de decisión en machine learning.
La variante más común en entrevistas es el Árbol Binario de Búsqueda (BST): cada nodo tiene como máximo dos hijos, y el subárbol izquierdo contiene solo valores menores que el nodo mientras el subárbol derecho contiene solo valores mayores. Esta propiedad hace que la búsqueda sea O(log n) en un árbol balanceado.
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
Recorrido de árboles
Hay tres órdenes clásicos de recorrido en profundidad. El recorrido in-order de un BST siempre devuelve los valores en orden ascendente, lo cual es útil para producir una lista ordenada a partir de un BST.
Un grafo es un conjunto de nodos (vértices) conectados por aristas. A diferencia de los árboles, los grafos pueden tener ciclos, múltiples caminos entre nodos y nodos sin ninguna conexión. Los grafos modelan relaciones: redes sociales, mapas de rutas, grafos de dependencias, máquinas de estado.
Las dos representaciones más comunes son la lista de adyacencia (un dict que mapea cada nodo a sus vecinos) y la matriz de adyacencia (un array 2D donde matrix[i][j] es 1 si hay una arista de i a j). Las listas de adyacencia son casi siempre la elección correcta en Python porque usan menos memoria para grafos dispersos.
Python 3 — Interactive
>>> # Representación con lista de adyacencia
>>> graph: dict[str, list[str]] = {
>>> "Alice": ["Bob", "Carol"],
>>> "Bob": ["Alice", "Dave"],
>>> "Carol": ["Alice"],
>>> "Dave": ["Bob"],
>>> }
>>> # Agregar una arista
>>> graph["Carol"].append("Dave")
>>> graph["Dave"].append("Carol")
>>> # Ver vecinos
>>> print(graph["Alice"]) # ['Bob', 'Carol']
['Bob', 'Carol']
>>> print("Dave" in graph["Bob"]) # True
True
Búsqueda en profundidad (DFS)
DFS explora lo más lejos posible por cada rama antes de retroceder. Es naturalmente recursivo y usa el call stack (o un stack explícito) para recordar a dónde retroceder. DFS se usa para detección de ciclos, ordenamiento topológico y encontrar componentes conectados.
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']
Referencia de complejidad Big O
La notación Big O describe cómo crece el tiempo de ejecución o el uso de memoria de un algoritmo a medida que aumenta el tamaño de entrada n. Captura la tasa de crecimiento en el peor caso, ignorando factores constantes y términos de orden inferior. Esta tabla cubre las complejidades que aparecen con más frecuencia al hablar de estructuras de datos.
Notation
Nombre
Ejemplo
O(1)
Constante
Búsqueda en dict, acceso por índice en lista
O(log n)
Logarítmica
Búsqueda binaria, búsqueda en BST balanceado
O(n)
Lineal
Escaneo lineal, insertar al principio de una lista
O(n log n)
Lineal-logarítmica
Merge sort, heap sort
O(n²)
Cuadrática
Bubble sort, bucles anidados sobre n
O(2ⁿ)
Exponencial
Enumeración de subconjuntos por fuerza bruta
Comparación de estructuras
Estructura
Acceso
Búsqueda
Inserción
Eliminación
Lista
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 (balanceado)
O(log n)
O(log n)
O(log n)
O(log n)
* O(1) amortizado al final. ** O(1) solo en ambos extremos.
Las estructuras de datos se evalúan en casi toda entrevista técnica para roles de ingeniería de software. Si te estás preparando para entrevistas, la guía de preguntas de entrevista técnica cubre los patrones más comunes en inglés para que puedas explicar tu enfoque con claridad al entrevistador.
Roxana Lafuente es ingeniera de software con más de 8 años de experiencia. Al comienzo de su carrera, aunque ya había aprobado el First Certificate in English, se bloqueaba cada vez que tenía que hablar en el standup diario. Era un problema que nadie estaba resolviendo. Después de más de 2.000 standups, descubrió qué es lo que realmente construye la fluidez: practicar situaciones que se parecen a tu trabajo real. Creó Lingua-e para que otros developers no tuvieran que tomar el camino largo para sentirse seguros trabajando en un entorno de desarrollo internacional.