Estructuras de datos esenciales para entender algoritmos

Una estructura de datos no es solo un lugar donde guardar valores. Es una decisión sobre qué operaciones serán baratas, qué reglas deben mantenerse y cuánto espacio estamos dispuestos a usar.

El mismo conjunto de datos puede vivir en un array, un Set, un Map, un heap o un grafo. La elección correcta depende menos del nombre del algoritmo y más de la pregunta que el sistema repetirá: acceder por posición, comprobar pertenencia, extraer una prioridad o recorrer relaciones.

Elige una estructura por su operación dominante y sus invariantes, no por familiaridad.

01. Estructuras de datos en 30 segundos

Antes de comparar costos conviene separar tres conceptos:

• Modelo: describe el problema. Un grafo representa entidades conectadas.
• Interfaz o tipo abstracto: define cómo se usa. Una stack expone una disciplina LIFO; una queue, FIFO.
• Representación: decide cómo se almacena. Un grafo puede usar una lista o una matriz de adyacencia; una queue puede usar un buffer circular.

Por eso una estructura no tiene una complejidad universal. Una queue implementada con shift() no se comporta igual que una queue con índices de inicio y fin.

Esta tabla es un punto de partida, no una receta. El tamaño de los datos, la memoria, el orden y la frecuencia de cada operación pueden cambiar la decisión.

Mapa visual que relaciona la operación dominante con la estructura de datos adecuada

02. Una decisión, cuatro costos

Para evaluar una estructura pregunta cuánto cuestan acceso, búsqueda, inserción y eliminación. Estas son referencias habituales, no promesas independientes de la implementación:

En JavaScript, Map y Set preservan el orden de inserción al iterar, pero eso no significa que ordenen sus claves. Su rendimiento suele aproximarse a O(1) para consultar, insertar y eliminar; la especificación exige acceso promedio sublineal, no una estrategia concreta de hashing.

También importa la memoria. Un índice auxiliar puede convertir muchas búsquedas lineales en consultas rápidas, pero duplica parte de la información y debe mantenerse sincronizado.

Comparación técnica de los costos de operación de arrays, mapas, heaps y árboles balanceados

03. Secuencias y fronteras

Un array funciona bien cuando el orden y el acceso por índice importan. Leer items[20] es directo; buscar un valor requiere recorrer hasta encontrarlo. Insertar o eliminar en medio suele desplazar elementos.

Una stack restringe la secuencia a una sola frontera. En JavaScript, push() y pop() ofrecen una implementación natural:

const history: string[] = [];

history.push("open-project");
history.push("edit-title");

const lastAction = history.pop(); // "edit-title"

Esta disciplina aparece en undo, navegación, evaluación de expresiones y recorridos en profundidad.

Una queue trabaja en dos fronteras: agrega al final y consume desde el inicio. Usar shift() puede exigir reindexar elementos. Para una cola duradera, podemos guardar índices explícitos y eliminar cada valor consumido:

class Queue<T> {
  private items = new Map<number, T>();
  private head = 0;
  private tail = 0;

  enqueue(value: T) {
    this.items.set(this.tail, value);
    this.tail += 1;
  }

  dequeue(): T | undefined {
    if (this.head === this.tail) return undefined;

    const value = this.items.get(this.head);
    this.items.delete(this.head);
    this.head += 1;

    if (this.head === this.tail) {
      this.head = 0;
      this.tail = 0;
    }

    return value;
  }

  get size() {
    return this.tail - this.head;
  }
}

En sistemas sensibles a memoria o rendimiento, un buffer circular sobre un array evita tanto el desplazamiento como el costo adicional de un Map. La interfaz sigue siendo una queue; cambia su representación.

04. Identidad y pertenencia

Recorrer un array para responder muchas veces “¿existe este valor?” repite trabajo. Set expresa pertenencia; Map expresa la relación entre una clave y un valor.

type User = { id: string; name: string };

function indexUsers(users: User[]) {
  return new Map(users.map((user) => [user.id, user]));
}

const usersById = indexUsers(users); // O(n) una vez
const user = usersById.get("usr_42"); // O(1) esperado

const selectedIds = new Set(["usr_12", "usr_42"]);
const isSelected = selectedIds.has("usr_42"); // O(1) esperado

El intercambio es claro: construir el índice cuesta O(n) y usa memoria adicional. Compensa cuando la misma colección recibe muchas consultas. Para una única búsqueda sobre pocos elementos, el array puede ser más simple y suficientemente rápido.

Con objetos, Map y Set comparan identidad de referencia:

const visited = new Set<object>();
visited.add({ id: 7 });

visited.has({ id: 7 }); // false: es otro objeto

Si dos objetos distintos representan la misma entidad, usa una clave estable como id. Si necesitas que una clave basada en objeto no impida su liberación por el recolector de basura, considera WeakMap o WeakSet, aceptando que no son iterables.

05. Prioridad, jerarquía y relaciones

Cuando la pregunta deja de ser “¿en qué posición está?” aparecen estructuras con invariantes más específicos:

Comparación visual de los invariantes de heap, árbol, trie y grafo

Un heap no es un array ordenado. Solo garantiza que el mínimo o máximo esté disponible en la raíz; el resto conserva el orden parcial necesario para restaurar esa propiedad. JavaScript no incluye un heap nativo, por lo que suele implementarse o incorporarse mediante una librería.

Un árbol binario de búsqueda solo mantiene O(log n) si su altura permanece controlada. Insertar datos en orden en un árbol simple puede convertirlo en una lista y degradar sus operaciones a O(n). Estructuras balanceadas como AVL o red-black trees evitan ese caso.

Un trie mide sus búsquedas según L, la longitud de la clave, pero puede consumir mucha memoria. Es útil cuando el prefijo es una operación del producto, no solo porque las claves sean strings.

En un grafo, la representación depende de su densidad. Una lista de adyacencia usa O(V + E) de memoria y permite recorrer los vecinos de un nodo en O(deg(v)):

class Graph {
  private edges = new Map<string, Set<string>>();

  connect(a: string, b: string) {
    if (!this.edges.has(a)) this.edges.set(a, new Set());
    if (!this.edges.has(b)) this.edges.set(b, new Set());

    this.edges.get(a)!.add(b);
    this.edges.get(b)!.add(a);
  }

  neighbors(node: string) {
    return this.edges.get(node) ?? new Set<string>();
  }
}

Para un grafo muy denso, una matriz de adyacencia usa O(V²) de memoria, pero responde si dos nodos están conectados en O(1). BFS y DFS sobre una lista de adyacencia recorren O(V + E) porque visitan cada nodo y cada arista como máximo un número constante de veces.

06. Checklist para elegir

Antes de cambiar de estructura, responde:

1. ¿Cuál es la operación dominante: acceso, búsqueda, inserción, eliminación, prioridad, rango o recorrido?
2. ¿Qué debe permanecer cierto: orden, unicidad, FIFO, LIFO, balance o conectividad?
3. ¿Cuántas veces se construye la estructura y cuántas veces se consulta?
4. ¿Cuál es el tamaño máximo realista de n, V y E?
5. ¿Puedes intercambiar memoria por menos trabajo repetido?
6. ¿Necesitas orden de inserción, orden por clave o ningún orden?
7. ¿La implementación de tu lenguaje sostiene la complejidad que esperas?

Empieza por la estructura más simple que exprese el problema. Cambia cuando una operación dominante, una invariante o una medición real lo justifique. Un Map no mejora automáticamente un array; un heap no reemplaza un ordenamiento completo; un grafo no necesita una clase compleja si una lista de adyacencia basta.

La pregunta final no es “¿qué estructura es más rápida?”. Es “¿qué estructura hace barata la operación que mi sistema repite sin ocultar un costo más importante?”.