Algorithmen und Datenstrukturen in TypeScript: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in TypeScript: Von der Theorie zur Praxis

Das Verständnis von Algorithmen und Datenstrukturen ist die Grundlage, die einen erfahrenen Entwickler von einem Anfänger unterscheidet. TypeScript ermöglicht dank strenger Typisierung und moderner Möglichkeiten das Schreiben von zuverlässigem und lesbarem Code zur Lösung klassischer Aufgaben. In diesem Artikel werden wir die wichtigsten Datenstrukturen und Algorithmen anhand praktischer Beispiele mit TypeScript behandeln. Sie erfahren, wie Sie einen Stapel, eine Warteschlange, eine binäre Suche und eine schnelle Sortierung implementieren und lernen die Grundlagen der Arbeit mit Graphen kennen.

1. Grundlegende Datenstrukturen: Stapel und Warteschlange

Stapel und Warteschlange sind einfache, aber äußerst nützliche Strukturen. Ein Stapel arbeitet nach dem LIFO-Prinzip (Last In, First Out), eine Warteschlange nach FIFO (First In, First Out). In TypeScript lassen sie sich bequem auf Basis eines Arrays unter Verwendung von Generics für Typsicherheit implementieren.

Implementierung eines Stapels (Stack)

class Stack<T> {\n    private items: T[] = [];\n\n    push(item: T): void {\n        this.items.push(item);\n    }\n\n    pop(): T | undefined {\n        return this.items.pop();\n    }\n\n    peek(): T | undefined {\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Beispiel zur Verwendung\nconst stack = new Stack<number>();\nstack.push(10);\nstack.push(20);\nconsole.log(stack.pop()); // 20\nconsole.log(stack.peek()); // 10

Implementierung einer Warteschlange (Queue)

class Queue<T> {\n    private items: T[] = [];\n\n    enqueue(item: T): void {\n        this.items.push(item);\n    }\n\n    dequeue(): T | undefined {\n        return this.items.shift();\n    }\n\n    front(): T | undefined {\n        return this.items[0];\n    }\n\n    isEmpty(): boolean {\n        return this.items.length === 0;\n    }\n\n    size(): number {\n        return this.items.length;\n    }\n}\n\n// Beispiel zur Verwendung\nconst queue = new Queue<string>();\nqueue.enqueue('A');\nqueue.enqueue('B');\nconsole.log(queue.dequeue()); // A\nconsole.log(queue.front()); // B

Beachten Sie: Die eingebaute Methode shift() hat eine Komplexität von O(n). Daher ist es für große Datenmengen besser, eine Warteschlange auf Basis einer verketteten Liste zu implementieren.

2. Suchalgorithmen: Lineare und Binäre Suche

Das Suchen von Elementen ist eine der häufigsten Operationen. Die lineare Suche ist einfach, aber bei großen Datenmengen langsam. Die binäre Suche arbeitet mit O(log n), erfordert jedoch ein sortiertes Array.

Lineare Suche

function linearSearch<T>(arr: T[], target: T): number {\n    for (let i = 0; i < arr.length; i++) {\n        if (arr[i] === target) {\n            return i;\n        }\n    }\n    return -1;\n}\n\nconst numbers = [3, 7, 1, 9, 4];\nconsole.log(linearSearch(numbers, 9)); // 3

Binäre Suche (rekursive Version)

function binarySearch<T>(arr: T[], target: T, left: number = 0, right: number = arr.length - 1): number {\n    if (left > right) {\n        return -1;\n    }\n\n    const mid = Math.floor((left + right) / 2);\n\n    if (arr[mid] === target) {\n        return mid;\n    }\n\n    if (arr[mid] > target) {\n        return binarySearch(arr, target, left, mid - 1);\n    } else {\n        return binarySearch(arr, target, mid + 1, right);\n    }\n}\n\nconst sortedArray = [1, 3, 5, 7, 9, 11];\nconsole.log(binarySearch(sortedArray, 7)); // 3\nconsole.log(binarySearch(sortedArray, 6)); // -1

Für die iterative Version verwenden Sie eine while-Schleife. TypeScript hilft, typbezogene Fehler zu vermeiden: Der Generic <T> stellt sicher, dass das Array und das Zielelement denselben Typ haben.

3. Sortierung: Schnelle Sortierung (Quick Sort)

Die schnelle Sortierung ist einer der effizientesten Algorithmen mit einer durchschnittlichen Komplexität von O(n log n). R