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

Introduction : Pourquoi les algorithmes et les structures de données sont importants en TypeScript ?

Dans le développement web moderne, TypeScript occupe une position de leader, offrant un typage strict et des outils puissants pour créer des applications évolutives. Cependant, même le code le plus élégant ne sera pas efficace sans la compréhension des algorithmes et structures de données fondamentaux. Cet article est votre guide vers le monde du code optimisé en TypeScript. Nous analyserons les structures de données clés, montrerons comment les implémenter en tenant compte des types, et examinerons les algorithmes classiques. Après avoir lu cet article, vous serez capable d'écrire non seulement un code fonctionnel, mais aussi un code rapide et prévisible.

1. Structures de données de base avec typage

TypeScript permet de définir strictement quels types de données peuvent être stockés dans une structure. Cela évite les erreurs au moment de la compilation. Examinons trois structures fondamentales.

1.1. Pile (Stack) — principe LIFO

La pile fonctionne selon le principe "dernier entré, premier sorti" (Last In, First Out). Elle est idéale pour les tâches où il faut annuler des actions (par exemple, l'historique du navigateur).

// Implémentation d'une pile avec un générique Tclass Stack<T> {    private items: T[] = [];

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

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

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

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

// Exemple d'utilisationconst numberStack = new Stack<number>();numberStack.push(10);numberStack.push(20);console.log(numberStack.pop()); // 20

1.2. File d'attente (Queue) — principe FIFO

La file d'attente fonctionne selon le principe "premier entré, premier sorti" (First In, First Out). Elle est utilisée pour traiter les tâches dans l'ordre de leur arrivée, par exemple, dans les systèmes de files d'attente de messages.

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

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

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

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

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

// Exemple avec un type personnaliséinterface Task {    id: number;    name: string;}const taskQueue = new Queue<Task>();taskQueue.enqueue({ id: 1, name: 'Traiter la commande' });taskQueue.enqueue({ id: 2, name: 'Envoyer un email' });

1.3. Liste chaînée (Linked List)

La liste chaînée est composée de nœuds, chacun faisant référence au suivant. Contrairement au tableau, l'insertion et la suppression d'éléments au milieu de la liste ne nécessitent pas de décaler tous les éléments.

class ListNode<T> {    value: T;    next: ListNode<T> | null = null;

    constructor(value: T) {        this.value = value;    }}

class LinkedList<T> {    private head: ListNode<T> | null = null;

    add(value: T): void {        const newNode = new ListNode(value);        if (!this.head) {            this.head = newNode;            return;        }        let current = this.head;        while (current.next) {            current = current.next;        }        current.next = newNode;    }

    print(): void {        let current = this.head;        while (current) {            console.log(current.value);            current = current.next;        }    }}

// Utilisationconst list = new LinkedList<string>();list.add('TypeScript');list.add('Python');list.print(); // TypeScript, Python

2. Algorithmes de tri et de recherche

Le tri des données est l'une des opérations les plus courantes. TypeScript permet de créer des fonctions universelles qui fonctionnent avec n'importe quel type de données.

2.1. Tri rapide (Quick Sort)

L'un des algorithmes les plus efficaces avec