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

Algorithmes et structures de données en TypeScript : par où commencer pour un débutant

La compréhension des algorithmes et des structures de données est le fondement qui distingue un développeur professionnel d'un amateur. Si vous débutez tout juste votre parcours en programmation TypeScript, cet article vous aidera à comprendre les concepts clés. Nous aborderons les structures de données de base (tableaux, pile, file) et les algorithmes simples (recherche linéaire et binaire), et nous montrerons comment les implémenter en TypeScript en tenant compte du typage strict.

1. Tableaux et leur manipulation en TypeScript

Le tableau est la structure de données la plus simple et la plus utilisée. En TypeScript, les tableaux peuvent être strictement typés, ce qui permet d'éviter les erreurs dès la phase de compilation.

// Déclaration d'un tableau typé de nombresconst numbers: number[] = [5, 12, 8, 130, 44];

// Tableau de chaînes de caractèresconst fruits: Array<string> = ['pomme', 'banane', 'cerise'];

// Accès par indexconsole.log(numbers[0]); // 5

// Ajout d'un élément à la finnumbers.push(100);

// Suppression du dernier élémentconst last = numbers.pop();

Important : TypeScript vérifie les types lors de la compilation. Si vous essayez d'ajouter une chaîne de caractères à un tableau de nombres, le compilateur générera une erreur. Cela rend le code plus fiable.

2. Pile et file : principes LIFO et FIFO

La pile (Stack) fonctionne selon le principe LIFO (Last In, First Out — dernier entré, premier sorti). La file (Queue) fonctionne selon le principe FIFO (First In, First Out — premier entré, premier sorti).

Implémentation d'une pile en TypeScript

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;    }}

// Utilisationconst stack = new Stack<number>();stack.push(10);stack.push(20);console.log(stack.pop()); // 20console.log(stack.peek()); // 10

Implémentation d'une file en TypeScript

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;    }}

// Utilisationconst queue = new Queue<string>();queue.enqueue('tâche 1');queue.enqueue('tâche 2');console.log(queue.dequeue()); // 'tâche 1'

Notez l'utilisation des génériques <T>. Cela permet de créer des structures de données fonctionnant avec n'importe quel type, tout en conservant un typage strict.

3. Algorithmes de recherche : linéaire et binaire

La recherche est l'une des opérations les plus courantes. Examinons deux algorithmes de base.

Recherche linéaire

Parcourt tous les éléments du tableau jusqu'à trouver celui recherché. Complexité : O(n).

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

const data = [3, 7, 1, 9, 4];console.log(linearSearch(data, 9)); // 3console.log(linearSearch(data, 10)); // -1

Recherche binaire (uniquement pour les tableaux triés)

Divise le tableau en deux à chaque étape. Complexité : O(log n). C'est nettement plus rapide que la recherche linéaire pour les grands tableaux.

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

    while (left <= right) {        const mid = Math.floor((left + right) / 2);