Informatik · Klasse 11 · Algorithmen und Komplexität · 2. Halbjahr

Datenstrukturen: Arrays und Listen

Die Schülerinnen und Schüler lernen grundlegende Datenstrukturen und deren Anwendung kennen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Strukturieren
• KMK: Sekundarstufe II - Implementieren

Über dieses Thema

Arrays und Listen bilden die Grundlage für effiziente Datenspeicherung in Programmen. Schülerinnen und Schüler in Klasse 11 lernen, dass Arrays eine feste Größe haben und direkten Indexzugriff in konstanter Zeit O(1) ermöglichen, was sie ideal für sequentielle Verarbeitung macht. Dynamische Listen, wie einfach verknüpfte Listen, erlauben flexibles Einfügen und Löschen in O(1) an der Spitze, kosten aber mehr Speicher durch Zeiger. Der Vergleich der Vor- und Nachteile schärft das Bewusstsein für Trade-offs in der Wahl der Struktur.

Im Kontext von Algorithmen und Komplexität analysieren Schüler, wann die Datenstruktur die Laufzeit maßgeblich beeinflusst, etwa bei Sortierungen oder Suchalgorithmen. Sie implementieren Operationen wie push_back, insert oder remove und berechnen Big-O-Notationen. Diese Inhalte entsprechen den KMK-Standards zum Strukturieren und Implementieren in der Sekundarstufe II und bereiten auf fortgeschrittene Themen wie Bäume vor.

Aktives Lernen eignet sich hervorragend, weil abstrakte Komplexitäten durch praktische Codings und Messungen greifbar werden. Schüler programmieren reale Szenarien, vergleichen Laufzeiten und diskutieren in Gruppen, was Verständnis festigt und Motivation steigert.

Leitfragen

1. Vergleichen Sie die Vor- und Nachteile von Arrays und dynamischen Listen für die Datenspeicherung.
2. Analysieren Sie, wann die Wahl der richtigen Datenstruktur die Effizienz eines Algorithmus maßgeblich beeinflusst.
3. Erklären Sie, wie man Elemente in einem Array oder einer Liste effizient hinzufügt oder entfernt.

Lernziele

• Vergleichen Sie die Zugriffszeiten auf Elemente in Arrays und dynamischen Listen für Einfüge-, Lösch- und Leseoperationen.
• Analysieren Sie die Speicheranforderungen von Arrays im Vergleich zu dynamischen Listen, einschließlich des Overheads für Zeiger.
• Erklären Sie anhand von Pseudocode, wie Elemente an verschiedenen Positionen in einem Array und einer einfach verketteten Liste eingefügt und entfernt werden.
• Bewerten Sie die Eignung von Arrays und dynamischen Listen für spezifische Anwendungsfälle, wie z.B. die Speicherung von Sensordaten oder die Verwaltung einer Warteschlange.
• Berechnen Sie die Big-O-Notation für grundlegende Operationen auf Arrays und dynamischen Listen.

Bevor es losgeht

Grundlagen der Programmierung: Variablen und Datentypen

Warum: Schüler müssen Variablen und grundlegende Datentypen wie ganze Zahlen und Zeichenketten verstehen, um sie in Datenstrukturen speichern zu können.

Kontrollstrukturen: Schleifen und Bedingungen

Warum: Schleifen sind notwendig, um über Elemente von Arrays und Listen zu iterieren, und Bedingungen sind wichtig für die Logik von Einfüge- und Löschoperationen.

Schlüsselvokabular

Array	Eine Datenstruktur, die eine feste Anzahl von Elementen desselben Datentyps speichert. Der Zugriff erfolgt über einen Index, was eine konstante Zeitkomplexität O(1) ermöglicht.
Dynamische Liste (verkettete Liste)	Eine Datenstruktur, deren Größe zur Laufzeit geändert werden kann. Elemente sind oft über Zeiger miteinander verbunden, was flexible Einfüge- und Löschoperationen ermöglicht.
Index	Eine numerische Kennung, die die Position eines Elements innerhalb einer Datenstruktur wie einem Array angibt. Indizes beginnen üblicherweise bei 0.
Zeiger (Pointer)	Eine Variable, die die Speicheradresse einer anderen Variablen speichert. In verketteten Listen werden Zeiger verwendet, um von einem Element zum nächsten zu navigieren.
Zeitkomplexität (Big-O-Notation)	Eine mathematische Notation, die beschreibt, wie sich die Laufzeit oder der Speicherbedarf eines Algorithmus mit zunehmender Eingabegröße ändert.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Arrays sind immer schneller als Listen.

Was Sie stattdessen lehren sollten

Arrays bieten schnellen Zugriff, aber Einfügen am Anfang kostet O(n) durch Verschieben. Listen sind hier effizienter. Aktive Vergleichsprogramme lassen Schüler Laufzeiten messen und Trade-offs selbst entdecken.

Häufige Fehlvorstellung

Dynamische Listen brauchen keinen zusätzlichen Speicher.

Was Sie stattdessen lehren sollten

Jeder Knoten speichert Daten und Zeiger, was mehr Overhead erzeugt. Peer-Diskussionen nach Codings helfen, Speicherverbrauch zu visualisieren und reale Einschränkungen zu verstehen.

Häufige Fehlvorstellung

Die Größe eines Arrays kann jederzeit geändert werden.

Was Sie stattdessen lehren sollten

Feste Arrays erfordern Neuzuweisung für Wachstum, was teuer ist. Praktische Resizing-Übungen zeigen den Aufwand und fördern den Wechsel zu Vektoren oder Listen.

Ideen für aktives Lernen

Pair Programming: Array- und Listen-Implementierung

Paare implementieren eine dynamische Liste einmal mit festem Array und einmal mit verknüpfter Liste in Python oder Java. Sie testen 1000 Einfügungen und Löschen und protokollieren die Zeiten. Abschließend vergleichen sie die Ergebnisse.

35 Min.·Partnerarbeit

Stationenrotation: Operationen vergleichen

Richten Sie vier Stationen ein: Array-Zugriff, Listen-Suche, Einfügen in Array, Einfügen in Liste. Gruppen rotieren alle 10 Minuten, führen Tests durch und notieren Vor- und Nachteile. Plenum diskutiert die Beobachtungen.

45 Min.·Kleingruppen

Ganzer Unterricht: Performance-Challenge

Die Klasse wählt ein Szenario wie eine Warteschlange und implementiert es mit Array und Liste. Jede Gruppe misst Laufzeiten für große Datensätze und präsentiert die effizientere Variante mit Begründung.

50 Min.·Ganze Klasse

Individuell: Big-O-Übungen

Schüler listen Operationen für Arrays und Listen auf, weisen Komplexitäten zu und coden Beispiele. Sie tauschen mit einem Partner und korrigieren gegenseitig.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Softwareentwickler, die an Betriebssystemen arbeiten, nutzen Arrays für die Verwaltung von Prozess-IDs oder Speicherblöcken, wo schnelle direkte Zugriffe entscheidend sind. Dynamische Listen kommen zum Einsatz, wenn die Anzahl der Prozesse oder Speichersegmente stark variiert.
• Datenbankmanagementsysteme verwenden interne Listenstrukturen, um Datensätze zu verwalten und effiziente Such- und Sortieroperationen zu ermöglichen. Die Wahl der Datenstruktur beeinflusst direkt die Abfragegeschwindigkeit.
• Entwickler von Echtzeitsystemen, z.B. in der Automobilindustrie für Airbag-Steuerungen, müssen Datenstrukturen wählen, die garantierte Reaktionszeiten bieten. Arrays könnten hier für feste Puffergrößen genutzt werden, während Listen für dynamische Ereigniswarteschlangen in Frage kommen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie jedem Schüler ein Kärtchen mit einem Szenario (z.B. 'Speicherung von 1000 Sensormesswerten', 'Verwaltung einer dynamischen Warteschlange von Benutzern'). Die Schüler schreiben auf das Kärtchen, welche Datenstruktur (Array oder dynamische Liste) sie wählen würden und begründen dies kurz mit Bezug auf Effizienz oder Flexibilität.

Kurze Überprüfung

Stellen Sie eine kurze Programmieraufgabe: 'Schreiben Sie eine Funktion, die ein Element an Position 5 in einem Array mit 10 Elementen löscht.' Die Schüler zeigen ihren Code oder beschreiben die Schritte. Überprüfen Sie, ob sie die Auswirkungen auf nachfolgende Elemente verstehen.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwickeln ein Spiel, das eine Highscore-Liste verwaltet. Welche Datenstruktur würden Sie verwenden, wenn die Liste maximal 10 Einträge hat? Was ändert sich, wenn die Liste beliebig lang werden kann?'

Häufig gestellte Fragen

Was sind Vor- und Nachteile von Arrays und Listen?

Arrays gewährleisten konstanten Zugriff O(1) und kompakte Speicherung, eignen sich für bekannte Größen, erfordern aber Verschieben bei Einfügungen O(n). Listen erlauben effizientes Einfügen/Löschen O(1) an Knoten, kosten mehr Speicher und haben langsamere Suche O(n). Der Vergleich klärt Einsatzszenarien wie Stapel (Array) oder Warteschlangen (Liste). Praktische Tests festigen das Wissen.

Wie wirkt sich die Datenstruktur auf Algorithmuseffizienz aus?

Falsche Strukturen erhöhen Komplexität, z.B. Suche in Liste O(n) statt Array O(1). Schüler lernen durch Analyse, Arrays für Random Access und Listen für dynamische Änderungen zu wählen. Beispiele wie Bubble Sort auf Arrays versus Insertion Sort auf Listen zeigen messbare Unterschiede in der Laufzeit.

Wie fügt man Elemente in Array oder Liste effizient hinzu?

In Arrays: Am Ende in O(1), sonst Verschieben O(n); Resizing verdoppelt Kapazität. In Listen: An Kopf/Schwanz O(1) mit Zeigeranpassung. Implementierungen in Code mit Timing demonstrieren Effizienz und helfen, Big-O zu verinnerlichen.

Wie fördert aktives Lernen das Verständnis von Arrays und Listen?

Durch Pair Programming und Performance-Messungen erleben Schüler abstrakte Konzepte konkret: Sie coden, timen Operationen mit großen Datensätzen und diskutieren Ergebnisse. Stationenrotationen bauen Kompetenzen schrittweise auf, Fehlvorstellungen werden in Gruppen korrigiert. Diese Methoden steigern Retention und Problemlösungsfähigkeiten nachhaltig.