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

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

Dans le développement web moderne, la connaissance des algorithmes et des structures de données n'est pas seulement une compétence académique, mais un outil pour créer des applications rapides et évolutives. JavaScript, en particulier dans l'environnement Node.js, permet d'implémenter des constructions algorithmiques simples et complexes. Dans cet article, nous allons analyser les structures de données et les algorithmes clés en pratique, avec des exemples de code que vous pouvez utiliser immédiatement dans vos projets.

1. Structures de données de base : pile, file d'attente et liste chaînée

Commençons par les fondamentaux. La pile et la file d'attente sont des structures linéaires souvent utilisées dans l'analyse syntaxique, les files de tâches et la gestion de l'historique des actions.

Pile (LIFO)

La pile fonctionne selon le principe "dernier arrivé, premier sorti". Implémentons-la à l'aide d'un tableau :

class Stack {  constructor() {    this.items = [];  }

  push(element) {    this.items.push(element);  }

  pop() {    return this.items.pop();  }

  peek() {    return this.items[this.items.length - 1];  }

  isEmpty() {    return this.items.length === 0;  }}

// Exemple d'utilisationconst stack = new Stack();stack.push('Page 1');stack.push('Page 2');console.log(stack.pop()); // 'Page 2'

File d'attente (FIFO)

La file d'attente est utile pour traiter les tâches dans l'ordre d'arrivée. Implémentation avec une classe :

class Queue {  constructor() {    this.items = {};    this.front = 0;    this.rear = 0;  }

  enqueue(element) {    this.items[this.rear] = element;    this.rear++;  }

  dequeue() {    const item = this.items[this.front];    delete this.items[this.front];    this.front++;    return item;  }

  peek() {    return this.items[this.front];  }

  size() {    return this.rear - this.front;  }}

// Exempleconst queue = new Queue();queue.enqueue('Tâche 1');queue.enqueue('Tâche 2');console.log(queue.dequeue()); // 'Tâche 1'

Liste chaînée

La liste chaînée est efficace pour l'insertion et la suppression d'éléments au milieu de la liste. Implémentons une liste simplement chaînée :

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}

class LinkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  }

  append(value) {    const newNode = new Node(value);    if (!this.head) {      this.head = newNode;      this.tail = newNode;    } else {      this.tail.next = newNode;      this.tail = newNode;    }    this.length++;  }

  prepend(value) {    const newNode = new Node(value);    newNode.next = this.head;    this.head = newNode;    if (!this.tail) {      this.tail = newNode;    }    this.length++;  }

  print() {    const arr = [];    let current = this.head;    while (current) {      arr.push(current.value);      current = current.next;    }    return arr;  }}

// Exempleconst list = new LinkedList();list.append(10);list.append(20);list.prepend(5);console.log(list.print()); // [5, 10, 20]

2. Algorithmes de recherche : linéaire et binaire

La recherche est l'une des opérations les plus courantes. Examinons deux approches : la recherche linéaire simple et la recherche binaire efficace.

Recherche linéaire

Convient aux données non triées. Complexité O(n) :

function linearSearch(arr, target) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === target) {      return i; // Retourne l'index    }  }  return -1;}

console.log(linearSearch([3, 7, 1, 9, 4], 9)); // 3

Recherche binaire

Nécessite un tableau trié. Complexité O(log n). Implémentation en Node.js :

function binarySearch(arr, target) {  let left = 0;  let right = arr.length - 1;

  while (left <= right) {    const mid = M