Listas enlazadas, pilas y colas

📐 Fundamento

class Nodo:
    def __init__(self, dato, siguiente=None):
        self.dato = dato
        self.siguiente = siguiente


class ListaEnlazada:
    def __init__(self):
        self.cabeza = None
        self.tamano = 0

    def insertar_inicio(self, x):
        self.cabeza = Nodo(x, self.cabeza)
        self.tamano += 1

    def insertar_final(self, x):
        nuevo = Nodo(x)
        if self.cabeza is None:
            self.cabeza = nuevo
        else:
            actual = self.cabeza
            while actual.siguiente is not None:
                actual = actual.siguiente
            actual.siguiente = nuevo
        self.tamano += 1

    def buscar(self, x):
        actual = self.cabeza
        while actual is not None:
            if actual.dato == x:
                return actual
            actual = actual.siguiente
        return None

    def eliminar(self, x):
        actual = self.cabeza
        anterior = None
        while actual is not None and actual.dato != x:
            anterior = actual
            actual = actual.siguiente
        if actual is None:
            return False
        if anterior is None:
            self.cabeza = actual.siguiente
        else:
            anterior.siguiente = actual.siguiente
        self.tamano -= 1
        return True

    def __len__(self):
        return self.tamano

    def __iter__(self):
        actual = self.cabeza
        while actual is not None:
            yield actual.dato
            actual = actual.siguiente

Visualización:

cabeza → [A | →] → [B | →] → [C | →] → None

Análisis:

• insertar_inicio: $O(1)$.
• insertar_final: $O(n)$ — recorre hasta el final. Mejorable guardando cola.
• buscar, eliminar: $O(n)$.
• Acceso por índice: $O(n)$ (no implementado arriba pero sería igual).

Optimización: guardar puntero al final.

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None
        self.cola = None
        self.tamano = 0

    def insertar_final(self, x):
        nuevo = Nodo(x)
        if self.cola is None:
            self.cabeza = self.cola = nuevo
        else:
            self.cola.siguiente = nuevo
            self.cola = nuevo
        self.tamano += 1

Ahora insertar_final es $O(1)$.

📐 Fundamento

Cada nodo tiene puntero al anterior y al siguiente.

class NodoDoble:
    def __init__(self, dato):
        self.dato = dato
        self.anterior = None
        self.siguiente = None


class ListaDoble:
    def __init__(self):
        self.cabeza = None
        self.cola = None
        self.tamano = 0

    def insertar_final(self, x):
        nuevo = NodoDoble(x)
        if self.cola is None:
            self.cabeza = self.cola = nuevo
        else:
            nuevo.anterior = self.cola
            self.cola.siguiente = nuevo
            self.cola = nuevo
        self.tamano += 1

    def eliminar_nodo(self, nodo):
        """Elimina el nodo dado en O(1)."""
        if nodo.anterior:
            nodo.anterior.siguiente = nodo.siguiente
        else:
            self.cabeza = nodo.siguiente
        if nodo.siguiente:
            nodo.siguiente.anterior = nodo.anterior
        else:
            self.cola = nodo.anterior
        self.tamano -= 1

Ventaja clave: eliminar un nodo dado es $O(1)$ — sin recorrer.

Trade-off: doble memoria por nodo (dos punteros).

Aplicación: caché LRU usa lista doble + dict para insertar/eliminar/mover-a-frente en $O(1)$. Una de las estructuras más usadas en sistemas reales.

Python's deque (collections.deque) es una lista doble optimizada. La mayoría de las veces, usá deque en vez de implementar tu propia.

📐 Fundamento

LIFO = Last In, First Out. El último que entró es el primero que sale. Como una pila de platos.

Operaciones esenciales:

• push(x) — agregar arriba.
• pop() — sacar el de arriba.
• peek() (o top()) — mirar el de arriba sin sacarlo.

Todas $O(1)$.

Implementación con array:

class Pila:
    def __init__(self):
        self.items = []

    def push(self, x):
        self.items.append(x)

    def pop(self):
        if not self.items:
            raise IndexError("pila vacía")
        return self.items.pop()

    def peek(self):
        if not self.items:
            raise IndexError("pila vacía")
        return self.items[-1]

    def __len__(self):
        return len(self.items)

En Python, una list ya es una pila eficiente: append para push, pop() para pop. No necesitás implementar tu propia salvo por motivos didácticos.

Implementación con lista enlazada: push/pop al frente.

class PilaEnlazada:
    def __init__(self):
        self.cabeza = None
        self._n = 0

    def push(self, x):
        self.cabeza = Nodo(x, self.cabeza)
        self._n += 1

    def pop(self):
        if self.cabeza is None:
            raise IndexError("pila vacía")
        x = self.cabeza.dato
        self.cabeza = self.cabeza.siguiente
        self._n -= 1
        return x

Aplicaciones

Validar paréntesis:

def balanceados(s):
    pila = []
    pares = {")": "(", "]": "[", "}": "{"}
    for c in s:
        if c in "([{":
            pila.append(c)
        elif c in ")]}":
            if not pila or pila.pop() != pares[c]:
                return False
    return not pila

print(balanceados("({[]})"))    # True
print(balanceados("([)]"))       # False

Otras aplicaciones:

• Llamadas a función (call stack).
• Undo / Redo.
• Evaluación de expresiones (parsers, calculadoras).
• DFS (profundidad).
• Backtracking.

📐 Fundamento

FIFO = First In, First Out. El primero que entró es el primero que sale. Como una cola de gente.

Operaciones:

• enqueue(x) — agregar al final.
• dequeue() — sacar del frente.

Trampa con array: dequeue() con pop(0) es $O(n)$ — Python tiene que mover todo. Inadecuado para colas.

Solución: deque (double-ended queue, collections.deque):

from collections import deque

cola = deque()
cola.append("a")        # enqueue: O(1)
cola.append("b")
cola.append("c")
print(cola.popleft())   # dequeue: O(1) → "a"

deque es una lista doblemente enlazada interna optimizada — append y popleft son ambos $O(1)$.

Implementación con lista enlazada:

class Cola:
    def __init__(self):
        self.cabeza = None
        self.cola_ptr = None
        self._n = 0

    def enqueue(self, x):
        nuevo = Nodo(x)
        if self.cola_ptr is None:
            self.cabeza = self.cola_ptr = nuevo
        else:
            self.cola_ptr.siguiente = nuevo
            self.cola_ptr = nuevo
        self._n += 1

    def dequeue(self):
        if self.cabeza is None:
            raise IndexError("cola vacía")
        x = self.cabeza.dato
        self.cabeza = self.cabeza.siguiente
        if self.cabeza is None:
            self.cola_ptr = None
        self._n -= 1
        return x

Aplicaciones

• BFS (búsqueda en anchura).
• Schedulers del SO (Round Robin).
• Sistemas de mensajería (RabbitMQ, Kafka).
• Buffers entre productor y consumidor.
• Impresoras, peticiones HTTP.

Cola con prioridad (vista rápida)

A veces querés sacar el más prioritario, no el más viejo.

import heapq

cola = []
heapq.heappush(cola, (3, "tarea normal"))
heapq.heappush(cola, (1, "URGENTE"))
heapq.heappush(cola, (2, "importante"))

while cola:
    prio, tarea = heapq.heappop(cola)
    print(prio, tarea)
# 1 URGENTE
# 2 importante
# 3 tarea normal

heapq implementa un heap binario — operaciones en $O(\log n)$. Lo veremos en el cap 3.