Algorithmen und Datenstrukturen in TypeScript: Ein vollständiger Leitfaden für Anfänger

Algorithmen und Datenstrukturen in TypeScript: Wo ein Anfänger beginnen sollte

Das Verständnis von Algorithmen und Datenstrukturen ist die Grundlage, die einen professionellen Entwickler von einem Hobbyisten unterscheidet. Wenn Sie gerade erst Ihren Weg in der Programmierung mit TypeScript beginnen, hilft Ihnen dieser Artikel, die wichtigsten Konzepte zu verstehen. Wir behandeln grundlegende Datenstrukturen (Arrays, Stack, Queue) und einfache Algorithmen (lineare und binäre Suche) und zeigen, wie man sie in TypeScript unter Berücksichtigung der strengen Typisierung implementiert.

1. Arrays und die Arbeit mit ihnen in TypeScript

Ein Array ist die einfachste und am häufigsten verwendete Datenstruktur. In TypeScript können Arrays streng typisiert werden, was hilft, Fehler bereits zur Kompilierzeit zu vermeiden.

// Deklaration eines typisierten Zahlen-Arraysconst numbers: number[] = [5, 12, 8, 130, 44];

// Array von Stringsconst fruits: Array<string> = ['apple', 'banana', 'cherry'];

// Zugriff über Indexconsole.log(numbers[0]); // 5

// Hinzufügen eines Elements am Endenumbers.push(100);

// Entfernen des letzten Elementsconst last = numbers.pop();

Wichtig: TypeScript überprüft die Typen zur Kompilierzeit. Wenn Sie versuchen, einen String zu einem Zahlen-Array hinzuzufügen, gibt der Compiler einen Fehler aus. Das macht den Code zuverlässiger.

2. Stack und Queue: Die Prinzipien LIFO und FIFO

Ein Stack (Stapel) arbeitet nach dem LIFO-Prinzip (Last In, First Out – zuletzt herein, zuerst heraus). Eine Queue (Warteschlange) arbeitet nach dem FIFO-Prinzip (First In, First Out – zuerst herein, zuerst heraus).

Implementierung eines Stacks in 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;    }}

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

Implementierung einer Queue in 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;    }}

// Verwendungconst queue = new Queue<string>();queue.enqueue('Aufgabe 1');queue.enqueue('Aufgabe 2');console.log(queue.dequeue()); // 'Aufgabe 1'

Beachten Sie die Verwendung von Generics <T>. Dies ermöglicht die Erstellung von Datenstrukturen, die mit jedem Typ arbeiten, während die strenge Typisierung erhalten bleibt.

3. Suchalgorithmen: Lineare und binäre Suche

Die Suche ist eine der häufigsten Operationen. Wir betrachten zwei grundlegende Algorithmen.

Lineare Suche

Durchläuft alle Elemente des Arrays, bis das gesuchte gefunden wird. Komplexität: O(n).

function linearSearch<T>(arr: T[], target: T): number {    for (let i = 0; i < arr.length; i++) {        if (arr[i] === target) {            return i; // gefunden, Index zurückgeben        }    }    return -1; // nicht gefunden}

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

Binäre Suche (nur für sortierte Arrays)

Teilt das Array bei jedem Schritt in zwei Hälften. Komplexität: O(log n). Dies ist für große Arrays deutlich schneller als die lineare Suche.

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