Algorithmen und Datenstrukturen in TypeScript: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in TypeScript: In der Praxis

TypeScript ist nicht nur ein Aufsatz für JavaScript. Dank strenger Typisierung und moderner Möglichkeiten eignet sich TypeScript ideal für die Implementierung komplexer Algorithmen und Datenstrukturen. In diesem Artikel besprechen wir die wichtigsten Datenstrukturen und Algorithmen mit praktischen Beispielen in TypeScript. Sie erfahren, wie Sie einen Stack, eine Queue, eine verkettete Liste und eine Hash-Tabelle implementieren und erlernen außerdem die Algorithmen der binären Suche und der Sortierung.

1. Stack und Queue: Fundamentale Datenstrukturen

Stack und Queue sind grundlegende Strukturen, die überall verwendet werden: von der Verarbeitung von Funktionsaufrufen bis zur Verwaltung von Aufgaben im Browser.

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

Der Stack arbeitet nach dem Prinzip „Der Letzte kommt zuerst“. Wir implementieren ihn mit einem Array und TypeScript-Generics:

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

// Beispiel zur Verwendungconst numberStack = new Stack<number>();numberStack.push(10);numberStack.push(20);console.log(numberStack.pop()); // 20console.log(numberStack.peek()); // 10

Queue (Warteschlange) — FIFO (First In, First Out)

Die Queue arbeitet nach dem Prinzip „Der Erste kommt zuerst“. Implementierung in 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;    }}

// Beispiel zur Verwendungconst stringQueue = new Queue<string>();stringQueue.enqueue('A');stringQueue.enqueue('B');console.log(stringQueue.dequeue()); // 'A'console.log(stringQueue.front());   // 'B'

Wichtig: Die Operation shift() hat in JavaScript die Komplexität O(n), da sie alle Elemente verschiebt. Für eine leistungsfähigere Queue verwenden Sie eine verkettete Liste oder einen Ringpuffer.

2. Verkettete Liste (Linked List)

Eine verkettete Liste ist eine Sequenz von Knoten, wobei jeder Knoten Daten und einen Verweis auf den nächsten Knoten speichert. In TypeScript können wir Interfaces für eine strenge Typisierung verwenden.

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[] = [];