Datenstrukturen meistern: Der JavaScript/TypeScript Interview-Guide

3. März 2026

datenstrukturen typescript javascript interview-vorbereitung informatik

In this article

1. Arrays (Die Grundlage)
Manuelle Implementierung
2. Hash-Tabellen (Objekte / Maps)
Manuelle Implementierung
3. Verkettete Listen (Linked Lists)
Manuelle Implementierung
4. Stacks (LIFO)
Manuelle Implementierung
5. Queues (Warteschlangen - FIFO)
Manuelle Implementierung
6. Binäre Suchbäume (BST)
Manuelle Implementierung
7. Graphen
Typen von Graphen
Darstellung im Code
8. Heaps (Kurze Erwähnung)
Zusammenfassung: Cheat Sheet

Aufbauend auf unserer Diskussion über die Big O Notation ist der nächste entscheidende Schritt zum Erfolg in technischen Interviews das Meistern von Datenstrukturen. Um sie wirklich zu verstehen, sollten wir nicht nur integrierte Methoden verwenden - wir sollten sie von Grund auf selbst bauen.

In diesem Guide werden wir die wichtigsten Strukturen implementieren, ihre Performance-”Fallen” analysieren und die “Senior”-Einsichten lernen, nach denen Interviewer suchen.

Datenstrukturen meistern

1. Arrays (Die Grundlage)

In Low-Level-Sprachen sind Arrays zusammenhängende Speicherblöcke. In JavaScript sind sie viel flexibler, aber diese Flexibilität hat einen versteckten “Preis”.

Manuelle Implementierung

class MyArray<T> {
  private length: number = 0;
  private data: { [key: number]: T } = {};

  get(index: number): T { return this.data[index]; } // O(1)

  push(item: T): number {
    this.data[this.length] = item;
    this.length++;
    return this.length; // O(1)
  }

  pop(): T | undefined {
    const lastItem = this.data[this.length - 1];
    delete this.data[this.length - 1];
    this.length--;
    return lastItem; // O(1)
  }

  delete(index: number): T | undefined {
    const item = this.data[index];
    this.shiftItems(index); // O(n)
    return item;
  }

  private shiftItems(index: number) {
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    delete this.data[this.length - 1];
    this.length--;
  }
}

[!IMPORTANT] Die String-Falle: In JS sind Strings unveränderlich (immutable). Obwohl str[0] wie ein Array-Zugriff aussieht, können Sie ihn nicht ändern. Das Verketten von Strings in einer Schleife (str += next) erzeugt jedes Mal einen neuen String, was zu einer Komplexität von $O(n^2)$ führt. Pro-Tipp: Verwenden Sie für umfangreiche Textmanipulationen immer ein Array und .join('').

2. Hash-Tabellen (Objekte / Maps)

Hash-Tabellen speichern Schlüssel-Wert-Paare. Sie verwenden eine Hash-Funktion, um einen Schlüssel einem bestimmten Index in einem internen Array zuzuordnen.

Manuelle Implementierung

class MyHashTable {
  private data: any[][];
  constructor(size: number) { this.data = new Array(size); }

  private _hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }

  set(key: string, value: any) {
    const adresse = this._hash(key);
    if (!this.data[adresse]) this.data[adresse] = [];
    this.data[adresse].push([key, value]); // Behandlung von Kollisionen via Separate Chaining
  }

  get(key: string) {
    const adresse = this._hash(key);
    const bucket = this.data[adresse];
    if (bucket) {
      for (const pair of bucket) {
        if (pair[0] === key) return pair[1]; // O(1) Durchschnitt, O(n) Worst Case
      }
    }
  }
}

3. Verkettete Listen (Linked Lists)

Eine Sammlung von Knoten, bei der jeder auf den nächsten zeigt. Im Gegensatz zu Arrays sind Knoten im Speicher nicht unbedingt zusammenhängend.

Manuelle Implementierung

class ListNode<T> {
  constructor(public value: T, public next: ListNode<T> | null = null) {}
}

class MyLinkedList<T> {
  head: ListNode<T> | null = null;
  tail: ListNode<T> | null = null;
  length: number = 0;

  append(value: T) {
    const newNode = new ListNode(value);
    if (!this.head) { this.head = newNode; this.tail = newNode; }
    else { this.tail!.next = newNode; this.tail = newNode; }
    this.length++; // O(1) dank Tail-Pointer
  }

  prepend(value: T) {
    this.head = new ListNode(value, this.head);
    if (!this.tail) this.tail = this.head;
    this.length++; // O(1)
  }

  insert(index: number, value: T) {
    if (index >= this.length) return this.append(value);
    if (index === 0) return this.prepend(value);

    const leader = this._getAt(index - 1);
    const newNode = new ListNode(value, leader!.next);
    leader!.next = newNode;
    this.length++; // O(n) Suche + O(1) Einfügen
  }

  private _getAt(index: number) {
    let aktuell = this.head;
    for (let i = 0; i < index; i++) aktuell = aktuell!.next;
    return aktuell;
  }
}

4. Stacks (LIFO)

Ein Stack folgt dem Last-In, First-Out-Prinzip. Stellen Sie sich einen Stapel Bücher vor: Sie legen Bücher obenauf und nehmen sie von oben weg. In der Softwareentwicklung wird so der Call Stack (Aufrufstapel) verwaltet.

Manuelle Implementierung

class Stack<T> {
  private items: T[] = [];

  push(item: T) {
    this.items.push(item); // O(1)
  }

  pop(): T | undefined {
    return this.items.pop(); // O(1)
  }

  peek(): T | undefined {
    return this.items[this.items.length - 1]; // O(1)
  }

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

5. Queues (Warteschlangen - FIFO)

Eine Queue folgt dem First-In, First-Out-Prinzip. Wie eine Schlange an der Kasse: Wer zuerst kommt, wird zuerst bedient. Dies ist entscheidend für die Aufgabenwarteschlange des Event Loops in JavaScript.

Manuelle Implementierung

Die Verwendung von Array.shift() für dequeue ist $O(n)$ , da jedes andere Element verschoben werden muss. Für echte $O(1)$ -Performance verwenden wir eine verkettete Liste.

class Queue<T> {
  private list = new MyLinkedList<T>();

  enqueue(item: T) {
    this.list.append(item); // O(1)
  }

  dequeue(): T | null {
    if (this.list.length === 0) return null;
    const value = this.list.head!.value;
    this.list.head = this.list.head!.next;
    this.list.length--;
    if (this.list.length === 0) this.list.tail = null;
    return value; // O(1)
  }

  peek(): T | null {
    return this.list.head ? this.list.head.value : null; // O(1)
  }
}

6. Binäre Suchbäume (BST)

Bäume sind hierarchische Datenstrukturen. Ein Binärer Suchbaum (BST) ist ein spezifischer Typ, bei dem für jeden Knoten gilt:

Alle Knoten im linken Teilbaum haben einen kleineren Wert.
Alle Knoten im rechten Teilbaum haben einen größeren Wert.

Manuelle Implementierung

class TreeNode<T> {
  constructor(
    public value: T,
    public left: TreeNode<T> | null = null,
    public right: TreeNode<T> | null = null
  ) {}
}

class BST<T> {
  root: TreeNode<T> | null = null;

  // Ein Element hinzufügen und dabei die BST-Eigenschaft beibehalten
  add(value: T) {
    const newNode = new TreeNode(value);
    if (!this.root) { this.root = newNode; return; }

    let curr = this.root;
    while (true) {
      if (value < curr.value) {
        if (!curr.left) { curr.left = newNode; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = newNode; return; }
        curr = curr.right;
      }
    }
  }

  // Ein Element finden: Durchschnittlich O(log n)
  find(value: T): TreeNode<T> | null {
    let curr = this.root;
    while (curr) {
      if (value === curr.value) return curr;
      curr = value < curr.value ? curr.left : curr.right;
    }
    return null;
  }
}

[!WARNING] Performance-Falle: Wenn Elemente sortiert eingefügt werden (z.B. 1, 2, 3, 4), wird der Baum zu einer einfachen Linie (einseitig). Die Komplexität verschlechtert sich von $O(\log n)$ zu $O(n)$ . Selbstbalancierende Bäume (wie AVL- oder Rot-Schwarz-Bäume) lösen dies durch Rotationen, um die Höhe minimal zu halten.

7. Graphen

Graphen repräsentieren Knoten (Ecken) und die Verbindungen (Kanten) zwischen ihnen. Sie sind überall: soziale Netzwerke, das Internet und Landkarten.

Typen von Graphen

Gerichtet vs. Ungerichtet: In einem gerichteten Graph (wie Twitter) ist das Folgen einseitig. In einem ungerichteten Graph (wie bei einer physischen Straße) kann man in beide Richtungen gehen.
Gewichtet vs. Ungewichtet: Gewichtete Graphen (wie Google Maps) haben “Kosten” oder Entfernungen an jeder Kante.

Darstellung im Code

Stellen Sie sich drei Knoten (0, 1, 2) vor, die in einem Dreieck verbunden sind.

1. Kantenliste (Edge List)

Ein einfaches Array, das die Verbindungen zeigt.

const graph = [[0, 1], [1, 2], [2, 0]];

2. Adjazenzliste (Adjacency List)

Eine Zuordnung jedes Knotens zu seinen Nachbarn. Dies ist die häufigste Implementierung in Interviews, da sie speichereffizient ist.

const adjacencyList = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1]
};

3. Adjazenzmatrix

Ein Gitter, in dem 1 eine Verbindung anzeigt und 0 keine.

const matrix = [
  [0, 1, 1], // Knoten 0 ist mit 1 und 2 verbunden
  [1, 0, 1], // Knoten 1 ist mit 0 und 2 verbunden
  [1, 1, 0]  // Knoten 2 ist mit 0 und 1 verbunden
];

8. Heaps (Kurze Erwähnung)

Ein Binary Heap ist ein spezieller Baum, bei dem die Wurzel immer das Maximum (Max-Heap) oder Minimum (Min-Heap) ist. Sie werden verwendet, um Prioritätswarteschlangen zu implementieren – essenziell für Algorithmen wie Dijkstra’s.

Zusammenfassung: Cheat Sheet

Weitere Details finden Sie in unserem Leitfaden zur Big O Notation.

Datenstruktur	Zugriff	Suche	Einfügen	Praxisbeispiel
Array	$O(1)$	$O(n)$	$O(n)$	Einfache Listen / Buffer
Hash Map	n.v.	$O(1)$	$O(1)$	Caches / Schnelle Suche
Linked List	$O(n)$	$O(n)$	$O(1)$	Undo/Redo-Systeme
Stack	$O(n)$	$O(n)$	$O(1)$	Funktionsaufrufe / Verlauf
Queue	$O(n)$	$O(n)$	$O(1)$	Task-Scheduling
BST	$O(\log n)$	$O(\log n)$	$O(\log n)$	Hierarchische Daten (DOM)
Graph	n.v.	$O(v + e)$	$O(1)$	Soziale Netzwerke / GPS

Das Beherrschen dieser manuellen Implementierungen und das Verständnis ihrer Abwägungen unterscheidet Junior-Entwickler von Senior-Engineers. Nutzen Sie nicht nur die Werkzeuge - wissen Sie, wie sie gebaut sind.