Algorithmen und Datenstrukturen in JavaScript: Ein praktischer Leitfaden

Algorithmen und Datenstrukturen in JavaScript: In der Praxis

In der modernen Webentwicklung ist die Kenntnis von Algorithmen und Datenstrukturen nicht nur eine akademische Fähigkeit, sondern ein Werkzeug zur Erstellung schneller und skalierbarer Anwendungen. JavaScript, insbesondere in der Node.js-Umgebung, ermöglicht die Implementierung sowohl einfacher als auch komplexer algorithmischer Konstrukte. In diesem Artikel analysieren wir die wichtigsten Datenstrukturen und Algorithmen in der Praxis, mit Codebeispielen, die Sie sofort in Projekten einsetzen können.

1. Grundlegende Datenstrukturen: Stapel, Warteschlange und verkettete Liste

Beginnen wir mit den Grundlagen. Stapel und Warteschlange sind lineare Strukturen, die häufig beim Parsen, in Aufgabenwarteschlangen und bei der Verwaltung des Aktionsverlaufs verwendet werden.

Stapel (LIFO)

Ein Stapel arbeitet nach dem Prinzip "Last In, First Out". Wir implementieren ihn basierend auf einem Array:

class Stack {  constructor() {    this.items = [];  }

  push(element) {    this.items.push(element);  }

  pop() {    return this.items.pop();  }

  peek() {    return this.items[this.items.length - 1];  }

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

// Beispiel zur Verwendungconst stack = new Stack();stack.push('Seite 1');stack.push('Seite 2');console.log(stack.pop()); // 'Seite 2'

Warteschlange (FIFO)

Eine Warteschlange ist nützlich für die Verarbeitung von Aufgaben in der Reihenfolge ihres Eingangs. Implementierung mit einer Klasse:

class Queue {  constructor() {    this.items = {};    this.front = 0;    this.rear = 0;  }

  enqueue(element) {    this.items[this.rear] = element;    this.rear++;  }

  dequeue() {    const item = this.items[this.front];    delete this.items[this.front];    this.front++;    return item;  }

  peek() {    return this.items[this.front];  }

  size() {    return this.rear - this.front;  }}

// Beispielconst queue = new Queue();queue.enqueue('Aufgabe 1');queue.enqueue('Aufgabe 2');console.log(queue.dequeue()); // 'Aufgabe 1'

Verkettete Liste

Eine verkettete Liste ist effizient für das Einfügen und Löschen von Elementen in der Mitte der Liste. Wir implementieren eine einfach verkettete Liste:

class Node {  constructor(value) {    this.value = value;    this.next = null;  }}

class LinkedList {  constructor() {    this.head = null;    this.tail = null;    this.length = 0;  }

  append(value) {    const newNode = new Node(value);    if (!this.head) {      this.head = newNode;      this.tail = newNode;    } else {      this.tail.next = newNode;      this.tail = newNode;    }    this.length++;  }

  prepend(value) {    const newNode = new Node(value);    newNode.next = this.head;    this.head = newNode;    if (!this.tail) {      this.tail = newNode;    }    this.length++;  }

  print() {    const arr = [];    let current = this.head;    while (current) {      arr.push(current.value);      current = current.next;    }    return arr;  }}

// Beispielconst list = new LinkedList();list.append(10);list.append(20);list.prepend(5);console.log(list.print()); // [5, 10, 20]

2. Suchalgorithmen: Lineare und binäre Suche

Suchen ist eine der häufigsten Operationen. Wir betrachten zwei Ansätze: die einfache lineare Suche und die effiziente binäre Suche.

Lineare Suche

Geeignet für unsortierte Daten. Komplexität O(n):

function linearSearch(arr, target) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === target) {      return i; // Gibt den Index zurück    }  }  return -1;}

console.log(linearSearch([3, 7, 1, 9, 4], 9)); // 3

Binäre Suche

Erfordert ein sortiertes Array. Komplexität O(log n). Implementierung in Node.js:

function binarySearch(arr, target) {  let left = 0;  let right = arr.length - 1;

  while (left <= right) {    const mid = M