Estructuras de datos: listas, pilas, colas, diccionarios y árboles

Introducción

Un programa casi nunca trabaja con un solo dato: gestiona listas de alumnos, historiales de navegación, colas de impresión, mapas con millones de calles... La forma en que se organizan esos datos en memoria es una estructura de datos, y elegir bien una u otra puede marcar la diferencia entre un programa que responde al instante y otro que tarda minutos.

En este artículo recorrerás las estructuras fundamentales, listas, listas enlazadas, pilas, colas, diccionarios y árboles, con ejemplos en Python ejecutados (las salidas mostradas son reales), y aprenderás a decidir cuál usar. Para medir la velocidad de cada operación se usa la notación O grande, que se explica en el artículo de complejidad algorítmica.

Las cuatro estructuras que veremos, de forma esquemática.

1. Listas o arrays

Una lista (o array) guarda sus elementos uno detrás de otro en memoria, numerados desde 0. Su gran ventaja es el acceso directo: pedir el elemento número 2 es inmediato, sin recorrer los anteriores. Su inconveniente es que insertar o borrar en medio obliga a desplazar todos los elementos siguientes.

numeros = [10, 20, 30]
numeros.append(40)          # al final: rápido
numeros.insert(1, 15)       # en medio: hay que desplazar los elementos siguientes
print(numeros)
print(numeros[2])           # acceso directo por posición

Salida:

[10, 15, 20, 30, 40]
20

2. Listas enlazadas

En una lista enlazada los datos no están seguidos en memoria: cada nodo guarda su valor y una referencia al siguiente. Insertar al principio es muy barato (solo se cambia un enlace), pero para llegar al elemento número 1000 hay que recorrer los 999 anteriores.

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


# 10 -> 20 -> 30
lista = Nodo(10, Nodo(20, Nodo(30)))
lista = Nodo(5, lista)      # insertar al principio: solo cambia un enlace

actual = lista
while actual is not None:
    print(actual.valor, end=" ")
    actual = actual.siguiente

Salida (se recorre la lista nodo a nodo):

5 10 20 30

3. Pilas (LIFO)

Una pila funciona como una torre de platos: el último en entrar es el primero en salir (LIFO, Last In First Out). Solo se opera por la cima con dos acciones: push (apilar) y pop (desapilar). Se usan para el botón «deshacer», el historial de páginas, evaluar expresiones y gestionar las llamadas a funciones de un programa.

pila = []
pila.append("A")            # apilar (push)
pila.append("B")
pila.append("C")
print(pila.pop())           # desapilar (pop): sale el último en entrar
print(pila[-1])             # mirar la cima sin quitarla (peek)

Salida:

C
B

4. Colas (FIFO)

Una cola funciona como la fila de un mostrador: el primero en llegar es el primero en ser atendido (FIFO, First In First Out). Se encola por un extremo y se desencola por el otro. Aparece en las colas de impresión, en los turnos de un sistema operativo y en las peticiones que recibe un servidor. En Python se usa collections.deque, que es eficiente en ambos extremos (con una lista normal, quitar el primer elemento es lento).

from collections import deque

cola = deque()
cola.append("Ana")          # encolar: se añade al final
cola.append("Luis")
cola.append("Eva")
print(cola.popleft())       # desencolar: sale el primero en entrar
print(list(cola))

Salida:

Ana
['Luis', 'Eva']

5. Diccionarios (tablas hash)

Un diccionario guarda pares clave → valor y permite recuperar un valor directamente con su clave, sin recorrer nada. Por dentro usa una función hash que transforma la clave en una posición, de modo que, en promedio, buscar, insertar y borrar tardan lo mismo con 10 elementos que con 10 millones. Es la estructura más útil en la práctica: contar frecuencias, guardar la configuración, indexar por identificador...

frase = "el gato y el perro y el pez"
conteo = {}
for palabra in frase.split():
    conteo[palabra] = conteo.get(palabra, 0) + 1
print(conteo)
print(conteo["el"])         # acceso directo por clave

Salida:

{'el': 3, 'gato': 1, 'y': 2, 'perro': 1, 'pez': 1}
3

6. Árboles

Un árbol organiza los datos de forma jerárquica: tiene una raíz de la que cuelgan nodos hijos, y los nodos sin hijos son hojas. Es el modelo de las carpetas de un ordenador o de la estructura de una página web. En un árbol binario de búsqueda cada nodo tiene como máximo dos hijos y se cumple que los valores menores van a la izquierda y los mayores a la derecha; así, en cada paso se descarta aproximadamente la mitad de los datos.

class Nodo:
    def __init__(self, valor):
        self.valor = valor
        self.izq = None
        self.der = None


def insertar(raiz, valor):
    if raiz is None:
        return Nodo(valor)
    if valor < raiz.valor:
        raiz.izq = insertar(raiz.izq, valor)
    else:
        raiz.der = insertar(raiz.der, valor)
    return raiz


def en_orden(nodo):
    if nodo is None:
        return []
    return en_orden(nodo.izq) + [nodo.valor] + en_orden(nodo.der)


def buscar(raiz, valor):
    comparaciones = 0
    while raiz is not None:
        comparaciones += 1
        if valor == raiz.valor:
            return True, comparaciones
        raiz = raiz.izq if valor < raiz.valor else raiz.der
    return False, comparaciones


raiz = None
for v in [50, 30, 70, 20, 40, 60, 80]:
    raiz = insertar(raiz, v)

print(en_orden(raiz))
print(buscar(raiz, 60))
print(buscar(raiz, 65))

Salida:

[20, 30, 40, 50, 60, 70, 80]
(True, 3)
(False, 3)

Recorrer el árbol «en orden» (izquierda, nodo, derecha) devuelve los valores ya ordenados. Para buscar el 60 solo se visitan 3 nodos (50, 70 y 60) de los 7 que hay: cada comparación descarta una rama entera. Si el árbol está equilibrado, buscar entre $n$ elementos cuesta del orden de $\log_2 n$ comparaciones.

7. ¿Cuál elijo? Comparación

8. Ejemplo resuelto: ¿están bien cerrados los paréntesis?

Enunciado. Comprueba si una expresión tiene los paréntesis, corchetes y llaves correctamente emparejados. Por ejemplo, (a+b)*[c-d] es correcta, pero (a+b] no.

Idea. Una pila es la estructura perfecta: cada vez que aparece un símbolo de apertura se apila; cada vez que aparece uno de cierre, debe coincidir con el que está en la cima de la pila (el último abierto). Si al final la pila está vacía, todo estaba bien emparejado.

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


print(balanceado("(a+b)*[c-d]"))
print(balanceado("(a+b]"))
print(balanceado("((a+b)"))

Salida:

True
False
False

Traza de la ejecución para la expresión ([]):

La pila acaba vacía, así que la expresión es correcta. En ((a+b) sobra un paréntesis de apertura: la pila no queda vacía y la función devuelve False.

9. Errores frecuentes

• ⚠️ Usar una lista como cola. Quitar el primer elemento de una lista obliga a desplazar todos los demás; para colas usa deque
• ⚠️ Confundir pila y cola. Pila: sale el último que entró (LIFO). Cola: sale el primero que entró (FIFO)
• ⚠️ Buscar en una lista cuando necesitas un diccionario. Si buscas por clave muchas veces, un diccionario evita recorrer la lista entera cada vez
• ⚠️ Desapilar una pila vacía. Provoca un error. Comprueba siempre que no está vacía antes de hacer pop()
• ⚠️ Creer que un árbol de búsqueda siempre es rápido. Si se insertan los datos ya ordenados, el árbol degenera en una lista y buscar vuelve a costar O(n); por eso existen los árboles equilibrados

10. 📌 En 30 segundos

1. Lista: acceso directo por posición, pero insertar en medio es lento.
2. Lista enlazada: inserción rápida al principio, pero para acceder hay que recorrerla.
3. Pila = LIFO (deshacer, recursión). Cola = FIFO (turnos, impresión).
4. Diccionario: búsqueda por clave en tiempo casi constante; la estructura más usada.
5. Árbol binario de búsqueda equilibrado: búsqueda en O(log n) y datos ordenados.

Para seguir estudiando

• Programación orientada a objetos: clases, objetos, herencia y polimorfismo
• Complejidad algorítmica y notación O grande
• Introducción a algoritmos y pseudocódigo