Estructuras de datos en JavaScript

En este artículo vamos a echar un vistazo a un tema clave en lo que respecta a la informática y el desarrollo de software: las estructuras de datos. En concreto, estructuras de datos en JavaScript.

Obviamente es un tema que debe conocer cualquier persona que trabaje en el mundo del desarrollo de software, pero puede ser difícil de entender e incluso un poco intimidante cuando se está comenzando.

En este artículo intentaré dar una explicación sencilla de las estructuras de datos, qué son, cuándo son útiles y cómo podemos implementarlas usando JavaScript.

Estructuras de datos en JavaScript

En informática, una estructura de datos es un formato para organizar, administrar y almacenar datos de manera que permita un acceso y modificación eficientes.

Más precisamente, una estructura de datos es una colección de valores de datos, las relaciones entre ellos y las funciones u operaciones que se pueden aplicar a esos datos.

Estas descripciones pueden sonar un poco abstractas al principio, pero piénsalo. Si ha estado codificando por un tiempo, debe haber usado estructuras de datos antes.

¿Ha utilizado matrices y objetos? Esas son estructuras de datos. Todos ellos son una colección de valores que se relacionan entre sí y pueden ser usadas por ti.

// A collection of the values 1, 2 and 3
const arr = [1, 2, 3]

// Each value is related to one another, in the sense that each is indexed in a position of the array
const indexOfTwo = arr.indexOf(2)
console.log(arr[indexOfTwo-1]) // 1
console.log(arr[indexOfTwo+1]) // 3

// We can perform many operations on the array, like pushing new values into it
arr.push(4)
console.log(arr) // [1,2,3,4]

JavaScript tiene estructuras de datos primitivas (integradas) y no primitivas (no integradas).

Las estructuras de datos primitivas vienen de forma predeterminada con el lenguaje de programación y puede implementarlas de forma inmediata (como matrices y objetos). Las estructuras de datos no primitivas no vienen por defecto y tienes que codificarlas si quieres usarlas.

Existen diferentes estructuras de datos porque algunas de ellas son más adecuadas para cierto tipo de operaciones. Probablemente podrá abordar la mayoría de las tareas de programación con estructuras de datos primitivas, pero para algunas tareas muy específicas, una estructura de datos no primitiva puede ser útil.

Ahora repasemos las estructuras de datos más populares que existen y veamos cómo funciona cada una de ellas, en qué ocasiones son útiles y cómo podemos codificarlas en JavaScript.

Arrays

Un array o matriz es una colección de elementos almacenados en ubicaciones de memoria contiguas.

Se puede acceder a cada elemento a través de su número de índice (posición) y siempre comienzan en el índice 0, por lo que en una matriz de 4 elementos podríamos acceder al tercer elemento usando el número de índice 2.

const arr = ['a', 'b', 'c', 'd']
console.log(arr[2]) // c

La propiedad length de longitud de un array se define como el número de elementos que contiene. Si el array contiene 4 elementos, podemos decir que tiene una longitud de 4.

const arr = ['a', 'b', 'c', 'd']
console.log(arr.length) // 4

En algunos lenguajes de programación, el usuario solo puede almacenar valores del mismo tipo en una matriz y la longitud de la matriz debe definirse en el momento de su creación y no puede modificarse después.

En JavaScript ese no es el caso, ya que podemos almacenar valores de cualquier tipo en la misma matriz y la longitud de la misma puede ser dinámica (puede crecer o reducirse tanto como sea necesario).

const arr = ['store', 1, 'whatever', 2, 'you want', 3]

Cualquier tipo de datos se puede almacenar en un array, y eso también incluye a los propios arrays. Una matriz que tiene otras matrices dentro de sí misma se denomina matriz multidimensional (multidimensional array).

const arr = [
    [1,2,3],
    [4,5,6],
    [7,8,9],
]

En JavaScript, las matrices vienen con muchas propiedades y métodos integrados que podemos usar con diferentes propósitos, como agregar o eliminar elementos de la matriz, clasificarlos, filtrar sus valores, conocer su longitud, etc. Puede encontrar una lista completa de métodos de array aquí.

Como mencioné, en los arrays, cada elemento tiene un índice definido por su posición en el arreglo. Cuando agregamos un nuevo elemento al final de la matriz, solo toma el número de índice que sigue al último elemento anterior de la matriz.

Pero cuando agregamos/eliminamos un nuevo elemento al principio o en medio de la matriz, los índices de todos los elementos que vienen después del elemento agregado/eliminado deben cambiarse. Esto, por supuesto, tiene un costo computacional y es una de las debilidades de esta estructura de datos.

Los arrays son útiles cuando tenemos que almacenar valores individuales y agregar/eliminar valores desde el final de la estructura de datos. Pero cuando necesitamos agregar/eliminar de cualquier parte, hay otras estructuras de datos que funcionan de manera más eficiente (hablaremos de ellas más adelante).

Objects (hash tables)

En JavaScript, un objeto es una colección de pares clave-valor. Esta estructura de datos también se denomina mapa, diccionario o tabla hash en otros lenguajes de programación.

Un objeto JS típico se ve así:

const obj = {
    prop1: "I'm",
    prop2: "an",
    prop3: "object"
}

Usamos llaves para declarar el objeto. Luego declare cada clave seguida de dos puntos y el valor correspondiente. Sencillo.

Una cosa importante a mencionar es que cada clave tiene que ser única dentro del objeto. No puedes tener dos llaves con el mismo nombre.

Los objetos pueden almacenar valores y funciones. Cuando se habla de objetos, los valores se denominan propiedades y las funciones se denominan métodos.

const obj = {
    prop1: "Hello!",
    prop3: function() {console.log("I'm a property dude!")
}}

console.log(obj.prop1) // "Hello!"
console.log(obj["prop1"]) // "Hello!"
obj.prop3() // "I'm a property dude!"

Para acceder a las propiedades, puede usar dos sintaxis diferentes, ya sea object.property u object["property"]. Para acceder a los métodos llamamos object.method().

La sintaxis para asignar nuevos valores es bastante similar:

obj.prop4 = 125
obj["prop5"] = "The new prop on the block"
obj.prop6 = () => console.log("yet another example")

console.log(obj.prop4) // 125
console.log(obj["prop5"]) // "The new prop on the block"
obj.prop6() // "yet another example"

Al igual que las matrices, en JavaScript los objetos vienen con muchos métodos integrados que nos permiten realizar diferentes operaciones y obtener información de un objeto determinado. Puede encontrar una lista completa aquí.

Los objetos son una buena manera de agrupar datos que tienen algo en común o están relacionados de alguna manera. Además, gracias al hecho de que los nombres de las propiedades son únicos, los objetos resultan útiles cuando tenemos que separar los datos en función de una condición única.

Un ejemplo podría ser contar a cuántas personas son hombres y cuantos mujeres:

 

const people = {
    man: 1000,
    woman: 750
}

 

Stacks (pilas)

Las pilas son una estructura de datos que almacena información en forma de lista. Solo permiten agregar y quitar elementos bajo un patrón LIFO (last in, first out). En las pilas, los elementos no pueden agregarse o eliminarse desordenadamente, siempre deben seguir el patrón LIFO.

Para entender cómo funciona esto, imagina una pila de papeles encima de tu escritorio. Solo puede agregar más papeles a la pila colocándolos encima de todos los demás. Y puede quitar un papel de la pila solo tomando el que está encima de todos los demás. Último en entrar primero en salir. LIFO.

 

Las pilas son útiles cuando necesitamos asegurarnos de que los elementos sigan el patrón LIFO. Algunos ejemplos del uso de la pila son:

• Pila de llamadas de JavaScript 🙂
• Gestión de invocaciones de funciones en varios lenguajes de programación.
• La funcionalidad de deshacer/rehacer que ofrecen muchos programas.

Hay más de una forma de implementar una pila, pero probablemente la más simple sea usar una matriz con sus métodos push y pop. Si solo usamos pop y push para agregar y eliminar elementos, siempre seguiremos el patrón LIFO y, por lo tanto, operaremos sobre él como una pila.

Otra forma es implementarlo como una lista, que puede verse así:

// We create a class for each node within the stack
class Node {
    // Each node has two properties, its value and a pointer that indicates the node that follows
    constructor(value){
        this.value = value
        this.next = null
    }
}

// We create a class for the stack
class Stack {
    // The stack has three properties, the first node, the last node and the stack size
    constructor(){
        this.first = null
        this.last = null
        this.size = 0
    }
    // The push method receives a value and adds it to the "top" of the stack
    push(val){
        var newNode = new Node(val)
        if(!this.first){
            this.first = newNode
            this.last = newNode
        } else {
            var temp = this.first
            this.first = newNode
            this.first.next = temp
        }
        return ++this.size
    }
    // The pop method eliminates the element at the "top" of the stack and returns its value
    pop(){
        if(!this.first) return null
        var temp = this.first
        if(this.first === this.last){
            this.last = null
        }
        this.first = this.first.next
        this.size--
        return temp.value
    }
}

const stck = new Stack

stck.push("value1")
stck.push("value2")
stck.push("value3")

console.log(stck.first) /* 
        Node {
        value: 'value3',
        next: Node { value: 'value2', next: Node { value: 'value1', next: null } }
        }
    */
console.log(stck.last) // Node { value: 'value1', next: null }
console.log(stck.size) // 3

stck.push("value4")
console.log(stck.pop()) // value4

La gran O de los métodos de pila es la siguiente:

• Inserción – O(1)
• Eliminación – O(1)
• Búsqueda – O(n)
• Acceso – O(n)

Queues (colas)

Las colas funcionan de manera muy similar a las pilas, pero los elementos siguen un patrón diferente para agregar y eliminar. Las colas solo permiten un patrón FIFO (primero en entrar, primero en salir). En las colas, los elementos no se pueden agregar o quitar fuera de orden, siempre deben seguir el patrón FIFO.

Para entender esto, imagínate a la gente haciendo cola para comprar comida. La lógica aquí es que si obtienes la cola primero, serás el primero en ser atendido. Si llegas primero, serás el primero en salir. FIFO.

 

Algunos ejemplos de uso de la cola son:

• Tarea en segundo plano.
• Impresión/procesamiento de tareas.

Al igual que con las pilas, hay más de una forma de implementar una cola. Pero probablemente el más simple es usar una matriz con sus métodos push y shift.

Si solo usamos empujar y cambiar para agregar y eliminar elementos, siempre seguiremos el patrón FIFO y, por lo tanto, operaremos sobre él como una cola.

Otra forma es implementarlo como una lista es esta:

// We create a class for each node within the queue
class Node {
    // Each node has two properties, its value and a pointer that indicates the node that follows
    constructor(value){
        this.value = value
        this.next = null
    }
}

// We create a class for the queue
class Queue {
    // The queue has three properties, the first node, the last node and the stack size
    constructor(){
        this.first = null
        this.last = null
        this.size = 0
    }
    // The enqueue method receives a value and adds it to the "end" of the queue
    enqueue(val){
        var newNode = new Node(val)
        if(!this.first){
            this.first = newNode
            this.last = newNode
        } else {
            this.last.next = newNode
            this.last = newNode
        }
        return ++this.size
    }
    // The dequeue method eliminates the element at the "beginning" of the queue and returns its value
    dequeue(){
        if(!this.first) return null

        var temp = this.first
        if(this.first === this.last) {
            this.last = null
        }
        this.first = this.first.next
        this.size--
        return temp.value
    }
}

const quickQueue = new Queue

quickQueue.enqueue("value1")
quickQueue.enqueue("value2")
quickQueue.enqueue("value3")

console.log(quickQueue.first) /* 
        Node {
            value: 'value1',
            next: Node { value: 'value2', next: Node { value: 'value3', next: null } }
        }
    */
console.log(quickQueue.last) // Node { value: 'value3, next: null }
console.log(quickQueue.size) // 3

quickQueue.enqueue("value4")
console.log(quickQueue.dequeue()) // value1

La gran O de los métodos de cola es la siguiente:

• Inserción – O(1)
• Eliminación – O(1)
• Búsqueda – O(n)
• Acceso – O(n)

 

Linked lists (listas enlazadas)

Las listas enlazadas son un tipo de estructura de datos que almacenan valores en forma de lista. Dentro de la lista, cada valor se considera un nodo, y cada nodo se conecta con el siguiente valor de la lista (o nulo en caso de que el elemento sea el último de la lista) a través de un puntero.

Hay dos tipos de listas enlazadas, listas simplemente enlazadas  y listas doblemente enlazadas. Ambos funcionan de manera muy similar, pero la diferencia está en las listas simplemente enlazadas , cada nodo tiene un solo puntero que indica el siguiente nodo en la lista. Mientras que en las listas doblemente enlazadas, cada nodo tiene dos punteros, uno que apunta al siguiente nodo y otro que apunta al nodo anterior.

 

El primer elemento de la lista se considera la cabeza y el último elemento se considera la cola. Al igual que con las matrices, la propiedad de longitud se define como el número de elementos que contiene la lista.

Las principales diferencias con respecto a los arrays son las siguientes:

• Las listas no tienen índices. Cada valor solo «conoce» los valores a los que está conectado a través de los punteros.
• Dado que las listas no tienen índices, no podemos acceder a los valores de forma aleatoria. Cuando queremos acceder a un valor, siempre tenemos que buscarlo iterando a través de la lista a partir de su cabeza o cola.
• Lo bueno de no tener índices es que la inserción/eliminación en cualquier parte de la lista es más eficiente que con arrays. Solo tenemos que redirigir los punteros de los valores «vecinos», mientras que en las matrices, los valores deben volver a indexarse.

Como cualquier estructura de datos, se implementan diferentes métodos para operar sobre los datos. Los más comunes incluyen: push, pop, unshift, shift, get, set, insert, remove, y reverse.

Primero, veamos cómo implementar una lista de enlaces simples y luego una lista de enlaces dobles.

Singly linked list (lista enlazada)

Una implementación completa de una lista enlazada simplemente podría verse así:

// We create a class for each node within the list
class Node{
    // Each node has two properties, its value and a pointer that indicates the node that follows
    constructor(val){
        this.val = val
        this.next = null
    }
}

// We create a class for the list
class SinglyLinkedList{
    // The list has three properties, the head, the tail and the list size
    constructor(){
        this.head = null
        this.tail = null
        this.length = 0
    }
    // The push method takes a value as parameter and assigns it as the tail of the list
    push(val) {
        const newNode = new Node(val)
        if (!this.head){
            this.head = newNode
            this.tail = this.head
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++
        return this
    }
    // The pop method removes the tail of the list
    pop() {
        if (!this.head) return undefined
        const current = this.head
        const newTail = current
        while (current.next) {
            newTail = current
            current = current.next
        }
        this.tail = newTail
        this.tail.next = null
        this.length--
        if (this.length === 0) {
            this.head = null
            this.tail = null
        }
        return current
    }
    // The shift method removes the head of the list
    shift() {
        if (!this.head) return undefined
        var currentHead = this.head
        this.head = currentHead.next
        this.length--
        if (this.length === 0) {
            this.tail = null
        }
        return currentHead
    }
    // The unshift method takes a value as parameter and assigns it as the head of the list
    unshift(val) {
        const newNode = new Node(val)
        if (!this.head) {
            this.head = newNode
            this.tail = this.head
        }
        newNode.next = this.head
        this.head = newNode
        this.length++
        return this
    }
    // The get method takes an index number as parameter and returns the value of the node at that index
    get(index) {
        if(index < 0 || index >= this.length) return null
        const counter = 0
        const current = this.head
        while(counter !== index) {
            current = current.next
            counter++
        }
        return current
    }
    // The set method takes an index number and a value as parameters, and modifies the node value at the given index in the list
    set(index, val) {
        const foundNode = this.get(index)
        if (foundNode) {
            foundNode.val = val
            return true
        }
        return false
    }
    // The insert method takes an index number and a value as parameters, and inserts the value at the given index in the list
    insert(index, val) {
        if (index < 0 || index > this.length) return false
        if (index === this.length) return !!this.push(val)
        if (index === 0) return !!this.unshift(val)

        const newNode = new Node(val)
        const prev = this.get(index - 1)
        const temp = prev.next
        prev.next = newNode
        newNode.next = temp
        this.length++
        return true
    }
    // The remove method takes an index number as parameter and removes the node at the given index in the list
    remove(index) {
        if(index < 0 || index >= this.length) return undefined
        if(index === 0) return this.shift()
        if(index === this.length - 1) return this.pop()
        const previousNode = this.get(index - 1)
        const removed = previousNode.next
        previousNode.next = removed.next
        this.length--
        return removed
    }
    // The reverse method reverses the list and all pointers so that the head becomes the tail and the tail becomes the head
    reverse(){
      const node = this.head
      this.head = this.tail
      this.tail = node
      let next
      const prev = null
      for(let i = 0; i < this.length; i++) {
        next = node.next
        node.next = prev
        prev = node
        node = next
      }
      return this
    }
}

Los métodos de listas enlazadas simples tienen las siguientes complejidades:

• Inserción – O(1)
• Eliminación – O(n)
• Búsqueda –  O(n)
• Acceso – O(n)

Doubly linked lists (lista doblemente enlazada)

Como ya se mencionó, la diferencia entre las listas con enlace simple y doble es que las listas con enlace doble tienen sus nodos conectados a través de punteros con el valor anterior y el siguiente. Por otro lado, las listas enlazadas simplemente solo conectan sus nodos con el siguiente valor.

Este enfoque de doble puntero permite que las listas doblemente enlazadas funcionen mejor con ciertos métodos en comparación con las listas enlazadas simplemente, pero a costa de consumir más memoria (con las listas doblemente enlazadas necesitamos almacenar dos punteros en lugar de uno).

Una implementación completa de una lista doblemente enlazada podría verse así:

// We create a class for each node within the list
class Node{
    // Each node has three properties, its value, a pointer that indicates the node that follows and a pointer that indicates the previous node
    constructor(val){
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

// We create a class for the list
class DoublyLinkedList {
    // The list has three properties, the head, the tail and the list size
    constructor(){
        this.head = null
        this.tail = null
        this.length = 0
    }
    // The push method takes a value as parameter and assigns it as the tail of the list
    push(val){
        const newNode = new Node(val)
        if(this.length === 0){
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        this.length++
        return this
    }
    // The pop method removes the tail of the list
    pop(){
        if(!this.head) return undefined
        const poppedNode = this.tail
        if(this.length === 1){
            this.head = null
            this.tail = null
        } else {
            this.tail = poppedNode.prev
            this.tail.next = null
            poppedNode.prev = null
        }
        this.length--
        return poppedNode
    }
    // The shift method removes the head of the list
    shift(){
        if(this.length === 0) return undefined
        const oldHead = this.head
        if(this.length === 1){
            this.head = null
            this.tail = null
        } else{
            this.head = oldHead.next
            this.head.prev = null
            oldHead.next = null
        }
        this.length--
        return oldHead
    }
    // The unshift method takes a value as parameter and assigns it as the head of the list
    unshift(val){
        const newNode = new Node(val)
        if(this.length === 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.head.prev = newNode
            newNode.next = this.head
            this.head = newNode
        }
        this.length++
        return this
    }
    // The get method takes an index number as parameter and returns the value of the node at that index
    get(index){
        if(index < 0 || index >= this.length) return null
        let count, current
        if(index <= this.length/2){
            count = 0
            current = this.head
            while(count !== index){
                current = current.next
                count++
            }
        } else {
            count = this.length - 1
            current = this.tail
            while(count !== index){
                current = current.prev
                count--
            }
        }
        return current
    }
    // The set method takes an index number and a value as parameters, and modifies the node value at the given index in the list
    set(index, val){
        var foundNode = this.get(index)
        if(foundNode != null){
            foundNode.val = val
            return true
        }
        return false
    }
    // The insert method takes an index number and a value as parameters, and inserts the value at the given index in the list
    insert(index, val){
        if(index < 0 || index > this.length) return false
        if(index === 0) return !!this.unshift(val)
        if(index === this.length) return !!this.push(val)

        var newNode = new Node(val)
        var beforeNode = this.get(index-1)
        var afterNode = beforeNode.next

        beforeNode.next = newNode, newNode.prev = beforeNode
        newNode.next = afterNode, afterNode.prev = newNode
        this.length++
        return true
    }
}

La gran O de los métodos de listas doblemente enlazadas es la siguiente:

• Inserción – O(1)
• Eliminación – O(1)
• Búsqueda – O(n)
• Acceso – O(n)

 

Trees (árboles)

Los árboles son estructuras de datos que vinculan nodos en una relación padre/hijo, en el sentido de que hay nodos que dependen o se desprenden de otros nodos.

Los árboles están formados por un nodo raíz o root (el primer nodo del árbol), y todos los nodos que salen de esa raíz se denominan hijos. Los nodos en la parte inferior del árbol, que no tienen «descendientes», se denominan nodos hoja. Y la altura del árbol está determinada por la cantidad de conexiones padre/hijo que tiene.

A diferencia de las listas enlazadas o matrices, los árboles no son lineales, en el sentido de que al iterar el árbol, el flujo del programa puede seguir diferentes direcciones dentro de la estructura de datos y, por lo tanto, llegar a diferentes valores mientras que en las linked list o arrays, el programa solo puede iterar la estructura de datos de un extremo al otro, siempre siguiendo la misma ruta.

Un requisito importante para la formación de árboles es que la única conexión válida entre nodos sea de padre a hijo. La conexión entre hermanos o de hijo a padre no está permitida en los árboles (este tipo de conexiones forman grafos, un tipo diferente de estructura de datos). Otro requisito importante es que los árboles deben tener una sola raíz.

Algunos ejemplos del uso de árboles en la programación son:

• El modelo DOM.
• Análisis de situación en inteligencia artificial.
• Carpetas de archivos en los sistemas operativos.

Hay muchos tipos diferentes de árboles. En cada tipo de árbol, los valores pueden organizarse siguiendo diferentes patrones que hacen que esta estructura de datos sea más adecuada para usar frente a diferentes tipos de problemas. Los tipos de árboles más utilizados son los árboles binarios y los heaps.

Binary trees (árboles binarios)

Los árboles binarios son un tipo de árbol en el que cada nodo tiene un máximo de dos hijos.

 

Una situación clave en la que los árboles binarios son realmente útiles es en la búsqueda. Y para buscar, se utiliza un cierto tipo de árbol binario, llamado árboles de búsqueda binarios o binary search trees (BST).

Los BST son como árboles binarios, pero la información dentro de ellos está ordenada de una manera que los convierte en una estructura de datos adecuada para la búsqueda.

En BST, los valores se ordenan de modo que cada nodo que desciende al lado izquierdo de su padre debe tener un valor menor que su padre, y cada nodo que desciende al lado derecho de su padre debe tener un valor mayor que su padre.

 

Este orden en sus valores hace que esta estructura de datos sea excelente para la búsqueda, ya que en cada nivel del árbol podemos identificar si el valor que se busca es mayor o menor que el nodo principal y, a partir de esa comparación, descartar progresivamente aproximadamente la mitad de los datos hasta alcanzamos nuestro valor.

Al insertar o eliminar valores, el algoritmo seguirá los siguientes pasos:

• Comprueba si hay un nodo raíz.
• Si lo hay, verifica si el valor para agregar/eliminar es mayor o menor que el nodo.
• Si es más pequeño, comprueba si hay un nodo a la izquierda y repite la operación anterior. Si no lo hay, agrega/elimina el nodo en esa posición.
• Si es mayor, comprueba si hay un nodo a la derecha y repite la operación anterior. Si no lo hay, agrega/elimina el nodo en esa posición

La búsqueda en BST es muy similar, solo que en lugar de agregar/eliminar valores, verificamos la igualdad de los nodos con el valor que estamos buscando.

La gran complejidad O de estas operaciones es logarítmica (log(n)). Pero es importante reconocer que para lograr esta complejidad, el árbol debe tener una estructura equilibrada para que en cada paso de búsqueda, aproximadamente la mitad de los datos se puedan «descartar». Si se almacenan más valores a un lado u otro de tres, la eficiencia de la estructura de datos se ve afectada.

Una implementación de un BST podría verse así:

// We create a class for each node within the tree
class Node{
    // Each node has three properties, its value, a pointer that indicates the node to its left and a pointer that indicates the node to its right
    constructor(value){
        this.value = value
        this.left = null
        this.right = null
    }
}
// We create a class for the BST
class BinarySearchTree {
    // The tree has only one property which is its root node
    constructor(){
        this.root = null
    }
    // The insert method takes a value as parameter and inserts the value in its corresponding place within the tree
    insert(value){
        const newNode = new Node(value)
        if(this.root === null){
            this.root = newNode
            return this
        }
        let current = this.root
        while(true){
            if(value === current.value) return undefined
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode
                    return this
                }
                current = current.left
            } else {
                if(current.right === null){
                    current.right = newNode
                    return this
                } 
                current = current.right
            }
        }
    }
    // The find method takes a value as parameter and iterates through the tree looking for that value
    // If the value is found, it returns the corresponding node and if it's not, it returns undefined
    find(value){
        if(this.root === null) return false
        let current = this.root,
            found = false
        while(current && !found){
            if(value < current.value){
                current = current.left
            } else if(value > current.value){
                current = current.right
            } else {
                found = true
            }
        }
        if(!found) return undefined
        return current
    }
    // The contains method takes a value as parameter and returns true if the value is found within the tree
    contains(value){
        if(this.root === null) return false
        let current = this.root,
            found = false
        while(current && !found){
            if(value < current.value){
                current = current.left
            } else if(value > current.value){
                current = current.right
            } else {
                return true
            }
        }
        return false
    }
}

 

Heaps

Los heaps son otro tipo de árbol que tiene algunas reglas particulares. Hay dos tipos principales de heaps, MaxHeaps y MinHeaps. En MaxHeaps, los nodos principales siempre son mayores que sus hijos, y en MinHeaps, los nodos principales siempre son más pequeños que sus hijos.

 

En esta estructura de datos no hay garantías entre hermanos, lo que significa que los nodos en el mismo «nivel» no siguen ninguna regla además de ser más altos o más bajos que su padre.

Además, los heaps son lo más compactos posible, lo que significa que cada nivel contiene todos los nodos que puede contener sin espacios vacíos, y los nuevos elementos secundarios se colocan primero en los espacios de la izquierda del árbol.

Los heaps, y en particular los heaps binarios, se utilizan con frecuencia para implementar colas de prioridad, que al mismo tiempo se utilizan con frecuencia en algoritmos conocidos como el algoritmo de búsqueda de rutas de Dijkstra.

Las colas de prioridad son un tipo de estructura de datos en la que cada elemento tiene una prioridad asociada y los elementos con mayor prioridad se presentan primero.

 

Graphs (grafos)

Los grafos son una estructura de datos formada por un grupo de nodos y ciertas conexiones entre esos nodos. A diferencia de los árboles, los grafos no tienen nodos raíz ni nodos hojas, ni una «cabeza» o una «cola». Los diferentes nodos están conectados entre sí y no existe una conexión padre-hijo implícita entre ellos.

 

Los grafos son estructuras de datos a menudo útiles para:

• Redes sociales
• Geolocalización
• Sistemas de recomendación

Los grafos se pueden clasificar en diferentes tipos según las características de las conexiones entre nodos:

Gráficos dirigidos y no dirigidos

Decimos que un grafo no está dirigido si no hay una dirección implícita en las conexiones entre los nodos.

Si tomamos la siguiente imagen de ejemplo, puede ver que no hay dirección en la conexión entre el nodo 2 y el nodo 3. La conexión va en ambos sentidos, lo que significa que puede atravesar la estructura de datos del nodo 2 al nodo 3, y del nodo 3 al nodo 2. No dirigido significa que las conexiones entre los nodos se pueden utilizar en ambos sentidos.

Y como habrás adivinado, los grafos dirigidos son exactamente lo contrario. Reutilicemos la imagen de ejemplo anterior y veamos que aquí hay una dirección implícita en las conexiones entre nodos.

En este grafo en particular, podría atravesar del nodo A al nodo B, pero no puede ir del nodo B al A.

 

Grafos ponderados y no ponderados

Decimos que un grafo está ponderado si las conexiones entre los nodos tienen un peso asignado. En este caso, el peso solo significa un valor que se asigna a una conexión específica. Es información sobre la conexión en sí, no sobre los nodos.

Siguiendo este ejemplo, podemos ver que la conexión entre los nodos 0 y 4 tiene un peso de 7. Y la conexión entre los nodos 3 y 1 tiene un peso de 4.

Para comprender el uso de grafos ponderados, imagina que deseas representar un mapa con muchas ubicaciones diferentes y que brinda al usuario información sobre cuánto tiempo puede demorar en ir de un lugar a otro.

Un grafo ponderado sería perfecto para esto, ya que podría usar cada nodo para guardar información sobre la ubicación, las conexiones podrían representar las carreteras disponibles entre cada lugar y los pesos representarían la distancia física de un lugar a otro.

Y como habrás adivinado una vez más, los grafo no ponderados son aquellos en los que las conexiones entre nodos no tienen pesos asignados. Entonces, no hay información particular sobre las conexiones entre los nodos, solo sobre los nodos mismos.

Cómo representar gráficos

Al codificar grafos, hay dos métodos principales que podemos usar: una matriz de adyacencia y una lista de adyacencia. Expliquemos cómo funcionan ambos y veamos sus pros y sus contras.

Una matriz de adyacencia es una estructura bidimensional que representa los nodos en nuestro gráfico y las conexiones entre ellos.

Si usamos este ejemplo, puedes crear una matriz como una tabla, donde las columnas y las filas representan los nodos en nuestro gráfico, y el valor de las celdas representa las conexiones entre los nodos. Si la celda es 1, hay una conexión entre la fila y la columna, y si es 0, no la hay.

[
    [0, 1, 1, 0]
    [1, 0, 0, 1]
    [1, 0, 0, 1]
    [0, 1, 1, 0]
]

 

Por otro lado, una lista de adyacencia puede pensarse como una estructura de pares clave-valor donde las claves representan cada nodo en nuestro gráfico y los valores son las conexiones que tiene ese nodo en particular.

Usando el mismo gráfico de ejemplo, nuestra lista de adyacencia podría representarse con este objeto:

{
    A: ["B", "C"],
    B: ["A", "D"],
    C: ["A", "D"],
    D: ["B", "C"],
}

 

Puede ver que para cada nodo tenemos una clave y almacenamos todas las conexiones del nodo dentro de una matriz.

Entonces, ¿cuál es la diferencia entre las listas y matrices de adyacencia? Bueno, las listas tienden a ser más eficientes cuando se trata de agregar o eliminar nodos, mientras que las matrices son más eficientes cuando consultan conexiones específicas entre nodos.

Para ver esto, imagina que queremos agregar un nuevo nodo a nuestro gráfico:

Para representar esto en una matriz, necesitaríamos agregar una columna completamente nueva y una fila completamente nueva, mientras que para hacer lo mismo en una lista, es suficiente agregar un valor a las conexiones B y un par clave-valor para representar E:

{
    A: ["B", "C"],
    B: ["A", "D", "E"],
    C: ["A", "D"],
    D: ["B", "C"],
    E: ["B"],
}

 

Ahora imagine que queremos verificar si existe una conexión entre el nodo B y E. Verificar eso en una matriz es muy fácil, ya que sabemos exactamente la posición en la matriz que representa esa conexión.
Pero en una lista, no tenemos esa información que necesitaríamos para iterar por toda la matriz que representa las conexiones B y ver qué hay allí. Entonces puede ver que hay pros y contras para cada enfoque.

Una implementación completa de un gráfico usando una lista de adyacencia podría verse así. Para simplificar las cosas, representaremos un gráfico no ponderado no dirigido.

// We create a class for the graph
class Graph{
    // The graph has only one property which is the adjacency list
    constructor() {
        this.adjacencyList = {}
    }
    // The addNode method takes a node value as parameter and adds it as a key to the adjacencyList if it wasn't previously present
    addNode(node) {
        if (!this.adjacencyList[node]) this.adjacencyList[node] = []
    }
    // The addConnection takes two nodes as parameters, and it adds each node to the other's array of connections.
    addConnection(node1,node2) {
        this.adjacencyList[node1].push(node2)
        this.adjacencyList[node2].push(node1)
    }
    // The removeConnection takes two nodes as parameters, and it removes each node from the other's array of connections.
    removeConnection(node1,node2) {
        this.adjacencyList[node1] = this.adjacencyList[node1].filter(v => v !== node2)
        this.adjacencyList[node2] = this.adjacencyList[node2].filter(v => v !== node1)
    }
    // The removeNode method takes a node value as parameter. It removes all connections to that node present in the graph and then deletes the node key from the adj list.
    removeNode(node){
        while(this.adjacencyList[node].length) {
            const adjacentNode = this.adjacencyList[node].pop()
            this.removeConnection(node, adjacentNode)
        }
        delete this.adjacencyList[node]
    }
}

const spain = new Graph()
spain.addNode("Cordoba")
spain.addNode("Sevilla")
spain.addNode("Toledo")
spain.addNode("Madrid")
spain.addConnection("Sevilla", "Cordoba")
spain.addConnection("Cordoba", "Toledo")
spain.addConnection("Toledo", "Madrid")

console.log(spain)
// Graph {
//   adjacencyList: {
//     Cordoba: [ 'Sevilla', 'Toledo' ],
//     Sevilla: [ 'Cordoba' ],
//     Toledo: [ 'Cordoba', 'Madrid' ],
//     Madrid: [ 'Toledo' ]
//   }
// }

 

---

 

Conclusión

Eso es todo, todos. En este artículo, presentamos las principales estructuras de datos utilizadas en informática y desarrollo de software. Estas estructuras son la base de la mayoría de los programas que usamos en la vida cotidiana, por lo que es un buen conocimiento para adquirir.

Aunque este tema puede parecer un poco abstracto y complicado al principio, creo que podemos entenderlo mejor simplemente pensando en las estructuras de datos como formas en las que organizamos los datos para lograr mejor ciertas tareas.

 

---

 

Espero que el artículo «Estructuras de datos en JavaScript» te haya sido de ayuda ❤️