Algorithmen und Datenstrukturen in JavaScript: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in JavaScript: Von der Theorie zur Praxis

Die Fähigkeit, mit Algorithmen und Datenstrukturen zu arbeiten, ist eine Schlüsselkompetenz jedes Entwicklers, unabhängig von der Programmiersprache. JavaScript (insbesondere in der Node.js-Umgebung) bildet hier keine Ausnahme. In diesem Artikel behandeln wir die grundlegenden Datenstrukturen und klassischen Algorithmen und implementieren sie in reinem JavaScript. Sie werden sehen, wie Stack, Queue, verkettete Liste, Baum sowie Sortier-/Suchalgorithmen in realen Backend-Entwicklungsaufgaben mit Node.js angewendet werden.

1. Stack und Queue: Grundlegende Strukturen zur Datenverwaltung

Stack und Queue sind lineare Datenstrukturen, die sich in den Regeln zum Hinzufügen und Entfernen von Elementen unterscheiden. Ein Stack arbeitet nach dem LIFO-Prinzip (Last In, First Out), eine Queue nach dem FIFO-Prinzip (First In, First Out).

Implementierung eines Stacks in JavaScript

In JavaScript kann ein Stack basierend auf einem Array oder einer verketteten Liste implementiert werden. Betrachten wir eine einfache Variante mit einem Array:

class Stack {\n    constructor() {\n        this.items = [];\n    }\n\n    push(element) {\n        this.items.push(element);\n    }\n\n    pop() {\n        if (this.isEmpty()) return null;\n        return this.items.pop();\n    }\n\n    peek() {\n        if (this.isEmpty()) return null;\n        return this.items[this.items.length - 1];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Beispiel zur Verwendung\nconst stack = new Stack();\nstack.push('A');\nstack.push('B');\nstack.push('C');\nconsole.log(stack.pop());  // 'C'\nconsole.log(stack.peek()); // 'B'

Ein Stack wird häufig verwendet, um die Ausgewogenheit von Klammern zu prüfen, die "Zurück"-Schaltfläche im Browser zu implementieren oder Bäume in der Tiefe zu durchlaufen.

Implementierung einer Queue in JavaScript

Eine Queue kann ebenfalls mit einem Array aufgebaut werden, aber für eine bessere Leistung (Vermeidung der Neuindizierung bei shift) verwenden wir eine verkettete Liste oder zwei Stacks. Hier ist eine einfache Implementierung mit einem Array:

class Queue {\n    constructor() {\n        this.items = [];\n    }\n\n    enqueue(element) {\n        this.items.push(element);\n    }\n\n    dequeue() {\n        if (this.isEmpty()) return null;\n        return this.items.shift();\n    }\n\n    front() {\n        if (this.isEmpty()) return null;\n        return this.items[0];\n    }\n\n    isEmpty() {\n        return this.items.length === 0;\n    }\n\n    size() {\n        return this.items.length;\n    }\n}\n\n// Beispiel zur Verwendung\nconst queue = new Queue();\nqueue.enqueue(1);\nqueue.enqueue(2);\nqueue.enqueue(3);\nconsole.log(queue.dequeue()); // 1\nconsole.log(queue.front());   // 2

Queues werden in Aufgabenverwaltungssystemen, in BFS-Algorithmen (Breitensuche) und zur Datenpufferung in Node.js (z. B. Streams) verwendet.

2. Verkettete Liste: Dynamische Struktur für häufige Einfügungen

Eine verkettete Liste (Linked List) ist eine Sequenz von Knoten, von denen jeder Daten und einen Verweis auf den nächsten Knoten enthält. Im Gegensatz zu einem Array erfolgen Einfügen und Löschen von Elementen in der Mitte der Liste in O(1), wenn ein Verweis auf den Knoten vorhanden ist.

Implementierung einer einfach verketteten Liste

class ListNode {\n    constructor(value, next = null) {\n        this.value = value;\n        this.next = next;\n    }\n}\n\nclass LinkedList {\n    constructor() {\n        this.head = null;\n        this.tail = null;\n        this.length = 0;\n    }\n\n    append(value) {\n        const newNode = new ListNode(value);\n        if (!this.head) {\n            this.head = newNode;\n            this.tail = newNode;\n        } else {\n            this.tail.next = newNode;\n            this.tail = newNode;\n        }\n        this.length++;\n        return this;\n    }\n\n    prepend(value) {\n        const newNode = new ListNode(value, this.head);\n        this.head = newNode;\n        if (!this.tail) this.tail = newNode;\n