Sommer Sitzung 02
| Thema | Stichworte | Material ___________________________ |
| Überblick | Grundlegende Datenstrukturen: Liste; Grundlagen Komplexität und O-Notation | Beispiele und Literatur: Home |
| Motivation | Arrays: feste Größe, fester Bereich im Speicher reserviert; Probleme? – wie Elemente dranhängen oder einfügen? – Umkopieren nötig; wir wollen: dynamische Datenstruktur, die z.B. wachsen kann |  |
| Listen | Idee: Verkettung unabhängiger Daten (im Ggs. zu Arrays als fester, konsekutiver Speicherbereich); einfachste Form: Paar aus Element und Rest/Next (head, tail); sehr elementares Prinzip, vgl. Lisp; low-level, ohne OOP in Java z.B. mit Arrays implementierbar (s. Code, simuliert Tupel/Record/Struct, zeigt Grundlage: unterschiedliche Speicherbereiche dynamisch verketten); mit Object, was ist das? – Referenztypen, d.h. alles unabhängige Elemente im Speicher: Liste, Knoten, Werte, durch Referenzen/Zeiger/Pointer verkettet |  |
| OOP | Wie als OOP-Lösung? – Klassen List und Node (s. Abb.): rekursive (d.h. selbstbezügliche), objektorientierte Datenstruktur |
 |
| Queue (Schlange) | Eine einfache Liste; Hinten anhängen/anstellen (und vorne raus); beschränkt (FIFO), s. Code (und Tests, stellen Verhalten sicher) | — |
| Stack (Stapel) | Eine noch einfachere Liste (nur Pointer auf first); Vorne/Oben anhängen/drauflegen (und vorne raus); beschränkt (LIFO), s. Code (und Tests, stellen Verhalten sicher); Wozu? – z.B. XML/HTML, Implementierung Rekursion, etc., vgl. Kellerautomat (Keller/Stack/Stapel) | — |
| Komplexität | Warum Zugriff einschränken? – wie lange dauert push, pop z.B. bei Stack mit 10, 100, 1000 Elementen? – immer gleich lang, deshalb Einfügen und Entfernen O(1), d.h. konstante Laufzeit (in Relation zur Problemgröße); Einfügen? – O(n); bei Arrays? – Einfügen erfordert umkopieren: O(n) bei n Elementen wenn Array voll ist; Zugriff schnell: O(1); Implementierung von Listen/dynamischen Datenstrukturen mit Pointern (wie besprochen) vs. Arrays; wann will man was? – Oft einfügen und entfernen: verkettete Listen, viel Lesen an beliebigen Positionen: Array-Liste; d.h. zum Optimieren von Software bei Algorithmus/Datenstruktur anfangen, erstmal viel wichtiger als Sprache oder Hardware, z.B. O(1) statt O(n) | — |
| Iterator | Gemeinsamkeit Queue und Stack? – 1. kapseln Einzelelemente (beide verwenden Node); 2. linear geordneter Zugriff; wie Gemeinsamkeit nutzen? – Iterator-Pattern für einheitlichen Zugriff unabhängig von Implementationsdetails (z.B. verkettete Knoten oder Arrays); Iterable statt eigenem List-Interface für Sprachsupport bei eigenen Klassen (for-Syntax), s. Code; List in Java mit beliebigem Einfügen und Entfernen |
 |
| Hausaufgabe | Einfügen und Löschen an beliebiger Stelle; Hausaufgaben Pflicht, vor nächster Sitzung, max. nächste Woche, Abgeben: NachnameVornameAufgabeX.java; zu empfehlen: Mo. Seminar, Code und Hausaufgabe ansehen, Di. Übung, Di., Mi. Aufgabe lösen, wenn nicht geschafft: Do. Tutorium; JUnit-Tests für eigene Erweiterungen | Sommer-Aufgabe-01 |