Algorithmes et structures de données en TypeScript : guide complet

Algorithmes et structures de données en TypeScript : du débutant au professionnel

Les algorithmes et les structures de données sont le fondement sur lequel repose tout le développement logiciel moderne. Que vous écriviez du frontend avec React, du backend avec Node.js ou une application mobile, une compréhension approfondie de ces concepts vous permet de créer des applications efficaces, évolutives et rapides. Dans cet article, nous allons détailler les algorithmes et structures de données clés en TypeScript — un langage qui combine la flexibilité de JavaScript et la rigueur du typage statique.

TypeScript est idéal pour l'apprentissage des algorithmes : le typage strict aide à éviter les erreurs dès la phase de compilation, et la prise en charge des generics permet de créer des structures de données universelles et réutilisables. Nous commencerons par des concepts simples et passerons progressivement à des sujets plus complexes, en accompagnant chaque étape d'exemples de code clairs.

1. Structures de données de base : Pile et File

La Pile (Stack) et la File (Queue) sont des structures de données linéaires fondamentales, utilisées partout : de la gestion de l'historique du navigateur à la planification des tâches dans les systèmes d'exploitation. Examinons leur implémentation en TypeScript.

Pile (LIFO — Last In, First Out)

La pile fonctionne sur le principe "dernier entré, premier sorti". Les opérations principales sont : push (ajout d'un élément) et pop (extraction du dernier élément).

class Stack<T> {
    private items: T[] = [];

    push(element: T): void {
        this.items.push(element);
    }

    pop(): T | undefined {
        return this.items.pop();
    }

    peek(): T | undefined {
        return this.items[this.items.length - 1];
    }

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

    size(): number {
        return this.items.length;
    }
}

// Exemple d'utilisation
const stack = new Stack<number>();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
console.log(stack.peek()); // 2

File (FIFO — First In, First Out)

La file fonctionne sur le principe "premier entré, premier sorti". Les opérations principales sont : enqueue (ajout à la fin) et dequeue (extraction du début).

class Queue<T> {
    private items: T[] = [];

    enqueue(element: T): void {
        this.items.push(element);
    }

    dequeue(): T | undefined {
        return this.items.shift();
    }

    front(): T | undefined {
        return this.items[0];
    }

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

    size(): number {
        return this.items.length;
    }
}

// Exemple d'utilisation
const queue = new Queue<string>();
queue.enqueue("Premier");
queue.enqueue("Deuxième");
queue.enqueue("Troisième");
console.log(queue.dequeue()); // "Premier"
console.log(queue.front()); // "Deuxième"

2. Algorithmes de recherche : Recherche linéaire et binaire

La recherche de données est l'une des opérations les plus courantes en programmation. Nous allons examiner deux approches principales : la recherche linéaire (simple mais lente) et la recherche binaire (rapide mais nécessitant des données triées).

Recherche linéaire

L'algorithme vérifie séquentiellement chaque élément du tableau jusqu'à trouver la cible. Complexité temporelle : O(n).

function linearSearch<T>(arr: T[], target: T): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i; // Retourne l'index de l'élément trouvé
        }
    }
    return -1; // Élément non trouvé
}

// Exemple
const numbers = [10, 20, 30, 40, 50];
console.log(linearSearch(numbers, 30)); // 2
console.log(linearSearch(numbers, 60)); // -1

Recherche binaire

La recherche binaire ne fonctionne que sur des tableaux triés. Elle divise le tableau en deux à chaque étape, en éliminant la moitié