Informatik · Klasse 13 · Datenstrukturen und Algorithmen-Analyse · 1. Halbjahr

Lineare Datenstrukturen: Arrays und Listen

Die Schülerinnen und Schüler implementieren und vergleichen Arrays und verkettete Listen.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Daten und ihre Strukturierung
• KMK: Sekundarstufe II - Modellieren und Implementieren

Über dieses Thema

Lineare Datenstrukturen wie Arrays und verkettete Listen sind essenziell für die effiziente Speicherung und Manipulation von Daten in Algorithmen. Schülerinnen und Schüler der Klasse 13 implementieren beide Strukturen in einer Sprache wie Python oder Java, testen grundlegende Operationen wie Zugriff, Einfügen und Löschen und vergleichen ihre Eigenschaften. Arrays ermöglichen schnellen Indexzugriff in konstanter Zeit O(1), haben aber eine feste Größe und erfordern teure Verschiebungen bei dynamischen Änderungen. Verkettete Listen bieten Flexibilität durch dynamische Knoten, erlauben O(1)-Einfügungen an bekannten Positionen, kosten jedoch mehr Speicher und verlangamen den sequentiellen Zugriff.

Dieses Thema knüpft an die KMK-Standards für Datenstrukturierung und Modellieren an. Lernende analysieren Laufzeitkomplexitäten, z. B. O(n) für Array-Insertion versus O(1) für Listen-Insertion am Anfang, und designen Anwendungen wie Stapel oder Warteschlangen, die von Listen profitieren. Solche Vergleiche fördern algorithmisches Denken und helfen, passende Strukturen für reale Probleme auszuwählen.

Aktives Lernen ist hier besonders wirksam, weil Schüler durch Pair-Programming, Benchmark-Tests und Gruppendiskussionen die Trade-offs hautnah erleben. Sie messen tatsächliche Laufzeiten, debuggen Code und reflektieren Vor- und Nachteile, was abstrakte Big-O-Notationen konkretisiert und langfristiges Verständnis schafft.

Leitfragen

1. Vergleichen Sie die Vor- und Nachteile von Arrays und verketteten Listen.
2. Designen Sie eine Anwendung, die von einer verketteten Liste profitiert.
3. Analysieren Sie die Laufzeitkomplexität grundlegender Operationen auf diesen Strukturen.

Lernziele

• Analysieren Sie die Laufzeitkomplexität von Einfüge-, Lösch- und Zugriffsoperationen für Arrays und verkettete Listen.
• Vergleichen Sie die Speicheranforderungen von Arrays und verketteten Listen unter Berücksichtigung von Overhead und Flexibilität.
• Entwerfen Sie eine einfache Anwendung, z. B. einen Stapel, der die Vorteile einer verketteten Liste gegenüber einem Array nutzt.
• Implementieren Sie sowohl Arrays als auch verkettete Listen in einer Programmiersprache und demonstrieren Sie deren grundlegende Funktionalität.
• Bewerten Sie die Eignung von Arrays und verketteten Listen für spezifische Anwendungsfälle basierend auf ihren jeweiligen Vor- und Nachteilen.

Bevor es losgeht

Grundlagen der Programmierung: Variablen, Datentypen, Kontrollstrukturen

Warum: Schüler müssen grundlegende Programmierkonzepte beherrschen, um Datenstrukturen implementieren und manipulieren zu können.

Grundlagen der Algorithmenanalyse: Big-O-Notation

Warum: Das Verständnis von Big-O-Notation ist unerlässlich, um die Effizienz von Operationen auf Arrays und Listen zu analysieren und zu vergleichen.

Zeiger und Referenzen (falls in der Sprache verwendet)

Warum: Ein grundlegendes Verständnis von Zeigern oder Referenzen ist notwendig, um die Funktionsweise verketteter Listen zu begreifen.

Schlüsselvokabular

Array	Eine Datenstruktur, die eine feste Anzahl von Elementen desselben Typs speichert, die über einen Index direkt zugänglich sind.
Verkettete Liste	Eine lineare Datenstruktur, bei der Elemente (Knoten) über Zeiger miteinander verbunden sind, was dynamische Größenänderungen ermöglicht.
Knoten	Die grundlegende Einheit einer verketteten Liste, die Daten und einen Verweis (Zeiger) auf den nächsten Knoten enthält.
Laufzeitkomplexität	Eine Beschreibung, wie die Ausführungszeit eines Algorithmus mit der Größe der Eingabe wächst, oft ausgedrückt in Big-O-Notation.
Indexzugriff	Die Fähigkeit, direkt auf ein Element in einer Datenstruktur zuzugreifen, indem seine Position (sein Index) angegeben wird.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Arrays sind immer schneller als Listen.

Was Sie stattdessen lehren sollten

Arrays bieten O(1)-Zugriff, aber Insertionen kosten O(n) durch Verschiebungen, während Listen hier O(1) erreichen. Pair-Tests mit großen Datensätzen zeigen dies empirisch, Gruppendiskussionen korrigieren das Bild.

Häufige Fehlvorstellung

Verkettete Listen brauchen keinen zusätzlichen Speicher.

Was Sie stattdessen lehren sollten

Jeder Knoten speichert Zeiger, was 2-3-mal mehr Speicher als Arrays verbraucht. Benchmarking-Aktivitäten machen den Overhead messbar, Peer-Reviews helfen, Speichermodelle zu visualisieren.

Häufige Fehlvorstellung

Laufzeitkomplexität ist unabhängig von der Implementierung.

Was Sie stattdessen lehren sollten

Big-O beschreibt asymptotisches Verhalten, reale Laufzeiten hängen von Konstanten ab. Schüler messen und plotten in Gruppen, um Theorie und Praxis zu verbinden.

Ideen für aktives Lernen

Pair Programming: Implementierung vergleichen

Paare implementieren eine Liste mit Arrays und verketteten Listen, testen Operationen wie append und insert. Sie protokollieren Laufzeiten mit timeit. Abschließend vergleichen sie Ergebnisse in der Klasse.

45 Min.·Partnerarbeit

Gruppenbenchmark: Laufzeit messen

Gruppen coden Zugriffs-, Einfüge- und Löschoperationen für beide Strukturen mit wachsenden Datensätzen. Sie visualisieren Messungen in Diagrammen. Diskussion der Komplexitätskurven folgt.

50 Min.·Kleingruppen

Design Challenge: Anwendung entwickeln

Gruppen entwerfen und implementieren eine App wie eine Playlist, die von Listen profitiert. Sie präsentieren Vor-/Nachteile und testen mit Szenarien. Peer-Feedback rundet ab.

60 Min.·Kleingruppen

Whole Class: Komplexitäts-Tabelle

Klasse erstellt gemeinsam eine Tabelle mit Big-O für Operationen auf Arrays und Listen. Jede*r trägt ein Beispiel bei, Diskussion klärt Unterschiede.

30 Min.·Ganze Klasse

Bezüge zur Lebenswelt

• Betriebssysteme verwenden verkettete Listen, um Prozesswarteschlangen zu verwalten, bei denen die Reihenfolge der Ausführung und das schnelle Hinzufügen/Entfernen von Prozessen entscheidend sind. Dies ist wichtig für die effiziente Ressourcenzuweisung auf Servern in Rechenzentren.
• Datenbankmanagementsysteme nutzen Arrays für Tabellen mit fester Größe und feste Spalten, während verkettete Listen für dynamische Indexstrukturen oder zur Implementierung von Transaktionsprotokollen eingesetzt werden können, was die Leistung von Abfragen in großen Online-Shops beeinflusst.
• Compiler und Interpreter verwenden oft verkettete Listen zur Darstellung von Symboltabellen oder abstrakten Syntaxbäumen, was eine flexible Handhabung von Programmstrukturen während der Code-Analyse und -Generierung ermöglicht.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Stellen Sie den Lernenden zwei Code-Snippets vor: eines, das Elemente in ein Array einfügt, und eines, das Elemente am Anfang einer verketteten Liste einfügt. Bitten Sie sie, die geschätzte Laufzeitkomplexität für jede Operation zu identifizieren und zu begründen, warum sie unterschiedlich ist.

Diskussionsfrage

Leiten Sie eine Diskussion mit der Frage: 'Unter welchen Umständen würden Sie sich für ein Array entscheiden, obwohl eine verkettete Liste mehr Flexibilität bietet, und umgekehrt?' Sammeln Sie Beispiele für Anwendungsfälle, bei denen die Speicheroverhead- oder Zugriffsgeschwindigkeitsunterschiede eine Rolle spielen.

Lernstandskontrolle

Jeder Lernende erhält eine Karte mit einer der folgenden Operationen: 'Element an Position k in Array einfügen', 'Element am Anfang einer verketteten Liste einfügen', 'Element an Position k in verketteter Liste abrufen'. Sie sollen die Laufzeitkomplexität (z.B. O(1), O(n)) und eine kurze Begründung angeben.

Häufig gestellte Fragen

Was sind die Vor- und Nachteile von Arrays und verketteten Listen?

Arrays: fester Speicherplatz, O(1)-Zugriff, aber O(n)-Insertion durch Verschiebung. Verkettete Listen: dynamische Größe, O(1)-Insertion/Löschung an Knoten, aber O(n)-Zugriff und höherer Speicherverbrauch. Schüler vergleichen sie durch Implementierung und Tests, um passende Einsätze zu lernen. (62 Wörter)

Wie analysiert man die Laufzeitkomplexität dieser Strukturen?

Berechnen Sie Big-O für Operationen: Array-Zugriff O(1), Suche O(n); Listen-Insertion am Kopf O(1), Traversierung O(n). Nutzen Sie timeit für Messungen mit n=10 bis 10.000, plotten Sie Kurven. Das verdeutlicht asymptotisches Verhalten und Konstantenfaktoren. (68 Wörter)

Welche Anwendungen profitieren von verketteten Listen?

Listen eignen sich für dynamische Strukturen wie Queues, Stacks oder Undo-Funktionen in Editoren, wo häufige Insertionen/Löschungen vorkommen. Designen Sie z. B. eine Musik-Playlist mit Insert/Delete. Arrays passen besser für statische, indexbasierte Zugriffe wie Bildpixel. (64 Wörter)

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

Pair-Programming und Benchmarks lassen Schüler Operationen implementieren, messen und debuggen, was Trade-offs erlebbar macht. Gruppendesigns für reale Apps verbinden Theorie mit Praxis, Diskussionen klären Missverständnisse. Solche Methoden stärken algorithmisches Denken nachhaltig, da Lernende aktiv experimentieren. (72 Wörter)