Comment créer des structures de données avec des classes JavaScript ES6
Les structures de données sont un aspect fondamental de l'informatique et de la programmation, quel que soit le langage que vous utilisez. En avoir une connaissance approfondie peut vous aider à organiser, gérer, stocker et modifier efficacement les données. L'identification de la structure de données appropriée pour votre cas d'utilisation peut améliorer considérablement les performances.
Cependant, JavaScript n'est fourni par défaut qu'avec des structures de données primitives telles que des tableaux et des objets. Mais avec l'introduction des classes ECMAScript 6 (ES6), vous pouvez désormais créer des structures de données personnalisées telles que des piles et des files d'attente à l'aide de structures de données primitives.
Structure de données de pile
La structure de données de la pile vous permet de pousser de nouvelles données au-dessus des données existantes d'une manière LIFO (dernier entré, premier sorti). Cette structure de données linéaire est facile à visualiser à l'aide d'un exemple simple. Considérons une pile d'assiettes conservées sur une table. Vous pouvez ajouter ou retirer une plaque du haut de la pile uniquement.
Voici comment implémenter la structure de données de la pile à l'aide de tableaux JavaScript et de classes ES6 :
class Stack {
constructor() {
this.data = [];
this.top = -1;
}
}Explorons et construisons certaines des opérations que vous pouvez effectuer sur une pile.
Opération de poussée
L'opération push est utilisée pour insérer de nouvelles données dans la pile. Vous devez passer les données en paramètre lors de l'appel de la méthode push. Avant d'insérer les données, le pointeur supérieur de la pile est incrémenté de un et les nouvelles données sont insérées à la position supérieure.
push(data) {
this.top++;
this.data[this.top] = data;
return this.data;
}Opération Pop
L'opération pop est utilisée pour supprimer l'élément de données le plus élevé de la pile. Lors de l'exécution de cette opération, le pointeur du haut est réduit de 1.
pop() {
if (this.top < 0) return undefined;
const poppedTop = this.data[this.top];
this.top--;
return poppedTop;
}Opération Aperçu
L'opération peek est utilisée pour retourner la valeur présente en haut de la pile. La complexité temporelle pour récupérer ces données est O(1).
peek() {
return this.top >= 0 ? this.data[this.top] : undefined;
}Structure de données de liste chaînée
Une liste chaînée est une structure de données linéaire composée de nombreux nœuds connectés les uns aux autres à l'aide de pointeurs. Chaque nœud de la liste contient les données et une variable de pointeur qui pointe vers le nœud suivant de la liste.
Contrairement à une pile, les implémentations de listes chaînées en JavaScript nécessitent deux classes. La première classe est la classe Node pour créer un nœud et la deuxième classe est la classe LinkedList pour effectuer toutes les opérations sur la liste chaînée. Le pointeur de tête pointe vers le premier nœud de la liste chaînée et le pointeur de queue pointe vers le dernier nœud de la liste chaînée.
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
}Voici quelques opérations principales que vous pouvez effectuer sur une liste chaînée :
Opération d'ajout
L'opération d'ajout est utilisée pour ajouter un nouveau nœud à la fin de la liste chaînée. Vous devez passer les données en paramètre pour insérer un nouveau nœud. Tout d'abord, créez un nouvel objet nœud en utilisant le nouveau mot-clé en JavaScript.
Si la liste chaînée est vide, les pointeurs de tête et de queue pointent vers le nouveau nœud. Sinon, seul le pointeur de queue pointera vers le nouveau nœud.
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;
}Insérer une opération
Pour insérer un nouveau nœud à un index particulier, vous pouvez utiliser l'opération d'insertion. Cette méthode prend deux paramètres : les données à insérer et l'index auquel elles doivent être insérées. Dans le pire des cas, cette méthode a une complexité temporelle de O(N) car elle peut avoir à parcourir toute la liste.
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;
}Supprimer l'opération
L'opération de suppression parcourt la liste chaînée pour obtenir la référence au nœud à supprimer et supprime le lien du nœud précédent. Semblable à l'opération d'insertion, l'opération de suppression a également une complexité temporelle de O(N) dans le pire des cas.
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;
}Structure de données de file d'attente
La structure des données de la file d'attente est similaire à un groupe de personnes debout dans une file d'attente. La personne qui entre en premier dans la file d'attente est servie avant les autres. De même, cette structure de données linéaire suit l'approche FIFO (premier entré, premier sorti) pour insérer et supprimer des données. Cette structure de données peut être recréée en JavaScript à l'aide d'une liste chaînée de cette manière :
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
}Voici comment insérer et supprimer des données d'une file d'attente en JavaScript :
Opération de mise en file d'attente
L'opération de mise en file d'attente insère de nouvelles données dans la file d'attente. Lors de l'appel de cette méthode, si la structure de données de la file d'attente est vide, les pointeurs avant et arrière pointent vers le nœud nouvellement inséré dans la file d'attente. Si la file d'attente n'est pas vide, le nouveau nœud est ajouté à la fin de la liste et le pointeur arrière pointe sur ce nœud.
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;
}Opération de retrait de la file d'attente
L'opération de suppression de la file d'attente supprime le premier élément de la file d'attente. Au cours de l'opération de suppression de la file d'attente, le pointeur de tête est avancé jusqu'au deuxième nœud de la liste. Ce deuxième nœud devient maintenant la tête de la file d'attente.
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;
}La prochaine étape après les structures de données
Les structures de données peuvent être un concept difficile à comprendre, surtout si vous débutez en programmation. Mais comme toute autre compétence, la pratique peut vous aider à vraiment comprendre et apprécier l'efficacité qu'elle procure pour le stockage et la gestion des données dans vos applications.
Les algorithmes sont tout aussi utiles que les structures de données et pourraient devenir la prochaine étape logique de votre parcours de programmation. Alors, pourquoi ne pas commencer par un algorithme de tri tel que le tri à bulles ?