Una estructura de datos es una forma que tenemos de guardar elementos en el ordenador, de tal forma que podemos acceder, crear y eliminar datos de una forma eficiente dependiendo de cada caso. Por ejemplo una lista es una estructura de datos, y una cola también.
Normalmente cuando se explican las estructura de datos, se usa un lenguaje con punteros como C o Java para sus implementaciones, ya que es la manera más eficiente que existe.
Para este caso, voy a explicar las estructuras en Javascript, que, aunque no tiene punteros, nos sirve para saber cómo se crean sus implementaciones.
Vamos con las implementaciones de algunas estructuras básicas.
Listas enlazadas
Una lista enlazada, es una tipo de lista de elementos en los que cada elemento tiene almacenado la dirección del siguiente elemento de la lista, de tal forma que si queremos acceder a un elemento en particular tenemos que empezar por el primer elemento para recorrer uno a uno hasta llegar al item deseado.
Características
- Insertar nodos por el inicio de la lista es inmediato
- Buscar un elemento en la lista tiene complejidad 0(n)
- Puede servir de base para implementar pilas y colas
- Borrar el primer elemento de la lista también es inmediato
- Si la lista no guarda el úlitmo elemento, insertar elementos por el final de la lista tiene complejidad O(n)
Empecemos por algo sencillo, una lista enlazada con una variable que nos diga qué nodo es el primer nodo de la lista. Con esto es suficiente para la lista porque teniendo el primer nodo si quieres recorrer la lista tan solo tienes que ir pasando de elemento en elemento accediendo a su valor next.
class LinkedListItem {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
prepend(value) {
const newItem = new LinkedListItem(value, this.head);
this.head = newItem;
}
}Lo primero que hago es crear la clase LinkedListItem que será cada uno de los elementos de la lista que estamos creando. Dentro de esta clase, en el constructor, se define el propio valor que guardará cada elemento de la lista y un valor llamado next para acceder al siguiente valor.
Luego creo la clase LinkedList propiamente dicha, que simplemente guardará el primer item de la lista. También creo la función prepend ya que en este tipo de listas lo mejor es insertar nodos por la cabecera de la lista ya que es lo más óptimo.
La función prepend lo que hace es recibir el valor a guardar y con ese valor se crea un elemento de la clase LinkedListItem que hemos creado antes pasando el value y el elemento head que esté guardado en ese momento. Como insertamos por el principio de la lista, la idea es que el nuevo elemento que se crea tenga como valor next el primer nodo de la lista. Por último se hace que ahora el valor head pase a valer el nodo que hemos creado, así actualizamos el primer nodo de la lista.
Pasemos ahora a la función find que buscará y devolverá el item de la lista con un valor dado.
find(value) {
if (!this.head) {
return null;
}
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next;
}
}Esta función lo primero que hace es comprobar si la lista es vacía, es decir, si no existe el primer elemento de la lista, el elemento head, en ese caso se devuelve null.
Luego se hace un loop while para recorrer la lista, para ello se selecciona el primer elemento de la lista, se mira si su valor es el que estamos buscando para devolverlo en ese caso y si no es el que buscamos pasamos al siguiente elemento cambiando currentNode por el elemento next que esté apuntando.
Para estos ejemplos estamos buscando los elementos dentro de la lista por su valor, lo suyo sería tener un parámetro id para hacer las búsquedas y que el parámetro value sea un objeto con el valor que quieres guardar.
También podemos crear una función deleteHead para borrar elementos por la cabecera, ya que es lo más óptimo en este tipo de listas.
deleteHead() {
if (this.head) {
if (this.head.next) {
const secondNode = this.head.next;
this.head = secondNode;
} else {
this.head = null;
}
}
}Lo primero es comprobar si la lista no tiene cabecera y por tanto está vacía, en ese caso no hacemos nada. Si la lista tiene items lo primero es ver si la cabecera tiene un parámetro next con valor, es decir, para ver si la lista tiene más de dos items. Si es ese caso entonces accedemos a ese segundo item para que sea la nueva cabecera. Si la lista solo tiene un item en ese caso hacemos que la cabecera valga null para que sea una lista vacía.
El código completo quedaría así:
class LinkedListItem {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
prepend(value) {
const newItem = new LinkedListItem(value, this.head);
this.head = newItem;
}
find(value) {
if (!this.head) {
return null;
}
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
return currentNode;
}
currentNode = currentNode.next;
}
}
deleteHead() {
if (this.head) {
if (this.head.next) {
const secondNode = this.head.next;
this.head = secondNode;
} else {
this.head = null;
}
}
}
print() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}
}También me he metido un método llamado print para poder imprimir por consola todos los elementos de la lista.
Y para usar la lista sería así:
list = new LinkedList();
list.prepend("a");
list.prepend("b");
list.prepend("c");
console.log(list.find("b"));
list.print();Colas
Las colas son estructuras de datos de tipo FIFO (First In First Out) es decir, el primer valor que se inserta en la lista es el primer valor que se va a sacar.
Las colas son un tipo de lista con la particularidad de que solo se pueden insertar elementos por la cabecera de la lista y solo se pueden sacar por el final de la lista, en otras palabras, se saca siempre el elemento que lleve más tiempo dentro de la lista.
El ejemplo típico de este tipo de estructuras es la cola de impresión. Imagina que quieres imprimir varios documentos, lo que ocurre es que se van encolando los elementos y se van desencolando e imprimiendo los primeros que llegaron.
Características
- Se encolan items por el final de la lista
- Se desencolan items por el comienzo de la lista
- Tanto encolar como desencolar son operaciones inmediatas
Vamos con la implementación en Javascript:
class QueueItem {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
}
}La implementación de este tipo de estructuras es parecida a la lista que hemos visto antes. Lo único es que aquí vamos a tener un parámetro tail para saber el último elemento de la cola.
Vamos con los métodos importantes, empecemos por encolar:
enqueue(value) {
const newItem = new QueueItem(value, null);
if (this.tail) {
this.tail.next = newItem;
}
this.tail = newItem
if (!this.head) {
this.head = this.tail
}
}Aquí lo primero que hay que saber es que se insertan elementos por el final de la lista, por eso tenemos que mantener la variable tail, así conseguimos tener la lista de elementos siempre ordenada, los primeros elementos son los que más tiempo llevan en la cola.
Lo primero que se hace es crear el elemento de la cola y mirar si existe el último elemento de la cola, si existe, es decir, ya hay elementos en la cola, lo que hacemos es que coger el último elemento de la cola y hacer que apunte al elemento que vamos a insertar ahora ya que va a ser el último. Luego se hace que el propio valor de tail sea el propio elemento que estamos insertando, así pasará a ser el último.
Por último, se mira si la cola no tiene head, y por tanto es una cola vacía, en ese caso hacemos que el head sea también el último elemento, ya que si solo hay un elemento, la cabecera de la lista y el final de la lista será el mismo elemento.
Vamos con el método desencolar:
dequeue() {
if (!this.head) {
return null;
}
const firstNode = this.head;
if (this.head.next) {
this.head = this.head.next;
} else {
this.head = null;
this.tail = null;
}
return firstNode;
}Como la lista está ordenada y los primeros elementos son los que más tiempo llevan, desencolar se hace sobre el primer elemento de la lista, es decir, se borra y se devuelve el primer elemento de la lista.
Si la cola está vacía no se desencola nada y por tanto devolvemos null. En caso de que la cola tenga elementos cogemos el primer elemento y miramos si tiene siguiente, es decir, si hay más de un elemento en la cola, en ese caso actualizamos el valor de la cabecera para que valga lo que el segundo elemento y por tanto el primero desaparezca.
Si solo hay un elemento en la cola, lo que se hace al sacar el último elemento de la cola es hacer que la cabecera y el final de la cola valgan null, volvemos al estado inicial. Por último se devuelve el propio elemento desencolado.
El código completo quedaría tal que así:
class QueueItem {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
class Queue {
constructor() {
this.head = null;
this.tail = null;
}
enqueue(value) {
const newItem = new QueueItem(value, null);
if (this.tail) {
this.tail.next = newItem;
}
this.tail = newItem;
if (!this.head) {
this.head = this.tail;
}
}
dequeue() {
if (!this.head) {
return null;
}
const firstNode = this.head;
if (this.head.next) {
this.head = this.head.next;
} else {
this.head = null;
this.tail = null;
}
return firstNode;
}
print() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}
}Como este tipo de estructuras no dejan de ser listas enlazadas, el método print es exactamente el mismo que vimos anteriormente.
Si queremos usar la cola sería tal que así:
const queue = new Queue();
queue.enqueue("1");
queue.enqueue("2");
queue.enqueue("3");
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 3
console.log(queue.dequeue()); // null
queue.print();Pilas
Las pilas también son una particularidad de las listas enlazadas. A diferencia de las colas, las pilas son lo contrario, son de tipo FILO (First In Last Out).
Piensa en una mesa y que vas dejando folios uno encima del otro, lo que estás haciendo es apilarlos. Si quieres coger un folio de los de la pila de folios lo que haces es coger el primero de arriba, es decir, el folio que lleva menos tiempo sobre la mesa.
Características
- Se apilan items por el comienzo de la lista
- Se desapilan items por el comienzo de la lista también
- Tanto apilan como desapilar son operaciones inmediatas
Vamos con su implementación.
class StackItem {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
class Stack {
constructor() {
this.head = null;
}
push(value) {
const newValue = new StackItem(value, this.head);
this.head = newValue;
}
pop() {
if (this.head) {
if (this.head.next) {
const secondNode = this.head.next;
this.head = secondNode;
} else {
this.head = null;
}
}
}
print() {
let currentNode = this.head;
while (currentNode) {
console.log(currentNode.value);
currentNode = currentNode.next;
}
}
}Si te has fijado bien la implementación es idéntica a las listas enlazadas que hemos visto antes y eso es porque insertar por la cabecera y eliminar por la cabecera es lo más óptimo al no necesitar recorrer la lista.
Árboles binarios de búsqueda
Los árboles son estructuras de datos en los que los nodos tienen jerarquía. Cada nodo puede tener uno o más árboles hijos y así recursivamente hasta llegar a los nodos hojas, que no tienen hijos.
El ejemplo típico es un árbol genealógico o árbol familiar en los que se ve claramente que los nodos padres pueden tener nodos hijos y éstos a su vez más nodos hijos.
Dentro de los árboles, en la informática es muy típico un tipo de árbol que se usa para tener una lista ordenada de números. Estos árboles se llaman árboles binarios de búsqueda porque cada nodo como mucho puede tener dos nodos hijos. Para cada nodo, el hijo de la izquerda siempre tiene un valor menor que el nodo padre mientras que el nodo de la derecha siempre es mayor que el valor del padre.
Esto es así porque si quieres localizar un elemento del árbol no necesitas recorrerlo entero, porque al estar ordenado vas a poder descartar nodos cuando lo recorrers mirando si el elemento es mayor o menos que los nodos hijos.
Características
- Insertar, borrar y localizar nodos tiene complejidad O(log(n)) de media
- En el peor de los casos, insertar, borrar y localizar nodos tiene complejidad O(n)
Empecemos con la implementación. Para empezar cada nodo del árbol va a tener 3 parámetros: el propio valor (el número a guardar), el hijo de la izquierda y el hijo de la derecha:
class ThreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}El árbol en sí solo va a almacenar el nodo raíz, es decir, el nodo del que cuelgan todos los demás nodos.
class BinarySeachTree {
constructor() {
this.root = null;
}
}Empecemos con lo interesante, la inserción de nodos:
insert(value) {
const newNode = new ThreeNode(value, null, null);
if (!this.root) {
this.root = newNode;
} else {
let current = this.root;
let isFound = false;
while (!isFound) {
if (current.value === value) {
isFound = true
return undefined
}
if (current.value > value) {
if (!current.left) {
current.left = newNode
isFound = true
return this
} else {
current = current.left
}
} else {
if (!current.right) {
current.right = newNode
isFound = true
return this
} else {
current = current.right
}
}
}
}
}Primero lo que se hace es crear el nuevo nodo y comprobar si el nodo raíz del árbol, el nodo root está vacío. En ese caso, como no hay elementos se crea el nodo raíz con el nuevo nodo que hemos creado.
Luego lo que hay que hacer es ir recorriendo el árbol. Creamos currentNode para saber el nodo actual y empezamos por el nodo raíz. Comprobamos ambos hijos y miramos si el valor que vamos a insertar es mayor o menos que el hijo izquierdo y el derecho.
Si el nuevo valor es menor lo que se hace es mirar si el nodo en el que estamos tiene hizo izquierdo, si no lo tiene lo insertamos ahí, para ello hacemos que el nodo actual tenga como hijo izquierdo el nuevo nodo y hacemos que isFound sea true para salir del bucle. Si ya tiene nodo izquierdo el nodo actual hacemos que el nodo actual sea el hijo izquierdo para seguir recorriendo el árbol.
Lo mismo sucede para el hijo derecho, solo que mirando si el valor que vamos a insertar es mayor que el nodo que estamos recorriendo.
class ThreeNode {
constructor(value, left, right) {
this.value = value;
this.left = left;
this.right = right;
}
}
class BinarySeachTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new ThreeNode(value, null, null);
if (!this.root) {
this.root = newNode;
} else {
let currentNode = this.root;
let isFound = false;
while (!isFound) {
if (value === currentNode.value) {
isFound = true;
return;
}
if (value !== currentNode.value) {
if (value < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode;
isFound = true;
return;
} else {
currentNode = currentNode.left;
}
}
if (value > currentNode.value) {
if (!currentNode.right) {
currentNode.right = newNode;
isFound = true;
return;
} else {
currentNode = currentNode.right;
}
}
}
}
}
}
}
three = new BinarySeachTree();
three.insert(10);
three.insert(5);
three.insert(15);
three.insert(7);
three.insert(3);El eliminado de los nodos en los árboles binarios de búsqueda es la parte más difícil de implementar ya que eliminar nodos requiere copiar todos sus hijos al árbol para no perder esos nodos. Esto hace que haya que considerar varios casos: nodos sin hijos, con un solo hijo, con más de un hijo y más árboles por debajo, etc.
Para no alargar demasiado este artículo, la implementación la vamos a dejar pendiente. Si el artículo gusta a la gente, quizás haga segunda parte de este artículo implementando el borrado.
Conclusiones
En Javascript como mucho yo implementaría el árbol binario de búsqueda, ya que por defecto viene con listas que podemos usar para crear colas y pilas también:
const stack = [];
stack.push(2); // stack is now [2]
stack.push(5); // stack is now [2, 5]
const i = stack.pop(); // stack is now [2]
alert(i); // displays 5
const queue = [];
queue.push(2); // queue is now [2]
queue.push(5); // queue is now [2, 5]
const i = queue.shift(); // queue is now [5]
alert(i); // displays 2Como digo estas implementaciones son para que aprendas cómo se crearían este tipo de estructuras en este lenguaje, no creo que le saques mucha utilidad más hayá de aprender.
Yo personalmente nunca he necesitado este tipo de estructuras y menos en Javascript. Alguna vez si que he necesitado una pila o una cola, pero simplemente he usado lo que ofrece en lenguaje por defecto.