Como construir estruturas de dados com classes JavaScript ES6
As estruturas de dados são um aspecto fundamental da ciência da computação e da programação, independentemente da linguagem que você usa. Ter um conhecimento completo deles pode ajudá-lo a organizar, gerenciar, armazenar e modificar dados de forma eficiente. Identificar a estrutura de dados adequada para seu caso de uso pode melhorar o desempenho por uma margem enorme.
No entanto, o JavaScript só vem com estruturas de dados primitivas, como matrizes e objetos, por padrão. Mas, com a introdução das classes ECMAScript 6 (ES6), agora você pode criar estruturas de dados customizadas, como pilhas e filas, com a ajuda de estruturas de dados primitivas.
Estrutura de dados da pilha
A estrutura de dados da pilha permite que você coloque novos dados sobre os dados existentes de maneira LIFO (último a entrar, primeiro a sair). Essa estrutura de dados linear é fácil de visualizar usando um exemplo simples. Considere uma pilha de pratos mantidos sobre uma mesa. Você pode adicionar ou remover um prato apenas do topo da pilha.
Veja como você pode implementar a estrutura de dados da pilha usando matrizes JavaScript e classes ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Vamos explorar e construir algumas das operações que você pode realizar em uma pilha.
Operação Push
A operação push é usada para inserir novos dados na pilha. Você precisa passar os dados como um parâmetro ao chamar o método push. Antes de inserir os dados, o ponteiro superior da pilha é incrementado em um e os novos dados são inseridos na posição superior.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Operação Pop
A operação pop é usada para remover o elemento de dados superior da pilha. Ao realizar esta operação, o ponteiro superior é reduzido em 1.
pop() {
if (this.top < 0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Operação Peek
A operação peek é usada para retornar o valor presente no topo da pilha. A complexidade de tempo para recuperar esses dados é O (1).
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Estrutura de dados de lista vinculada
Uma lista vinculada é uma estrutura de dados linear que consiste em vários nós conectados uns aos outros com a ajuda de ponteiros. Cada nó da lista contém os dados e uma variável de ponteiro que aponta para o próximo nó da lista.
Ao contrário de uma pilha, as implementações de lista vinculada em JavaScript requerem duas classes. A primeira classe é a classe Node para criar um nó, e a segunda classe é a classe LinkedList para realizar todas as operações na lista vinculada. O ponteiro principal aponta para o primeiro nó da lista vinculada e o ponteiro final aponta para o último nó da 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;
}
}Aqui estão algumas operações principais que você pode executar em uma lista vinculada:
Anexar operação
A operação de acréscimo é usada para adicionar um novo nó ao final da lista vinculada. Você tem que passar os dados como parâmetro para inserir um novo nó. Em primeiro lugar, crie um novo objeto de nó usando a nova palavra-chave em JavaScript.
Se a lista vinculada estiver vazia, os ponteiros da ponta e da cauda apontarão para o novo nó. Caso contrário, apenas o ponteiro da cauda apontará para o novo nó.
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;
}Operação de Inserção
Para inserir um novo nó em um índice específico, você pode usar a operação de inserção. Este método leva dois parâmetros: os dados a serem inseridos e o índice no qual eles devem ser inseridos. No pior caso, esse método tem uma complexidade de tempo de O (N), pois pode ter que percorrer toda a 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;
}Excluir operação
A operação de exclusão percorre a lista vinculada para obter a referência ao nó que deve ser excluído e remove o link do nó anterior. Semelhante à operação de inserção, a operação de exclusão também tem uma complexidade de tempo de O (N) no pior caso.
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;
}Estrutura de dados da fila
A estrutura de dados da fila é semelhante a um grupo de pessoas em uma fila. A pessoa que entra na fila primeiro é atendida antes das outras. Da mesma forma, essa estrutura de dados linear segue a abordagem FIFO (primeiro a entrar, primeiro a sair) para inserir e remover dados. Essa estrutura de dados pode ser recriada em JavaScript usando uma lista vinculada desta maneira:
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Veja como você pode inserir e remover dados de uma fila em JavaScript:
Operação de enfileiramento
A operação de enfileiramento insere novos dados na fila. Ao chamar esse método, se a estrutura de dados da fila estiver vazia, os ponteiros frontal e traseiro apontam para o nó recém-inserido na fila. Se a fila não estiver vazia, o novo nó é adicionado ao final da lista e o ponteiro traseiro aponta para este nó.
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;
}Operação de desenfileiramento
A operação de desenfileiramento remove o primeiro elemento da fila. Durante a operação de desenfileiramento, o ponteiro principal é movido para o segundo nó na lista. Este segundo nó agora se torna o chefe da fila.
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;
}A próxima etapa após as estruturas de dados
Estruturas de dados podem ser um conceito complicado de entender, especialmente se você for novo em programação. Mas, assim como qualquer outra habilidade, a prática pode ajudá-lo a realmente entender e apreciar a eficiência que ela oferece para armazenar e gerenciar dados em seus aplicativos.
Algoritmos são tão úteis quanto estruturas de dados e podem se tornar a próxima etapa lógica em sua jornada de programação. Então, por que não começar com um algoritmo de classificação, como classificação por bolha?
