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

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

TypeScript n'est pas simplement une surcouche de JavaScript. Grâce à son typage strict et à ses fonctionnalités modernes, TypeScript est idéal pour implémenter des algorithmes et des structures de données complexes. Dans cet article, nous allons examiner les structures de données et les algorithmes clés avec des exemples pratiques en TypeScript. Vous apprendrez à implémenter une pile, une file d'attente, une liste chaînée, une table de hachage, et vous maîtriserez les algorithmes de recherche binaire et de tri.

1. Pile et file d'attente : structures de données fondamentales

La pile et la file d'attente sont des structures de base utilisées partout : du traitement des appels de fonctions à la gestion des tâches dans le navigateur.

Pile (Stack) — LIFO (Last In, First Out)

La pile fonctionne selon le principe « dernier arrivé, premier sorti ». Implémentons-la à l'aide d'un tableau et des génériques TypeScript :

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

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

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

File d'attente (Queue) — FIFO (First In, First Out)

La file d'attente fonctionne selon le principe « premier arrivé, premier sorti ». Implémentation en TypeScript :

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

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

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

// Exemple d'utilisationconst stringQueue = new Queue<string>();stringQueue.enqueue('A');stringQueue.enqueue('B');console.log(stringQueue.dequeue()); // 'A'console.log(stringQueue.front());   // 'B'

Important : L'opération shift() en JavaScript a une complexité O(n), car elle décale tous les éléments. Pour une file d'attente plus performante, utilisez une liste chaînée ou un tampon circulaire.

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

Une liste chaînée est une séquence de nœuds, où chaque nœud stocke des données et une référence au nœud suivant. En TypeScript, nous pouvons utiliser des interfaces pour un typage strict.

interface ListNode<T> {    value: T;    next: ListNode<T> | null;}

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

    append(value: T): void {        const newNode: ListNode<T> = { value, next: null };        if (!this.head) {            this.head = newNode;            return;        }        let current = this.head;        while (current.next) {            current = current.next;        }        current.next = newNode;    }

    prepend(value: T): void {        const newNode: ListNode<T> = { value, next: this.head };        this.head = newNode;    }

    delete(value: T): void {        if (!this.head) return;        if (this.head.value === value) {            this.head = this.head.next;            return;        }        let current = this.head;        while (current.next) {            if (current.next.value === value) {                current.next = current.next.next;                return;            }            current = current.next;        }    }

    print(): void {        let current = this.head;        const values: T[] = [];