Einführung in Datenstrukturen

Einführung

Ohne geeignete Datenstrukturen laufen Programme schnell ineffizient, belegen unnötig viel Speicher und reagieren träge. Schon kleine Entscheidungen bei der Organisation von Daten können über den Erfolg oder Misserfolg einer Anwendung bestimmen.

Chaos ohne vs. Struktur mit Datenstrukturen — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Damit du Software nicht nur funktionsfähig, sondern auch leistungsstark entwickeln kannst, lernst du in dieser Einheit die grundlegenden Datenstrukturen kennen. Sie sind das Fundament für effizientes Arbeiten mit Informationen und bilden die Basis für komplexere Konzepte in der Informatik.

Lernziele

Nach dieser Lerneinheit kannst du:

• Datenstrukturen definieren und ihre Bedeutung für effiziente Softwareentwicklung erklären.
• Arrays beschreiben, ihre Eigenschaften erläutern und entscheiden, wann sie sinnvoll oder ungeeignet sind.
• Listen erklären, ihre Funktionsweise darstellen und Anwendungsfälle von Arrays abgrenzen.
• Stacks verstehen, das LIFO-Prinzip anwenden und typische Einsatzszenarien benennen.
• Queues verstehen, das FIFO-Prinzip anwenden und reale Beispiele dafür identifizieren.
• Die Unterschiede zwischen den vier grundlegenden Strukturen systematisch vergleichen und eine geeignete Struktur für ein Problem auswählen.

Was sind Datenstrukturen?

Stell dir vor, du baust ein Haus. Bevor du Wände hochziehst, brauchst du einen Bauplan. In der Softwareentwicklung sind Datenstrukturen die Baupläne für die Organisation von Informationen in einem Computer. Sie legen fest, wie Daten gespeichert, angeordnet und wie auf sie zugegriffen wird.

Warum ist das so wichtig? Die Wahl der richtigen Datenstruktur ist entscheidend für die Effizienz deiner Software. Ein Programm, das die falschen Strukturen verwendet, ist wie ein Lagerhaus ohne Regalsystem: chaotisch, langsam und schwer zu verwalten.

Der praktische Nutzen ist:

• ✔ Schnellerer Zugriff: Daten werden schneller gefunden und abgerufen.
• ✔ Weniger Speicherplatz: Der Arbeitsspeicher des Computers wird optimal genutzt.
• ✔ Bessere Performance: Das gesamte Programm läuft flüssiger und reagiert schneller.
• ✔ Einfachere Wartung: Der Programmcode ist logischer, verständlicher und leichter zu erweitern.

Das Array

Ein Array ist die grundlegendste Datenstruktur. Stell es dir wie eine Reihe fest montierter, nummerierter Schließfächer vor. Technisch gesehen ist es ein zusammenhängender Block im Arbeitsspeicher des Computers. Das ist der Grund für seine wichtigsten Eigenschaften:

• Feste Position (Index): Jedes Fach hat eine eindeutige Nummer, den Index. Wichtig: Die Zählung beginnt fast immer bei 0! Das erste Element hat also den Index 0, das zweite den Index 1.
• Feste Größe: Da der Speicherblock am Stück reserviert wird, steht die Größe eines Arrays bei seiner Erstellung fest.
• Direkter Zugriff: Weil der Computer die Startadresse des Speicherblocks und die (immer gleiche) Größe jedes Elements kennt, kann er die Position jedes Elements sofort berechnen und direkt darauf zugreifen.

Wann solltest du Arrays verwenden?

• ✔ Wenn die Anzahl der Elemente von Anfang an bekannt und unveränderlich ist (z.B. die 12 Monate im Jahr, die 7 Wochentage).
• ✔ Wenn du sehr oft und schnell auf beliebige Elemente zugreifen musst.

Wann sind Arrays ungeeignet?

• ✘ Wenn du oft Elemente in der Mitte einfügen oder löschen musst.
• ✘ Wenn du vorher nicht weißt, wie viele Elemente du speichern musst.

Arrays: Code-Beispiel (Java)

In Java musst du den Datentyp des Arrays (z.B. String[] (String Array) für eine Reihe von Texten) bei der Erstellung festlegen. Der Zugriff erfolgt dann über die eckigen Klammern [].

// Ein Array für die Wochentage (feste Anzahl)
String[] wochentage = {"Montag", "Dienstag", "Mittwoch", "Donnerstag", "Freitag"};
 
// Direkter Zugriff auf das dritte Element.
// Da die Zählung bei 0 beginnt, hat es den Index 2.
System.out.println(wochentage[2]); // Gibt "Mittwoch" aus

Dieser Code erstellt zuerst eine feste Liste (ein Array) von Zeichenketten namens wochentage.

Anschließend wird auf das Element an der dritten Position zugegriffen. Da die Zählung in der Programmierung bei 0 beginnt, hat das dritte Element den Index 2. Der Wert dieses Elements (“Mittwoch”) wird dann auf der Konsole ausgegeben.

Die Liste

Eine Liste (oft als “verkettete Liste / Linked List” implementiert) ist deutlich flexibler als ein Array. Stell sie dir wie eine Perlenkette vor, bei der jede Perle nicht nur den Schmuckstein (den Wert), sondern auch einen Faden zum Nachfolger enthält. Dieser “Faden” ist ein Verweis (oder Zeiger) auf den Speicherort des nächsten Elements.

• Flexible Verknüpfungen: Die Elemente können irgendwo im Arbeitsspeicher verstreut liegen. Der Zusammenhalt entsteht nur durch die Verweise von einem Element zum nächsten.
• Flexible Größe: Die Kette kann beliebig verlängert oder verkürzt werden.
• Langsamer sequenzieller Zugriff: Um zum gewünschten Element zu gelangen, muss der Computer beim ersten Element starten und sich entlang des “Fadens” von Element zu Element hangeln.

Array vs. LinkedList im Vergleich — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Wann solltest du Listen verwenden?

• ✔ Wenn sich die Anzahl der Elemente häufig ändert.
• ✔ Wenn du oft Elemente hinzufügen oder entfernen musst.

Wann sind Listen ungeeignet?

• ✘ Wenn du oft direkt auf Elemente in der Mitte zugreifen musst.

Unterschied LinkedList vs. ArrayList

Nachdem du nun weißt, wie eine Liste grundsätzlich aufgebaut ist, lohnt sich ein Blick auf die beiden häufigsten Implementierungen in Java: ArrayList und LinkedList. Beide gehören zum Java Collection Framework und erfüllen das gleiche Ziel – sie speichern Elemente in einer bestimmten Reihenfolge – unterscheiden sich aber darin, wie sie das tun und wo ihre Stärken liegen.

Aspekt	ArrayList (dynamisches Array)	LinkedList (verkettete Liste)
Speicherlayout	Elemente liegen zusammenhängend	Elemente sind über Knoten miteinander verknüpft
Direktzugriff	Sehr schneller Indexzugriff	Zugriff erfolgt durch Durchlaufen der Liste
Einfügen/Entfernen	In der Mitte oder am Anfang werden Elemente verschoben	Elemente werden über Verweise verbunden oder gelöst
Wachstum	Vergrößert das interne Array bei Bedarf automatisch	Wächst und schrumpft flexibel über neue Knoten
Speicherbedarf	Kompakt (nur Werte)	Etwas höher durch zusätzliche Verweise
API-Besonderheiten	Standard-List-Methoden	Zusätzliche Deque-Methoden (addFirst, addLast, …)
Typische Nutzung	Viele Lesezugriffe, stabile Größe	Viele Änderungen am Anfang oder Ende

Merke: Wenn du viele Lesezugriffe oder Zugriffe über den Index brauchst, ist die ArrayList meist die bessere Wahl. Wenn du dagegen häufig Elemente am Anfang oder Ende einfügst oder entfernst, bietet sich die LinkedList an – sie bleibt dabei flexibler und spart sich das Verschieben bestehender Elemente.

LinkedList: Code-Beispiel (Java)

In Java kannst du eine LinkedList verwenden, um Elemente flexibel zu speichern. Sie gehört wie die ArrayList zum Java Collection Framework, speichert die Daten aber nicht zusammenhängend im Speicher, sondern als verkettete Knoten.

Dadurch kannst du Elemente besonders effizient am Anfang oder Ende der Liste einfügen oder entfernen, ohne dass bestehende Elemente verschoben werden müssen.

import java.util.List;
import java.util.LinkedList;

public class LinkedListBeispiel {
    public static void main(String[] args) {
        // Eine Liste, die intern als verkettete Liste arbeitet
        List<String> namen = new LinkedList<>();

        // Elemente hinzufügen (am Ende)
        namen.add("Zara");   // ["Zara"]
        namen.add("Boris");  // ["Zara", "Boris"]
        System.out.println(namen); // -> [Zara, Boris]

        // Einfügen am Anfang (Position 0) – bei LinkedList ohne Verschieben eines Arrays
        namen.add(0, "Anna");      // ["Anna", "Zara", "Boris"]
        System.out.println(namen); // -> [Anna, Zara, Boris]

        // Entfernen am Anfang (Position 0)
        namen.remove(0);           // ["Zara", "Boris"]
        System.out.println(namen); // -> [Zara, Boris]
    }
}

Dieser Code erstellt eine LinkedList vom Typ String, fügt Elemente hinzu, fügt eines am Anfang ein und entfernt anschließend wieder das erste. Im Unterschied zur ArrayList verschiebt die LinkedList beim Einfügen oder Entfernen keine anderen Elemente, sondern passt nur ihre internen Verweise an. Dadurch sind Operationen am Kopf oder Ende der Liste sehr schnell, während Zugriffe über den Index länger dauern, da die Liste dafür durchlaufen werden muss.

ArrayListe: Code-Beispiel (Java)

In Java verwendet man oft eine ArrayList, eine verbreitete Implementierung einer Liste. Sie ist Teil des Java Collection Frameworks. Man deklariert eine Liste für einen bestimmten Datentyp (z.B. List<String>). Mit .add() fügt man Elemente hinzu und mit .remove() entfernt man sie.

import java.util.ArrayList;
import java.util.List;
 
// Eine Liste für eine To-Do-Liste, die leer startet
List<String> todoListe = new ArrayList<>();
 
// Aufgaben werden hinzugefügt, die Liste wächst
todoListe.add("E-Mails beantworten"); // ["E-Mails beantworten"]
todoListe.add("Meeting vorbereiten"); // ["E-Mails beantworten", "Meeting vorbereiten"]
 
// Die erste Aufgabe (am Index 0) wird als erledigt entfernt
todoListe.remove(0); // ["Meeting vorbereiten"]
 
System.out.println(todoListe); // Gibt "[Meeting vorbereiten]" aus

Dieser Code erstellt eine flexible Liste (eine ArrayList) namens todoListe, deren Größe sich ändern kann.

Zuerst werden mit der Methode .add() zwei Aufgaben hinzugefügt, wodurch die Liste wächst. Anschließend wird mit .remove(0) die erste Aufgabe (am Index 0) wieder gelöscht. Der System.out.println() Befehl gibt den finalen Inhalt der Liste auf der Konsole aus, die nach dem Löschen nur noch das zweite Element enthält.

⏳ Lädt Dataview-Inhalt...

Der Stack

Ein Stack ist eine spezialisierte Struktur, die streng nach dem Prinzip Last-In, First-Out (LIFO) funktioniert. Das Element, das zuletzt hinzugefügt wurde, wird als erstes wieder entfernt.

Jedes Mal, wenn dein Programm eine Funktion aufruft, wird diese auf einen internen “Call Stack” gelegt. Ist die Funktion fertig, wird sie wieder vom Stack genommen. Du nutzt dieses Prinzip also ständig, ohne es direkt zu sehen!

Typische Anwendungsfälle:

• ✔ Die “Rückgängig”-Funktion in einem Programm: Der letzte Arbeitsschritt (push) wird als erster wieder rückgängig gemacht (pop).
• ✔ Der “Zurück”-Button im Browser: Jede besuchte Seite wird auf den Verlaufs-Stack gelegt.

Stack: Code-Beispiel (Java)

Java stellt eine eigene Stack-Klasse zur Verfügung, die genau nach diesem Prinzip arbeitet. Die Methoden heißen passenderweise .push() (drauflegen) und .pop() (wegnehmen).

import java.util.Stack;
 
Stack<String> browserVerlauf = new Stack<>();
 
// Benutzer besucht Seiten (push)
browserVerlauf.push("Startseite");
browserVerlauf.push("Produkte");
browserVerlauf.push("Kontakt"); // Stack: ["Startseite", "Produkte", "Kontakt"]
 
// Benutzer klickt "Zurück" (pop)
String letzteSeite = browserVerlauf.pop();
 
System.out.println(letzteSeite); // Gibt "Kontakt" aus
System.out.println(browserVerlauf); // Gibt "[Startseite, Produkte]" aus

Dieser Code verwendet eine Datenstruktur namens Stack (Stapel), die nach dem “Last-In, First-Out”-Prinzip funktioniert.

Zuerst werden mit .push() drei Webseiten auf den Stapel browserVerlauf gelegt. Danach holt .pop() das oberste Element (“Kontakt”) vom Stapel herunter und speichert es. Ausgegeben wird zuerst das entfernte Element und danach der Rest des Stapels.

Die Queue

Eine Queue funktioniert genau wie eine Warteschlange an der Supermarktkasse und folgt dem Prinzip: First-In, First-Out (FIFO). Wer zuerst kommt, mahlt zuerst. Das Element, das zuerst hinzugefügt wurde, wird auch als erstes wieder entfernt.

Queues sind das Herzstück vieler asynchroner Systeme. Sie agieren als Puffer, um z.B. Anfragen an einen Server fair zu managen oder rechenintensive Aufgaben nacheinander abzuarbeiten, ohne das Hauptprogramm zu blockieren.

Typische Anwendungsfälle:

• ✔ Eine Drucker-Warteschlange: Dokumente werden in der Reihenfolge gedruckt, in der sie an den Drucker gesendet wurden.
• ✔ Aufgabenverteilung: Eingehende Aufgaben werden in eine Queue gelegt und von verfügbaren Bearbeitern (“Workern”) der Reihe nach abgeholt.

Die Queue: Code-Beispiel (Java)

In Java ist Queue ein Interface. Eine häufige Implementierung dafür ist die LinkedList. Man fügt Elemente mit .add() hinzu und entnimmt das vorderste Element mit .poll().

import java.util.LinkedList;
import java.util.Queue;
 
Queue<String> druckerWarteschlange = new LinkedList<>();
 
// Druckaufträge gehen ein (enqueue)
druckerWarteschlange.add("Dokument1.pdf");
druckerWarteschlange.add("Foto.jpg"); // Queue: ["Dokument1.pdf", "Foto.jpg"]
 
// Der Drucker holt sich den ersten Job in der Schlange (dequeue)
String aktuellerDruck = druckerWarteschlange.poll();
 
System.out.println(aktuellerDruck); // Gibt "Dokument1.pdf" aus
System.out.println(druckerWarteschlange); // Gibt "[Foto.jpg]" aus

Dieser Code bildet eine Warteschlange (eine Queue) ab, die nach dem “First-In, First-Out”-Prinzip arbeitet.

Zuerst werden mit .add() zwei Druckaufträge an das Ende der Schlange druckerWarteschlange gestellt. Danach holt .poll() den ersten Auftrag (“Dokument1.pdf”) aus der Schlange, um ihn zu “drucken”. Ausgegeben werden der entnommene Auftrag und danach der verbleibende Rest der Warteschlange.

Stack und Queue im Überblick

Stack und Queue sind zwei spezialisierte Datenstrukturen, die sich durch ihre Zugriffsreihenfolge unterscheiden. Während der Stack nach dem LIFO-Prinzip arbeitet (zuletzt rein, zuerst raus), folgt die Queue dem FIFO-Prinzip (zuerst rein, zuerst raus).

Stack (LIFO) vs. Queue (FIFO) im Vergleich — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Denke immer an die Eselsbrücke: Ein Stack ist wie ein Bücherstapel, bei dem du nur das oberste Buch nehmen kannst. Eine Queue ist wie eine Warteschlange, in der der Erste auch als Erster bedient wird.

Die richtige Wahl

Du hast die vier wichtigsten Datenstrukturen kennengelernt. Im Berufsalltag geht es darum, für ein gegebenes Problem schnell das richtige Werkzeug auszuwählen.

Merke dir diese vier einfachen Regeln als Entscheidungshilfe:

1. Feste Größe & schneller, beliebiger Zugriff? → Array
2. Flexible Größe & häufige Änderungen? → Liste
3. Rückgängig-Logik (zuletzt rein, zuerst raus)? → Stack
4. Faire Reihenfolge (zuerst rein, zuerst raus)? → Queue

⏳ Lädt Dataview-Inhalt...

Zusammenfassung

Zusammenfassung:

Übersicht der vier grundlegenden Datenstrukturen — Bildrechte: Ausbildung-in-der-IT.de (KI-unterstützt)

Grundidee von Datenstrukturen

Datenstrukturen bestimmen, wie Daten gespeichert, angeordnet und verarbeitet werden. Sie verbessern Geschwindigkeit, Speicherverwaltung und Lesbarkeit von Programmen.

• Organisation von Daten im Speicher
• Effizienter Zugriff auf Informationen
• Reduzierung von Speicherbedarf
• Erleichterte Wartung und Erweiterbarkeit

Arrays

Arrays sind lineare Strukturen mit fester Größe und direktem Zugriff über Indizes.

• Elemente liegen in einem zusammenhängenden Speicherblock
• Größe ist fix und bei Erstellung festgelegt
• Direkter Zugriff über Index möglich
• Geeignet bei fester Elementanzahl und häufigem Zugriff
• Ungeeignet bei häufigem Einfügen oder Löschen

Listen

Listen sind flexible Strukturen, die dynamisch wachsen oder schrumpfen können.

• Elemente sind über Referenzen verknüpft
• Variable Länge, beliebig erweiterbar oder kürzbar
• Zugriff langsamer, da sequenziell
• Geeignet bei häufigen Änderungen der Elementanzahl
• Ungeeignet für häufigen Direktzugriff

Stacks

Stacks arbeiten nach dem Prinzip Last-In, First-Out (LIFO).

• Neues Element wird mit push() oben abgelegt
• Letztes Element wird mit pop() entfernt
• Typische Anwendungen: Funktionsaufrufe, Rückgängig-Operationen

Queues

Queues funktionieren nach dem Prinzip First-In, First-Out (FIFO).

• Neues Element wird hinten eingefügt
• Erstes Element wird vorne entfernt
• Typische Anwendungen: Druckerwarteschlangen, Serveranfragen

Übersicht der Strukturen

Die Wahl der Struktur richtet sich nach dem Einsatzzweck.

• Array → feste Größe, schneller Zugriff
• Liste → variable Größe, flexible Änderungen
• Stack → LIFO-Verwaltung
• Queue → FIFO-Verwaltung

Ausblick:

In der nächsten Lerneinheit lernst du mehrdimensionale Arrays kennen – Datenstrukturen, die es ermöglichen, Informationen in Tabellen-, Matrix- oder Rasterform zu speichern. Du erfährst, wie solche Arrays aufgebaut sind, wie du auf ihre Elemente zugreifst und welche typischen Einsatzbereiche sie in der Programmierung und Datenverarbeitung haben.

---