Cuando escribes mi_lista = [1, 2, 3], Python no crea una cadena de nodos enlazados como en otros lenguajes. Crea un dynamic array: un bloque contiguo de memoria que almacena referencias a objetos, con una capacidad reservada mayor que los elementos actuales. Esta decisión de implementación lo explica todo: por qué append() es rápido, por qué insert(0, x) duele, y por qué buscar con in recorre la lista entera.
El mecanismo de sobreasignación de capacidad es clave. Cuando el array interno se llena, Python no reserva espacio para un elemento más, sino que multiplica la capacidad (aproximadamente por 1.125 cada vez). Así, una secuencia de append() solo necesita realojamiento ocasionalmente, lo que da un costo amortizado O(1) por inserción al final. Pero cuando haces insert(0, x), Python tiene que desplazar todos los elementos una posición hacia la derecha antes de escribir en la posición 0. Con un millón de elementos, eso es un millón de operaciones: O(n) en toda su expresión.
in sufre el mismo problema: no hay índice, no hay orden garantizado, así que Python compara elemento por elemento desde el principio hasta encontrarlo o agotar la lista. O(n) en el peor caso.
sort() usa Timsort, un algoritmo híbrido (merge sort + insertion sort) que aprovecha runs ya ordenados en los datos reales. Es estable (preserva el orden relativo de elementos iguales), corre en O(n log n), y opera in-place mutando la lista original. sorted() hace lo mismo pero devuelve una lista nueva, dejando la original intacta.
import time
import random
from typing import Any
# ── Métodos fundamentales ──────────────────────────────────────────────
def demo_basic_methods() -> None:
items: list[int] = [3, 1, 4, 1, 5, 9, 2, 6]
items.append(7) # O(1) amortizado — añade al final
items.extend([8, 0]) # O(k) donde k es la longitud del iterable
items.insert(0, 99) # O(n) — desplaza todo el array hacia la derecha
items.remove(1) # O(n) — busca y elimina la *primera* ocurrencia
last = items.pop() # O(1) — extrae el último elemento
first = items.pop(0) # O(n) — extrae el primero: igual que insert, desplaza todo
idx = items.index(9) # O(n) — búsqueda lineal; lanza ValueError si no existe
cnt = items.count(1) # O(n) — recorre toda la lista
print(f"pop last: {last}, pop first: {first}, index(9): {idx}, count(1): {cnt}")
# ── sort() muta vs sorted() devuelve una nueva lista ─────────────────
def demo_sort_vs_sorted() -> None:
original = [5, 2, 8, 1, 9, 3]
new_list = sorted(original) # original intacto, nueva lista ordenada
print(f"original después de sorted(): {original}") # [5, 2, 8, 1, 9, 3]
print(f"nueva lista: {new_list}") # [1, 2, 3, 5, 8, 9]
original.sort(reverse=True) # muta in-place; retorna None
print(f"original después de sort(): {original}") # [9, 8, 5, 3, 2, 1]
# Timsort es estable: elementos con igual key mantienen su orden relativo
words = ["banana", "apple", "cherry", "apricot"]
words.sort(key=lambda w: w[0]) # ordena por primera letra
print(words) # apple y apricot mantienen su orden original entre sí
# ── Medir el costo real de append vs insert(0, x) ────────────────────
def benchmark_append_vs_insert(n: int = 100_000) -> None:
# append: O(1) amortizado → tiempo total ≈ lineal en n
data: list[int] = []
t0 = time.perf_counter()
for i in range(n):
data.append(i)
append_time = time.perf_counter() - t0
# insert(0, x): O(n) por operación → tiempo total ≈ cuadrático en n
data2: list[int] = []
t0 = time.perf_counter()
for i in range(n):
data2.insert(0, i)
insert_time = time.perf_counter() - t0
print(f"append x{n}: {append_time:.4f}s")
print(f"insert(0) x{n}: {insert_time:.4f}s")
# La diferencia crece drásticamente al aumentar n
# ── Búsqueda: in en lista O(n) vs set O(1) ───────────────────────────
def demo_membership_cost(n: int = 10_000) -> None:
haystack_list = list(range(n))
haystack_set = set(haystack_list)
needle = n - 1 # peor caso: está al final
t0 = time.perf_counter()
for _ in range(1000):
_ = needle in haystack_list # busca lineal hasta el final
list_time = time.perf_counter() - t0
t0 = time.perf_counter()
for _ in range(1000):
_ = needle in haystack_set # hash lookup O(1)
set_time = time.perf_counter() - t0
print(f"'in' en lista: {list_time:.4f}s")
print(f"'in' en set: {set_time:.4f}s")
if __name__ == "__main__":
demo_basic_methods()
print("---")
demo_sort_vs_sorted()
print("---")
benchmark_append_vs_insert()
print("---")
demo_membership_cost()
Lo que revela cada decisión
append vs insert(0, x) no es una diferencia de conveniencia, es una diferencia de complejidad algorítmica. El benchmark lo vuelve tangible: con 100 000 elementos, insert(0, x) en bucle puede ser 100× más lento que append. Si necesitas insertar frecuentemente al frente, la herramienta correcta es collections.deque, que mantiene O(1) en ambos extremos.
remove(x) hace dos cosas: busca la primera ocurrencia (O(n)) y luego desplaza los elementos posteriores (O(n) en el peor caso). Doble costo, una sola línea. Si el elemento no existe, lanza ValueError sin previo aviso, lo que hace que valide primero con in o uses un bloque try/except según el contexto.
pop() sin argumento es O(1) porque extrae el último elemento y reduce el contador de longitud sin mover nada. pop(0) es O(n) por la misma razón que insert(0, x): desplazamiento completo.
La distinción sort() / sorted() refleja un patrón más amplio en Python: los métodos que mutan retornan None deliberadamente, para evitar el antipatrón de encadenar llamadas sobre una lista que ya cambió de estado. Si ves result = mi_lista.sort(), result es None y has perdido la referencia a la lista original si no la guardaste antes.
La estabilidad de Timsort no es un detalle académico. Cuando ordenas registros por múltiples criterios aplicando sort() varias veces en orden inverso de prioridad, la estabilidad garantiza que el orden de los niveles anteriores se preserva. Sin estabilidad, necesitarías una clave compuesta desde el principio.
Errores que debes conocer
Error: asignar el resultado de sort() a una variable, asumiendo que devuelve la lista ordenada.
# ❌ Wrong numbers = [3, 1, 2] sorted_numbers = numbers.sort() print(sorted_numbers) # None # ✅ Right numbers = [3, 1, 2] sorted_numbers = sorted(numbers) # nueva lista ordenada print(sorted_numbers) # [1, 2, 3]
sort() retorna None porque muta in-place; sorted() es la función que devuelve la lista nueva.
Error: usar in sobre una lista grande dentro de un bucle cuando la colección no cambia, ignorando el costo O(n) por consulta.
# ❌ Wrong — O(n²) total si valid_ids tiene n elementos valid_ids = [1, 2, 3, ..., 100_000] results = [x for x in records if x.id in valid_ids] # ✅ Right — O(n) total: convertir a set una vez, cada lookup O(1) valid_ids_set = set(valid_ids) results = [x for x in records if x.id in valid_ids_set]
Convertir a set antes del bucle cambia la búsqueda de lineal a hash lookup; el costo de construcción del set (O(n)) se amortiza inmediatamente en la primera iteración.
Error: modificar una lista mientras se itera sobre ella con for, causando saltos silenciosos de elementos.
# ❌ Wrong — el índice interno avanza aunque la lista encoge; se saltan elementos
nums = [1, 2, 3, 4, 5]
for n in nums:
if n % 2 == 0:
nums.remove(n) # modifica la lista bajo el iterador
print(nums) # [1, 3, 5] parece correcto aquí, pero con [2, 4, 6] falla
# ✅ Right — itera sobre una copia o construye una lista nueva
nums = [1, 2, 3, 4, 5]
nums = [n for n in nums if n % 2 != 0]
print(nums) # [1, 3, 5] siempre correcto
La list comprehension crea una nueva lista en lugar de mutar la que está siendo recorrida, eliminando el problema de índices desfasados.
N° 40