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

Dynamische Datenstrukturen: Listen

Die Schülerinnen und Schüler verwenden Listen zur flexiblen Speicherung von Daten im Gegensatz zu statischen Arrays.

• KMK Bildungsstandards
• KMK: STD.01
• KMK: STD.02

Über dieses Thema

Dynamische Datenstrukturen wie Listen erlauben die flexible Handhabung variabler Datenmengen, anders als statische Arrays mit fester Größe. Schülerinnen und Schüler in Klasse 10 verstehen, warum Arrays bei sich ändernden Daten unflexibel sind. Sie erforschen Zeiger und Referenzen, die Knoten im Speicher verknüpfen. Durch Programmierbeispiele lernen sie Operationen wie Einfügen und Löschen kennen, die bei Listen oft effizienter ablaufen als bei Arrays. Dies beantwortet zentrale Fragen zur Speicherverwaltung und Algorithmeneffizienz.

In der Einheit Algorithmen und Komplexität verknüpft das Thema Theorie mit Praxis, gemäß KMK-Standards STD.01 und STD.02. Schüler vergleichen Laufzeiten und Speicherverbrauch, was Big-O-Notation zugänglich macht. Solche Inhalte fördern algorithmisches Denken und Problemlösungsfähigkeiten, die in der Informatik zentral sind. Praktische Übungen zeigen reale Anwendungen in Softwareentwicklung.

Aktives Lernen passt ideal, weil abstrakte Konzepte wie Zeiger durch Simulationen und kollaboratives Programmieren konkret werden. Wenn Schüler Listen mit Alltagsobjekten nachstellen oder Code gemeinsam erweitern, erkennen sie Effizienzunterschiede selbst und festigen Verständnis nachhaltig.

Leitfragen

1. Warum sind Arrays unflexibel bei sich ändernden Datenmengen?
2. Wie funktionieren Zeiger und Referenzen im Speicher?
3. Vergleichen Sie die Effizienz von Listenoperationen (Einfügen, Löschen) mit denen von Arrays.

Lernziele

• Erklären Sie die Notwendigkeit dynamischer Datenstrukturen im Vergleich zu statischen Arrays bei sich ändernden Datengrößen.
• Analysieren Sie die Funktionsweise von Zeigern und Referenzen zur Speicherverwaltung in Listen.
• Vergleichen Sie die Effizienz von Einfüge- und Löschoperationen in verketteten Listen mit denen in Arrays unter Berücksichtigung von Laufzeit und Speicherbedarf.
• Demonstrieren Sie die Implementierung einer einfachen verketteten Liste in einer Programmiersprache Ihrer Wahl.
• Entwerfen Sie eine Lösung für ein Problem, das die Verwendung einer dynamischen Datenstruktur erfordert, wie z.B. eine Warteschlange oder ein Stapel.

Bevor es losgeht

Grundlagen von Variablen und Datentypen

Warum: Schüler müssen verstehen, was Variablen sind und wie verschiedene Datentypen gespeichert werden, um Zeiger und Referenzen nachvollziehen zu können.

Einführung in Arrays

Warum: Ein grundlegendes Verständnis von Arrays ist notwendig, um die Einschränkungen statischer Datenstrukturen zu verstehen und die Vorteile dynamischer Listen zu erkennen.

Grundlagen der Speicherverwaltung

Warum: Ein Basisverständnis, wie Programme Speicher nutzen, hilft den Schülern, die Konzepte von dynamischer Speicherzuweisung und Zeigern besser zu greifen.

Schlüsselvokabular

Verkettete Liste	Eine lineare Datenstruktur, bei der Elemente (Knoten) nicht zusammenhängend im Speicher liegen, sondern über Zeiger miteinander verbunden sind.
Knoten	Eine Einheit in einer verketteten Liste, die typischerweise sowohl die Daten als auch einen Zeiger auf den nächsten Knoten enthält.
Zeiger/Referenz	Eine Variable, die die Speicheradresse eines anderen Datenelements (z.B. eines Knotens) speichert und so Verbindungen zwischen Daten herstellt.
Dynamische Speicherzuweisung	Der Prozess, bei dem zur Laufzeit Speicher für Datenstrukturen angefordert und freigegeben wird, was deren Größe flexibel anpasst.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Listen sind immer langsamer als Arrays bei Zugriffen.

Was Sie stattdessen lehren sollten

Arrays bieten konstanten O(1)-Zugriff auf Indizes, Listen sequentiellen O(n). Aktive Vergleiche durch Benchmarking-Skripte helfen Schülern, Vor- und Nachteile situationsbezogen zu sehen und richtige Struktur zu wählen.

Häufige Fehlvorstellung

Zeiger sind magische Sprünge im Speicher ohne Regeln.

Was Sie stattdessen lehren sollten

Zeiger sind Adressen, die auf Speicherzellen verweisen, Referenzen Aliase. Pair-Programming mit Visualisierern wie Python Tutor zeigt Verknüpfungen, wodurch Schüler Nullzeiger-Fehler entdecken und vermeiden lernen.

Häufige Fehlvorstellung

Listen brauchen immer mehr Speicher als Arrays.

Was Sie stattdessen lehren sollten

Listen verbrauchen pro Element mehr durch Zeiger, aber wachsen dynamisch. Simulations mit Karten machen Overhead sichtbar, Gruppenexperimente quantifizieren und vergleichen realen Verbrauch.

Ideen für aktives Lernen

Pair Programming: Listen-Operationen

Paare implementieren in Python eine Liste und ein Array, fügen 100 Elemente ein und messen die Zeit. Sie vergleichen die Ergebnisse und optimieren den Listen-Code. Abschließende Diskussion teilt Erkenntnisse.

35 Min.·Partnerarbeit

Karten-Simulation: Dynamische Listen

Gruppen modellieren Listen mit Karten als Knoten und Pfeilen als Zeigern. Sie üben Einfügen vorne/hinten und Löschen, notieren Schritte. Jede Gruppe präsentiert eine Operation.

45 Min.·Kleingruppen

Debugging-Rallye: Zeiger-Fehler

Schüler erhalten fehlerhaften Code mit Listen und Zeigern, identifizieren Probleme in Runden. Sie korrigieren und testen schrittweise. Whole-Class-Debriefing klärt gängige Fehler.

40 Min.·Kleingruppen

Effizienz-Vergleich: Benchmarking

Individuell schreiben Schüler Skripte, die Insert/Delete in Array und Liste timen. Sie plotten Ergebnisse mit Matplotlib und interpretieren Graphen. Teilen in Plenum.

50 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Softwareentwickler, die an Betriebssystemen arbeiten, nutzen dynamische Listen für die Verwaltung von Prozessen oder Speicherbereichen, die sich ständig ändern können.
• Entwickler von Videospielen verwenden dynamische Listen, um z.B. die Objekte in einer Spielwelt zu verwalten, die zur Laufzeit erstellt oder zerstört werden, wie z.B. Gegner oder Items.
• Datenbankadministratoren setzen dynamische Strukturen für die Verwaltung von Datensätzen ein, die wachsen oder schrumpfen können, um eine effiziente Abfrage und Speicherung zu gewährleisten.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Stellen Sie den Schülern eine kurze Programmieraufgabe: 'Implementieren Sie eine Funktion, die ein Element am Ende einer gegebenen verketteten Liste einfügt.' Bewerten Sie die Korrektheit der Implementierung und die Verwendung von Zeigern.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwickeln eine Musik-Player-App. Welche Datenstruktur würden Sie für die Wiedergabeliste verwenden und warum? Vergleichen Sie die Vor- und Nachteile mit einem statischen Array.' Sammeln Sie Argumente für Listenoperationen wie Hinzufügen, Entfernen und Neuanordnen.

Lernstandskontrolle

Geben Sie jedem Schüler ein Blatt mit zwei Fragen: 1. 'Erklären Sie in eigenen Worten den Hauptunterschied zwischen einem Array und einer verketteten Liste bezüglich der Speicherverwaltung.' 2. 'Nennen Sie eine Situation, in der die Verwendung von Zeigern für die Effizienz entscheidend ist.'

Häufig gestellte Fragen

Warum sind Listen flexibler als Arrays?

Arrays haben feste Größe, was bei variablen Datenmengen Umkopieren erfordert und ineffizient ist. Listen wachsen schrumpfend durch Zeiger, Einfügen/Löschen kostet O(1) an Enden. Praktische Tests in Code zeigen diese Vorteile klar, fördern Wahl der passenden Struktur für Algorithmen.

Wie funktionieren Zeiger und Referenzen in Listen?

Zeiger speichern Speicheradressen von Folgeknoten, Referenzen sind indirekte Zugriffe. In Python sind Listen Referenzlisten. Visualisierungen und schrittweises Debugging machen den Ablauf greifbar, Schüler sehen, wie Daten dynamisch verknüpft werden, ohne Speicher zu vergeuden.

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

Aktive Methoden wie Pair-Programming und Karten-Simulationen machen abstrakte Zeiger konkret. Schüler experimentieren mit Operationen, messen Effizienz selbst und diskutieren Ergebnisse. Das reduziert Fehlvorstellungen, stärkt Retention und verbindet Theorie mit Praxis, wie KMK-Standards fordern. Kollaboratives Debugging vertieft Problemlösung.

Wie vergleiche ich Effizienz von Listen und Arrays?

Messen Sie Laufzeiten für Insert/Delete mit wachsenden Daten. Arrays sind bei random Access schnell, Listen bei dynamischen Änderungen. Benchmark-Skripte und Graphen visualisieren Big-O, Schüler interpretieren, wann welche Struktur optimal ist. Das trainiert Komplexitätsdenken für reale Algorithmen.