Estructuras de datos · #6 de 11

Listas + tuplas

Colecciones ordenadas y métodos esenciales

Por qué importa

Las listas son el contenedor por defecto para la mayoría de los problemas. Las tuplas resguardan los datos de forma segura.

La idea

Las listas son estantes flexibles; las tuplas son cajas selladas. Las tuplas son hashables (pueden ser claves de diccionario, miembros de conjunto), las listas no.

Pruébalo

Conceptos básicos de listas: append, extend, rebanado, comprensión:

xs = [1, 2, 3]
xs.append(4)          # in place
xs.extend([5, 6])     # in place
xs += [7]             # in place too
print(xs)

# Comprehension — the Pythonic loop
squares = [x*x for x in xs if x % 2 == 0]
print(squares)
not loaded

Las tuplas son inmutables, admiten desempaquetado y pueden ser claves de diccionario:

origin = (0, 0)
def move(point, dx, dy):
  x, y = point        # unpacking
  return (x + dx, y + dy)

print(move(origin, 3, 4))

routes = { (0, 0): "home", (3, 4): "park" }
print(routes[(3, 4)])
not loaded

Ordenamiento: en el sitio frente a devolver una nueva:

words = ["apple", "Banana", "cherry"]
print(sorted(words))                      # case-sensitive
print(sorted(words, key=str.lower))       # case-insensitive
print(sorted(words, key=len, reverse=True))

# In place — returns None! (common bug)
words.sort()
print(words)
not loaded

Métodos de lista (esenciales completos)

| Método | Qué hace | Ejemplo | | --- | --- | --- | | append(x) | agregar un elemento | nums.append(5) | | extend(iter) | agregar varios | nums.extend([6,7]) | | insert(i,x) | agregar en un índice | nums.insert(1, 42) | | remove(x) | quitar la primera coincidencia | nums.remove(2) | | pop(i) | quitar por índice | nums.pop() | | clear() | quitar todo | nums.clear() | | index(x) | encontrar la posición | nums.index(3) | | count(x) | contar un valor | nums.count(3) | | sort() | ordenar en el sitio | nums.sort() | | reverse() | invertir en el sitio | nums.reverse() | | copy() | copia superficial | nums.copy() |

La lista como pila / cola

Una lista funciona bien como pila (append / pop por el final). Para una cola rápida, recurre a collections.deque: sacar del frente de una lista es O(n):

from collections import deque
q = deque([1, 2, 3])
q.append(4)     # enqueue
q.popleft()     # dequeue — O(1)

Copia frente a alias (importante)

a = [1, 2, 3]
b = a          # alias — same list, mutations are shared
c = a.copy()   # new list — independent

La trampa de las listas anidadas

[[0] * 3] * 3 repite la misma fila interior tres veces: mutar una muta todas:

grid = [[0] * 3] * 3   # WRONG: shared rows
grid = [[0] * 3 for _ in range(3)]  # correct: independent rows

Verificación rápida

Mini ejercicios

Buenas y malas prácticas

Profundizando — vistazo de complejidad
  • Acceso por índice: O(1)
  • Append: O(1) amortizado
  • Insertar/quitar al frente: O(n)
  • Pertenencia (x in lst): O(n)

Errores comunes

Conclusiones clave