Algorithmes et structures de données en JavaScript : guide pratique

Algorithmes et structures de données en JavaScript : de la théorie à la pratique

La maîtrise des algorithmes et des structures de données est une compétence clé pour tout développeur, quel que soit le langage de programmation. JavaScript (notamment dans l'environnement Node.js) ne fait pas exception. Dans cet article, nous allons examiner les structures de données fondamentales et les algorithmes classiques, en les implémentant en JavaScript pur. Vous verrez comment la pile, la file d'attente, la liste chaînée, l'arbre et les algorithmes de tri/recherche sont utilisés dans des problèmes réels de développement back-end avec Node.js.

1. Pile et file d'attente : structures de base pour la gestion des données

La pile (Stack) et la file d'attente (Queue) sont des structures de données linéaires qui diffèrent par les règles d'ajout et de suppression des éléments. La pile fonctionne selon le principe LIFO (Last In, First Out), tandis que la file d'attente suit le principe FIFO (First In, First Out).

Implémentation d'une pile en JavaScript

En JavaScript, une pile peut être implémentée à l'aide d'un tableau ou d'une liste chaînée. Voici une version simple avec un tableau :

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Exemple d'utilisation\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

La pile est souvent utilisée pour vérifier l'équilibre des parenthèses, implémenter le bouton "Précédent" dans un navigateur ou pour le parcours en profondeur des arbres.

Implémentation d'une file d'attente en JavaScript

La file d'attente peut également être construite avec un tableau, mais pour de meilleures performances (en évitant le réindexage lors de l'utilisation de shift), on utilise une liste chaînée ou deux piles. Voici une implémentation simple avec un tableau :

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Exemple d'utilisation\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

Les files d'attente sont utilisées dans les systèmes de gestion des tâches, dans les algorithmes BFS (parcours en largeur) et pour la mise en mémoire tampon des données dans Node.js (par exemple, les flux).

2. Liste chaînée : structure dynamique pour les insertions fréquentes

La liste chaînée (Linked List) est une séquence de nœuds, chacun contenant des données et une référence vers le nœud suivant. Contrairement à un tableau, l'insertion et la suppression d'éléments au milieu de la liste s'effectuent en O(1) si l'on dispose d'une référence au nœud.

Implémentation d'une liste simplement chaînée

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n