Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- listen:verkettet:start [2024/09/18 08:01] – Martin Pabst
+++ listen:verkettet:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Warteschlange ======
-<WRAP center round info 60%>
-Eine **Warteschlange** ist eine Liste, bei der Elemente **am Ende der Liste hinzugefügt** und **am Anfang entnommen** werden können. Man spricht vom **FIFO**-Prinzip: //First in - first out!//
-\\ \\
-//Denken Sie an eine Supermarktkasse: Kunden stellen sich hinten an der Schlange an und gehen nach dem Kassiervorgang vorne wieder heraus.//
-</WRAP>
-====== Implementierung als einfach verkettete Liste - erster Ansatz ======
-<WRAP center round info 60%>
-Eine einfach verkettete Liste ist ein Ersatz für das Array um dessen Nachteile (Größenbeschränkung, Speicherplatzverschwendung und Aufwand beim Entnehmen) bei der Umsetzung der Warteschlange zu vermeiden. \\ \\
-Die Idee besteht darin, die Inhaltsobjekte hintereinanderzuhängen, indem jedes Inhaltselement ein Attribut ''nachfolger'' bekommt, das auf das jeweils nächste zeigt. Im Warteschlangen-Objekt wird dann nur noch die Referenz auf das erste Inhaltsobjekt gespeichert:
-{{ :listen:verkettet:objektdiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg |}}
-Beim letzten Inhaltsobjekt der Liste ist einfach ''nachfolger == null'' gesetzt.
-</WRAP>
-==== Als Java-Programm: ====
-<HTML>
-<div class="java-online" style="height: 70vh; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'warteschlange1'}">
-<script type="text/plain" title="Hauptprogramm.java">
-Supermarktkasse s = new Supermarktkasse();
-s.hintenAnstellen(new Kunde("Max"));
-s.hintenAnstellen(new Kunde("Tina"));
-s.hintenAnstellen(new Kunde("Silke"));
-s.hintenAnstellen(new Kunde("Tim"));
-println(s.erstenEntnehmen().name);
-println(s.erstenEntnehmen().name);
-println(s.erstenEntnehmen().name);
-class Supermarktkasse {
-   Kunde anfang;
-   Kunde ende;
-   void hintenAnstellen(Kunde kunde) {
-      if(anfang == null) {
-         anfang = kunde;
-         ende = kunde;
-         return;
-      }
-      ende.nachfolger = kunde;
-      ende = kunde;
-   }
-   Kunde erstenEntnehmen() {
-      Kunde erster = anfang;
-      anfang = erster.nachfolger;
-      return erster;
-   }
-}
-class Kunde {
-   String name;
-   Kunde nachfolger;
-   Kunde(String name) {
-      this.name = name;
-   }
-}
-</script>
-</HTML>
-==== Klassendiagramm ====
-<WRAP center round info 60%>
-{{ :listen:verkettet:klassendiagramm_einfach_verkettete_liste_einfacher_ansatz_.svg|}}
-Es ergibt sich das rechts dargestellte Klassendiagramm. \\ \\
-Die einfach verkettete Liste ist eine **rekursive** Datenstruktur. Dabei weist **rekursiv** (lat. recurrere „zurücklaufen“) darauf hin, dass ein Kunde-Objekt wiederum ein Kunde-Objekt als Nachfolger hat.
-Zwischen den Klassen Warteschlange und Kunde bestehen zwei **Aggregationsbeziehungen**.
-</WRAP>
-==== Aufgabe 1 ====
-<WRAP center round important 60%>
-**Problem 1: Vermischung von Struktur und Daten** \\
-Bei dieser Implementierung der Warteschlange müssen wir die Klasse ''Inhalt'' anpassen, um die Listenfunktionalität umzusetzen: Sie wird um ein zusätzliches Attribut ''nachfolger'' erweitert und bekommt mehrere Methoden zur Verwaltung der Listenstruktur (''hintenanstellenRekursiv'', ''getAnzahlRekursiv'', ...). Stell' Dir vor, Du programmierst ein Spiel und benötigst eine Liste zur Verwaltung der Spieler, eine zur Verwaltung der Gegner, eine zur Verwaltung der Hindernisse usw. Dies führt dazu, dass Du die Spieler-, Gegner- und Hindernis-Klasse jeweils um das Attribut ''nachfolger'' und die Methoden zur Verwaltung der Listenstruktur erweitern musst: **IMMER WIEDER DERSELBE PROGRAMMCODE!** \\ \\
-Der Kern des Problems liegt darin, dass der Code zur Modellierung der Daten (Klasse ''Inhalt'') und der Code zum Verwalten der Listenstruktur vermischt sind. [[datenstrukturen:einfachverklist:trennungstrukturdaten:start|Im nächsten Kapitel erfährst Du, wie Du im Fall der Warteschlange Struktur und Daten trennen kannst.]] \\ \\
-**Problem 2: Performance beim Zugriff aufs n-te Element** \\
-Will man auf das n-te Element einer verketteten Liste zugreifen, so muss sich das Programm - beginnend beim ersten Element - n-mal "nach vorne hangeln". Das kostet viel Zeit, denn im Mittel sind n/2 Schritte nötig. Dieser Aufwand fällt auch dann an, wenn an hinteren Ende der Liste ein neues Element eingefügt werden soll (siehe später). Letzteres ließe sich natürlich mit wenig Aufwand heilen, indem man im Warteschlangen-Objekt zusätzlich zur Referenz auf das erste Element immer auch die Referenz aufs letzte Element speichert. Da man bei einer Warteschlange nicht aufs n-te Element zugreifen muss, ist eine verkettete Liste dafür also insgesamt gut geeignet.
-</WRAP>