Cómo construir estructuras de datos con clases de JavaScript ES6
Las estructuras de datos son un aspecto fundamental de la informática y la programación, independientemente del lenguaje que utilice. Tener un conocimiento profundo de ellos puede ayudarlo a organizar, administrar, almacenar y modificar datos de manera eficiente. Identificar la estructura de datos adecuada para su caso de uso puede mejorar el rendimiento por un gran margen.
Sin embargo, JavaScript solo viene con estructuras de datos primitivas como matrices y objetos de forma predeterminada. Pero con la introducción de las clases ECMAScript 6 (ES6), ahora puede crear estructuras de datos personalizadas, como pilas y colas, con la ayuda de estructuras de datos primitivas.
Estructura de datos de pila
La estructura de datos de la pila le permite enviar nuevos datos sobre los datos existentes de una manera LIFO (último en entrar, primero en salir). Esta estructura de datos lineal es fácil de visualizar con un ejemplo simple. Considere una pila de platos colocados sobre una mesa. Puede agregar o quitar un plato de la parte superior de la pila únicamente.
A continuación, le mostramos cómo puede implementar la estructura de datos de la pila mediante matrices de JavaScript y clases de ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Exploremos y construyamos algunas de las operaciones que puede realizar en una pila.
Operación de empuje
La operación de inserción se utiliza para insertar nuevos datos en la pila. Debe pasar los datos como un parámetro mientras llama al método push. Antes de insertar los datos, el puntero superior de la pila se incrementa en uno y los nuevos datos se insertan en la posición superior.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Operación Pop
La operación pop se utiliza para eliminar el elemento de datos superior de la pila. Al realizar esta operación, el puntero superior se reduce en 1.
pop() {
if (this.top < 0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Operación de inspección
La operación de inspección se utiliza para devolver el valor presente en la parte superior de la pila. La complejidad de tiempo para recuperar estos datos es O (1).
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Estructura de datos de lista vinculada
Una lista vinculada es una estructura de datos lineal que consta de numerosos nodos conectados entre sí con la ayuda de punteros. Cada nodo de la lista contiene los datos y una variable de puntero que apunta al siguiente nodo de la lista.
A diferencia de una pila, las implementaciones de listas vinculadas en JavaScript requieren dos clases. La primera clase es la clase Node para crear un nodo y la segunda clase es la clase LinkedList para realizar todas las operaciones en la lista vinculada. El puntero de cabeza apunta al primer nodo de la lista vinculada y el puntero de cola apunta al último nodo de la lista vinculada.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}A continuación, se muestran algunas operaciones principales que puede realizar en una lista vinculada:
Agregar operación
La operación de agregar se usa para agregar un nuevo nodo al final de la lista vinculada. Tienes que pasar los datos como parámetro para insertar un nuevo nodo. En primer lugar, cree un nuevo objeto de nodo utilizando la nueva palabra clave en JavaScript.
Si la lista vinculada está vacía, tanto el puntero de cabeza como el de cola apuntarán al nuevo nodo. De lo contrario, solo el puntero de cola apuntará al nuevo nodo.
append(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.size++;
return this;
}Insertar operación
Para insertar un nuevo nodo en un índice particular, puede hacer uso de la operación de inserción. Este método toma dos parámetros: los datos que se van a insertar y el índice en el que se van a insertar. En el peor de los casos, este método tiene una complejidad temporal de O (N), ya que puede tener que recorrer toda la lista.
insert(data, index) {
if (index < 0 || index > this.size) return undefined;
if (index === 0) {
this.head = new Node(data, this.head);
!this.tail ? (this.tail = this.head) : null;
this.size++;
return this;
}
if (index === this.size) return this.append(data);
let count = 0;
let beforeNode = this.head;
while (count !== index) {
beforeNode = beforeNode.next;
count++;
}
const newNode = new Node(data);
let afterNode = beforeNode.next;
newNode.next = afterNode;
beforeNode.next = newNode;
this.size++;
return this;
}Eliminar operación
La operación de eliminación atraviesa la lista vinculada para obtener la referencia al nodo que se eliminará y elimina el enlace del nodo anterior. Similar a la operación de inserción, la operación de eliminación también tiene una complejidad de tiempo de O (N) en el peor de los casos.
deleteNode(index) {
if (index === 0) {
const removedHead = this.head;
this.head = this.head.next;
this.size--;
this.size === 0 ? (this.tail = null) : null;
return removedHead;
}
if (index === this.size - 1) {
if (!this.head) return undefined;
let currentNode = this.head;
let newTail = currentNode;
while (currentNode.next) {
newTail = currentNode;
currentNode = currentNode.next;
}
this.tail = newTail;
this.tail.next = null;
this.size--;
this.size === 0 ? ([this.head, this.tail] = [null, null]) : null;
return currentNode;
}
if (index < 0 || index > this.size - 1) return undefined;
let count = 0;
let beforeNode = this.head;
while (count !== index - 1) {
beforeNode = beforeNode.next;
count++;
}
const removedNode = beforeNode.next;
let afterNode = removedNode.next;
beforeNode.next = afterNode;
removedNode.next = null;
this.size--;
return removedNode;
}Estructura de datos de la cola
La estructura de datos de la cola es similar a la de un grupo de personas en una cola. La persona que ingresa primero a la cola es atendida antes que los demás. De manera similar, esta estructura de datos lineal sigue el enfoque FIFO (primero en entrar, primero en salir) para insertar y eliminar datos. Esta estructura de datos se puede recrear en JavaScript utilizando una lista vinculada de esta manera:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}A continuación, le mostramos cómo puede insertar y eliminar datos de una cola en JavaScript:
Operación de puesta en cola
La operación de puesta en cola inserta nuevos datos en la cola. Al llamar a este método, si la estructura de datos de la cola está vacía, los punteros delantero y trasero apuntan al nodo recién insertado en la cola. Si la cola no está vacía, el nuevo nodo se agrega al final de la lista y el puntero posterior apunta a este nodo.
enqueue(data) {
const newNode = new Node(data);
if (!this.front) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode;
this.rear = newNode;
}
this.size++;
return this;
}Operación de sacar de cola
La operación de quitar de la cola elimina el primer elemento de la cola. Durante la operación de quitar la cola, el puntero principal se mueve hacia el segundo nodo de la lista. Este segundo nodo ahora se convierte en el encabezado de la cola.
dequeue() {
if (!this.front) return undefined;
if (this.front === this.rear) this.rear = null;
const dequeuedNode = this.front;
this.front = this.front.next;
this.size--;
return dequeuedNode;
}El siguiente paso después de las estructuras de datos
Las estructuras de datos pueden ser un concepto complicado de comprender, especialmente si es nuevo en programación. Pero al igual que cualquier otra habilidad, la práctica puede ayudarlo a comprender y apreciar realmente la eficiencia que proporciona para almacenar y administrar datos en sus aplicaciones.
Los algoritmos son tan útiles como las estructuras de datos y podrían convertirse en el siguiente paso lógico en su viaje de programación. Entonces, ¿por qué no comenzar con un algoritmo de clasificación como la clasificación de burbujas?