Datenstrukturen

Geschätzte Lektüre: 13 Minuten 374 Ansichten

Datenstrukturen bilden das fundamentale Gerüst jeder Softwareanwendung – sie sind die organisierten Methoden, wie wir Informationen speichern, verwalten und abrufen. In JavaScript, einer Sprache die ursprünglich für einfache Webinteraktionen entwickelt wurde, haben sich die Datenstrukturen mit der Zeit zu einem mächtigen Werkzeugset entwickelt, das heute komplexe Anwendungen ermöglicht.

Grundlegende Datenstrukturen in JavaScript

Arrays: Die vielseitigen Sammlungen

Arrays sind die wohl am häufigsten verwendete Datenstruktur in JavaScript. Sie repräsentieren eine geordnete Sammlung von Werten, die unterschiedliche Datentypen enthalten können. Ein entscheidendes Merkmal von Arrays ist ihr numerischer Index, der bei 0 beginnt.

// Array-Erstellung
const fruits = ['Apfel', 'Banane', 'Orange'];

// Zugriff auf Elemente
console.log(fruits[1]); // Ausgabe: 'Banane'

// Modifikation
fruits.push('Mango'); // Fügt am Ende hinzu
fruits.unshift('Erdbeere'); // Fügt am Anfang hinzu

// Iteration
fruits.forEach(fruit => console.log(fruit));

Arrays bieten zahlreiche hilfreiche Methoden wie map(), filter(), und reduce(), die funktionale Programmierung ermöglichen. Besonders bemerkenswert ist, dass JavaScript-Arrays dynamisch sind – ihre Größe kann sich zur Laufzeit ändern, im Gegensatz zu statischen Arrays in Sprachen wie C oder Java.

Objekte: Schlüssel-Wert-Paare

Objekte sind die grundlegende Datenstruktur für die Darstellung von Entitäten mit Eigenschaften. Sie speichern Daten in Form von Schlüssel-Wert-Paaren, wobei der Schlüssel immer ein String (oder Symbol) ist.

const person = {
    name: 'Max Mustermann',
    age: 30,
    beruf: 'Entwickler',
    adresse: {
        stadt: 'Berlin',
        land: 'Deutschland'
    }
};

// Zugriff auf Eigenschaften
console.log(person.name); // Dot-Notation
console.log(person['age']); // Klammer-Notation

// Dynamische Eigenschaften
const eigenschaft = 'beruf';
console.log(person[eigenschaft]); // 'Entwickler'

Objekte sind besonders nützlich, wenn Sie Daten mit einer klaren semantischen Struktur darstellen müssen. Mit ES6 wurden zudem berechnete Eigenschaftsnamen eingeführt, die dynamische Schlüssel ermöglichen.

Sets: Sammlungen eindeutiger Werte

Das Set-Objekt wurde mit ES6 eingeführt und speichert eindeutige Werte jeglichen Typs. Im Gegensatz zu Arrays erlaubt ein Set keine Duplikate und hat keine Index-basierte Zugriffsmethode.

const uniqueNumbers = new Set();
uniqueNumbers.add(1);
uniqueNumbers.add(2);
uniqueNumbers.add(1); // Wird ignoriert

console.log(uniqueNumbers.size); // 2
console.log(uniqueNumbers.has(2)); // true

// Konvertierung zu Array
const numbersArray = [...uniqueNumbers];

Sets sind besonders effizient für Überprüfungen, ob ein Element vorhanden ist (O(1) Komplexität), während Arrays hier O(n) benötigen.

Maps: Geordnete Schlüssel-Wert-Paare

Ähnlich wie Objekte speichern Maps Schlüssel-Wert-Paare, aber mit einigen wichtigen Unterschieden: Die Schlüssel können von jedem Datentyp sein (nicht nur Strings oder Symbole), und die Reihenfolge der Einträge wird beibehalten.

const userMap = new Map();

// Schlüssel können beliebige Typen sein
userMap.set(1, 'Admin');
userMap.set('name', 'Max');
userMap.set(true, 'Aktiv');

console.log(userMap.get(1)); // 'Admin'
console.log(userMap.size); // 3

// Iteration
userMap.forEach((value, key) => {
    console.log(`${key}: ${value}`);
});

Maps sind besonders nützlich, wenn Sie nicht-String-Schlüssel benötigen oder die Einfügereihenfolge wichtig ist.

Komplexere Datenstrukturen

Verkettete Listen (Linked Lists)

Obwohl JavaScript keine eingebaute Linked-List-Implementierung hat, können wir sie selbst erstellen. Eine einfach verkettete Liste besteht aus Knoten (Nodes), wobei jeder Knoten auf den nächsten verweist.

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

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

    append(value) {
        const newNode = new ListNode(value);
        
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
            return;
        }
        
        this.tail.next = newNode;
        this.tail = newNode;
    }
}

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);

Verkettete Listen sind effizient für Einfüge- und Löschoperationen an beliebigen Positionen (O(1) wenn der Knoten bekannt ist), während Arrays hier O(n) benötigen.

Stapel (Stacks) und Warteschlangen (Queues)

Stacks (LIFO-Prinzip) und Queues (FIFO-Prinzip) können sowohl mit Arrays als auch mit Linked Lists implementiert werden.

• Stack-Implementierung:

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(element) {
        this.items.push(element);
    }
    
    pop() {
        if (this.items.length === 0) return null;
        return this.items.pop();
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
}

• Queue-Implementierung:

class Queue {
    constructor() {
        this.items = [];
    }
    
    enqueue(element) {
        this.items.push(element);
    }
    
    dequeue() {
        return this.items.shift();
    }
    
    front() {
        if (this.isEmpty()) return null;
        return this.items[0];
    }
}

In modernem JavaScript können wir für Queues auch die Map-Datenstruktur nutzen, die die Einfügereihenfolge beibehält.

Bäume (Trees) und Graphen (Graphs)

Bäume sind hierarchische Datenstrukturen mit einem Wurzelknoten und Kindknoten. Ein spezieller Fall ist der Binärbaum, wo jeder Knoten maximal zwei Kinder hat.

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }
    
    insert(value) {
        const newNode = new TreeNode(value);
        
        if (!this.root) {
            this.root = newNode;
            return;
        }
        
        let current = this.root;
        while (true) {
            if (value < current.value) {
                if (!current.left) {
                    current.left = newNode;
                    return;
                }
                current = current.left;
            } else {
                if (!current.right) {
                    current.right = newNode;
                    return;
                }
                current = current.right;
            }
        }
    }
}

Graphen sind noch allgemeiner und bestehen aus Knoten (Vertices) und Kanten (Edges). Sie können gerichtet oder ungerichtet sein.

class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }
    
    addVertex(vertex) {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }
    
    addEdge(v1, v2) {
        this.adjacencyList.get(v1).push(v2);
        this.adjacencyList.get(v2).push(v1); // Für ungerichtete Graphen
    }
}

Fortgeschrittene Datenstrukturen in modernem JavaScript

Typed Arrays und ArrayBuffer

Für Arbeiten mit binären Daten bietet JavaScript Typed Arrays wie Int8Array, Uint32Array oder Float64Array. Diese ermöglichen die Arbeit mit rohen Binärdaten und sind besonders für Performance-kritische Anwendungen wie WebGL oder Audioverarbeitung relevant.

// Erstellt einen Buffer für 16 Bytes (4 32-bit Integers)
const buffer = new ArrayBuffer(16);

// Erstellt eine "View" auf den Buffer als 32-bit Integers
const int32View = new Int32Array(buffer);

// Daten setzen
int32View[0] = 42;
int32View[1] = 1337;

console.log(int32View.length); // 4 (16 Bytes / 4 Bytes pro Element)

WeakMap und WeakSet

WeakMap und WeakSet sind spezielle Varianten von Map und Set, die „schwache“ Referenzen zu ihren Schlüsseln halten. Das bedeutet, dass wenn ein Objekt nur als Schlüssel in einer WeakMap existiert, es vom Garbage Collector entfernt werden kann.

let obj = { id: 1 };
const weakMap = new WeakMap();

weakMap.set(obj, 'geheimer Wert');

console.log(weakMap.get(obj)); // 'geheimer Wert'

obj = null; // Jetzt kann das Objekt vom Garbage Collector entfernt werden

Diese Strukturen sind nützlich für Metadaten-Zuordnung ohne Speicherlecks zu verursachen.

Performance-Aspekte und Zeitkomplexität

Das Verständnis der Zeitkomplexität (Big-O-Notation) ist entscheidend für die Auswahl der richtigen Datenstruktur:
—- Arrays:
• Zugriff per Index: O(1)
• Suche: O(n)
• Einfügen/Löschen am Ende: O(1)
• Einfügen/Löschen am Anfang oder Mitte: O(n)
Objekte (Hash Maps):
• Einfügen/Zugriff/Löschen: O(1) im Durchschnitt
• Schlüsseliteration: O(n)
—- Sets/Maps:
• Wertüberprüfung (has/get): O(1)
• Einfügen/Löschen: O(1)
—- Verkettete Listen:
• Einfügen/Löschen am Anfang/Ende: O(1)
• Zugriff/Suche: O(n)

Praxisbeispiel: Wann welche Datenstruktur verwenden?

• Szenario 1: Sie entwickeln eine E-Commerce-Anwendung und müssen Produktkategorien mit Unterkategorien darstellen.

// Baumstruktur ist ideal
const categories = {
    name: 'Elektronik',
    children: [
        {
            name: 'Computer',
            children: [
                { name: 'Laptops' },
                { name: 'Desktops' }
            ]
        },
        {
            name: 'Smartphones'
        }
    ]
};

• Szenario 2: Sie implementieren einen Cache-Mechanismus mit begrenzter Größe und LRU (Least Recently Used) Entfernungsstrategie.

// Kombination aus Map
// (für schnellen Zugriff) und verlinkter Liste (für Reihenfolge)
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) return null;
        
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // Entfernt den ältesten Eintrag
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }
        this.cache.set(key, value);
    }
}

Vielseitig

Datenstrukturen in JavaScript sind vielseitig und haben sich von einfachen Arrays und Objekten zu einem reichhaltigen Ökosystem entwickelt. Die Wahl der richtigen Struktur hängt von den spezifischen Anforderungen Ihrer Anwendung ab – ob es um schnellen Zugriff, effiziente Modifikation oder spezielle Organisationsformen geht. Moderne JavaScript-Engines optimieren diese Strukturen hochgradig, aber ein grundlegendes Verständnis ihrer Eigenschaften und Kompromisse ist unerlässlich für die Entwicklung performanter und wartbarer Anwendungen.

Durch die Kombination der grundlegenden mit den spezialisierten Datenstrukturen können JavaScript-Entwickler heute komplexe Algorithmen und Systeme implementieren, die mit klassischen Compiler-Sprachen vergleichbar sind.

Dieses Dokument teilen

Datenstrukturen

Oder Link kopieren

INHALT

Abonnieren

×
Cancel