8 - Comparativa entre pilas con listas y pilas enlazadas

Contexto y elección

En Python podemos implementar una pila con una lista (o deque) o con una estructura enlazada propia. Ambas ofrecen operaciones O(1) en el tope, pero difieren en memoria, previsibilidad y cómo manejan el crecimiento. Elegir a tiempo evita refactors innecesarios.

8.1 Resumen rápido

Criterio Lista / deque Lista enlazada
Memoria Contigua; overhead interno pequeño Nodo a nodo; un enlace extra por elemento
Crecimiento Dinámico; deque evita realocaciones grandes Bajo demanda, solo limitado por RAM
Operaciones append/pop O(1) amortizado; deque O(1) firme push/pop O(1) siempre
Complejidad de código Mínima; sin clases extra Requiere nodos y manejo de referencias
Casos ideales Historias acotadas, cargas intensivas, simplicidad Tamaños impredecibles, fines didácticos, evitar bloques contiguos

8.2 Comparación de uso práctico

Podemos mantener la misma interfaz y alternar entre implementaciones según el escenario. El siguiente ejemplo define una función que recibe cualquier pila que implemente push, pop y esta_vacia:

def procesar(pila):
  for valor in (1, 2, 3):
    pila.push(valor)
  while not pila.esta_vacia():
    print("Pop:", pila.pop())


# Con lista
from collections import deque


class PilaLista:
  def __init__(self):
    self._datos = deque()
  def push(self, v):
    self._datos.append(v)
  def pop(self):
    return self._datos.pop()
  def esta_vacia(self):
    return not self._datos


# Con nodos enlazados
class Nodo:
  def __init__(self, valor, sig=None):
    self.valor = valor
    self.sig = sig


class PilaEnlazada:
  def __init__(self):
    self.tope = None
  def push(self, v):
    self.tope = Nodo(v, self.tope)
  def pop(self):
    if not self.tope:
      raise IndexError("Pila vacia")
    valor = self.tope.valor
    self.tope = self.tope.sig
    return valor
  def esta_vacia(self):
    return self.tope is None


procesar(PilaLista())
procesar(PilaEnlazada())

Mientras la interfaz se conserve, el código consumidor no se entera de la representación. Esto permite iniciar con listas y migrar a nodos sin tocar la lógica de negocio.

Abrir editor online

8.3 Errores frecuentes

  • Listas/deque: usar pop(0) en lugar de pop() (desplaza todo); olvidar que deque ofrece append/pop constantes.
  • Listas enlazadas: no validar pila vacía antes de pop/peek; perder la referencia al tope antes de enlazar el nuevo nodo.
  • General: mezclar responsabilidades de memoria con lógica de negocio; no documentar la capacidad máxima (si existe) ni probar los edge cases de vacío y overflow.

8.4 ¿Cuándo preferir cada una?

  • Lista/deque: elige esta opción por defecto; ideal para aplicaciones web, CLIs y scripts donde la simplicidad y el rendimiento predecible importan.
  • Lista enlazada: útil en ejercicios académicos, visualizadores de estructuras, o si deseas evitar bloques contiguos (por ejemplo, en flujos muy grandes o impredecibles).
  • Concurrencia: para hilos usa queue.LifoQueue, que incorpora locks y límite opcional.

La elección puede ser incremental: comienza con list/deque y cambia a nodos solo si los requisitos lo demandan.

Retornar