Algoritmos y estructuras de datos en JavaScript: guía práctica

Algoritmos y estructuras de datos en JavaScript: de la teoría a la práctica

Saber trabajar con algoritmos y estructuras de datos es una habilidad clave para cualquier desarrollador, independientemente del lenguaje de programación. JavaScript (especialmente en el entorno Node.js) no es una excepción. En este artículo, analizaremos las estructuras de datos fundamentales y los algoritmos clásicos, implementándolos en JavaScript puro. Verás cómo se aplican la pila, la cola, la lista enlazada, el árbol y los algoritmos de ordenamiento/búsqueda en problemas reales de desarrollo backend con Node.js.

1. Pila y cola: estructuras básicas para la gestión de datos

La pila (Stack) y la cola (Queue) son estructuras de datos lineales que se diferencian por las reglas de agregar y eliminar elementos. La pila funciona bajo el principio LIFO (Last In, First Out), mientras que la cola sigue el principio FIFO (First In, First Out).

Implementación de una pila en JavaScript

En JavaScript, una pila se puede implementar basándose en un array o en una lista enlazada. Veamos una opción simple con un array:

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Ejemplo de uso\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

La pila se utiliza a menudo para verificar el balance de paréntesis, implementar el botón "Atrás" en un navegador o para recorrer árboles en profundidad.

Implementación de una cola en JavaScript

La cola también se puede construir con un array, pero para un mejor rendimiento (evitando la reindexación con shift) usamos una lista enlazada o dos pilas. Aquí hay una implementación simple con un array:

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Ejemplo de uso\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

Las colas se utilizan en sistemas de gestión de tareas, en algoritmos BFS (recorrido en anchura) y para el almacenamiento en búfer de datos en Node.js (por ejemplo, streams).

2. Lista enlazada: estructura dinámica para inserciones frecuentes

La lista enlazada (Linked List) es una secuencia de nodos, cada uno de los cuales contiene datos y una referencia al siguiente nodo. A diferencia de un array, la inserción y eliminación de elementos en medio de la lista se realizan en O(1) si se tiene una referencia al nodo.

Implementación de una lista simplemente enlazada

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n