| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung |
| faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:start [20.10.2021 15:02] – [Implementation] sbel | faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:start [11.01.2024 08:59] (aktuell) – [Definition: Verkettete Liste] Marco Kuemmel |
|---|
| * Konstruktor ''List()'' – erzeugt eine leere Liste. | * Konstruktor ''List()'' – erzeugt eine leere Liste. |
| * ''isEmpty(): boolean'' – gibt ''true'' zurück, wenn die Liste kein Element enthält, sonst wird ''false'' zurückgegeben. | * ''isEmpty(): boolean'' – gibt ''true'' zurück, wenn die Liste kein Element enthält, sonst wird ''false'' zurückgegeben. |
| *'' length(): int'' – gibt die Anzahl der in der Liste enthaltenen Werte zurück. Eine leere Liste hat die Länge 0. Aufrufe von ''append'' und ''instertAt'' erhöhen die Anzahl um 1. | *'' length(): int'' – gibt die Anzahl der in der Liste enthaltenen Werte zurück. Eine leere Liste hat die Länge 0. Aufrufe von ''append'' und ''insertAt'' erhöhen die Anzahl um 1. |
| * ''getValueAtN(n: int): T'' – gibt den Wert an der Position n in der Liste zurück. n muss dabei mindestens 0 und höchstens ''lenght()-1'' sein. Falls dies nicht zutrifft, wird null zurückgegeben. | * ''getValueAtN(n: int): T'' – gibt den Wert an der Position n in der Liste zurück. n muss dabei mindestens 0 und höchstens ''length()-1'' sein. Falls dies nicht zutrifft, wird null zurückgegeben. |
| * ''append(val: T)'' – fügt einen Wert am Ende der Liste ein. Der eingefügte Wert befindet sich nach dem Aufruf an der Stelle ''length()-1''. | * ''append(val: T)'' – fügt einen Wert am Ende der Liste ein. Der eingefügte Wert befindet sich nach dem Aufruf an der Stelle ''length()-1''. |
| * ''insertAt(index: int, val: T)'' – fügt einen Wert an der Position ''index'' ein. Jeder Wert, der sich hinter der Einfügestelle befindet, befindet sich nach dem Aufruf eine Position weiter hinten. ''index'' muss mindestens 0 und höchstens ''lenght()'' sein. Falls dies nicht zutrifft, wird die Liste nicht verändert. Der eingefügte Wert befindet sich nach dem Aufruf an der Stelle ''index''. | * ''insertAt(index: int, val: T)'' – fügt einen Wert an der Position ''index'' ein. Jeder Wert, der sich hinter der Einfügestelle befindet, befindet sich nach dem Aufruf eine Position weiter hinten. ''index'' muss mindestens 0 und höchstens ''length()'' sein. Falls dies nicht zutrifft, wird die Liste nicht verändert. Der eingefügte Wert befindet sich nach dem Aufruf an der Stelle ''index''. |
| * ''hasValue(val: T): boolean'' – gibt ''true'' zurück, wenn die Liste einen Wert enthält, der gleich (im Sinne von ''equals'') dem Wert val ist, sonst wird ''false'' zurückgegeben. | * ''hasValue(val: T): boolean'' – gibt ''true'' zurück, wenn die Liste einen Wert enthält, der gleich (im Sinne von ''equals'') dem Wert val ist, sonst wird ''false'' zurückgegeben. |
| * ''removeAt(index: int)'' – entfernt den Wert, der an der Stelle ''index'' in der Liste steht, aus der Liste. ''index'' muss mindestens 0 und höchstens ''length()-1'' sein. Falls dies nicht zutrifft, wird die Liste nicht verändert. | * ''removeAt(index: int)'' – entfernt den Wert, der an der Stelle ''index'' in der Liste steht, aus der Liste. ''index'' muss mindestens 0 und höchstens ''length()-1'' sein. Falls dies nicht zutrifft, wird die Liste nicht verändert. |
| |
| |
| {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:klassendiagramm_list.drawio.png?600 |}} | {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:klassendiagramm_list.png?650 |}} |
| |
| Hinweise: | Hinweise: |
| |
| * Liste und Knoten werden ist als generische Klassen implementiert und mit dem Typ-Parameter T parametrisiert, so dass man beliebige Java Objekte in der Liste verwalten kann. | * Liste und Knoten werden als generische Klassen implementiert und mit dem Typ-Parameter T parametrisiert, so dass man beliebige Java Objekte in der Liste verwalten kann. |
| * Es gibt andere (komfortablere) Möglichkeiten Listen zu implementieren, wir beschränken uns zunächst auf das wesentliche und entwickeln das dann weiter. | * Es gibt andere (komfortablere) Möglichkeiten Listen zu implementieren, wir beschränken uns zunächst auf das wesentliche und entwickeln das dann weiter. |
| |
| ==== Implementation ==== | ==== Implementation ==== |
| |
| Klone das Repo https://codeberg.org/qg-info-unterricht/verkettete-liste-java und bearbeite folgenden Aufgaben, um die Liste gemäß des obigen Implementatoinsdiagramms zu programmieren. | Arbeite mit der BlueJ Vorlage von https://codeberg.org/qg-info-unterricht/verkettete-liste-java und bearbeite folgenden Aufgaben, um die Liste gemäß des obigen Implementationsdiagramms zu programmieren. |
| |
| ---- | ---- |
| === (A1) Die Klasse ''Node'' === | === (A1) Die Klasse ''Node'' === |
| |
| Die Klasse ''Node'' ist in der Vorlage bereits vollständig implementiert. Betrachte den Quellecode und mache dich mit Bedeutung und Funktionsweise der Methoden vertraut. Überprüfe besonders die Typen der Parameter und Rückgabewerte hinsichtlich der Parametrisierung der Klasse mit dem Typparameter ''T''. | Die Klasse ''Node'' ist in der Vorlage bereits vollständig implementiert. Betrachte den Quellcode, vergleiche ihn mit dem oberen Klassendiagramm und mache dich mit Bedeutung und Funktionsweise der Methoden vertraut. Überprüfe besonders die Typen der Parameter und Rückgabewerte hinsichtlich der Parametrisierung der Klasse mit dem Typparameter ''T''. |
| |
| ---- | ---- |
| {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:empty_list.drawio.png?200|}} | {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:empty_list.drawio.png?200|}} |
| |
| Das Bild zeigt das Objektdiagramm einer leeren Liste. Füge der Klasse ''List'' einen Konstruktor hinzu, der eine solches Listenobjekt erzeugt. Teste den Konstruktor indem du ein Listenobjekt erzeugst und mit dem Objektinspektor untersuchst, ob er eine leere Liste wie gewünscht erzeugt. | Das Bild zeigt das Objektdiagramm einer leeren Liste. Füge der Klasse ''List'' einen Konstruktor hinzu, der eine solches Listenobjekt erzeugt. Teste den Konstruktor, indem du ein Listenobjekt erzeugst und mit dem Objektinspektor untersuchst, ob er eine leere Liste wie gewünscht erzeugt. |
| |
| ++++ Hilfe | | ++++ Hilfe | |
| |
| * Benötigt der Konstruktor Parameter? | * Benötigt der Konstruktor Parameter? |
| * Welche Attribute hat das Listenobjekt? Wie müssen diese bei einer neuen, leeren Liste belegt sein? | * Welche Attribute hat das Listenobjekt? Wie müssen diese bei einer neuen, **leeren** Liste belegt sein? |
| * Welche Anweisungen musst du deinem Konstruktor hinzufügen, so dass die Attribute die gewünschten Werte haben? | * Welche Anweisungen musst du deinem Konstruktor hinzufügen, sodass die Attribute die gewünschten Werte haben? |
| |
| ++++ | ++++ |
| |
| Implementiere dann die Methode ''isEmpty''. Welches Kriterium kannst du verwenden um festzustellen, dass die Liste leer ist? Verleiche das Objektdiagramm der leeren Liste mit dem der Liste mit Knoten oben auf der Seite. | Implementiere dann die Methode ''isEmpty''. Welches Kriterium kannst du verwenden, um festzustellen, dass die Liste leer ist? Vergleiche das Objektdiagramm der leeren Liste mit dem der Liste mit Knoten oben auf der Seite. |
| |
| Teste die Methode zunächst mit deiner leeren Liste. | Teste die Methode zunächst mit deiner leeren Liste. |
| ++++ | ++++ |
| |
| | ==== Weitere Methoden der Liste ==== |
| |
| ---- | Bearbeite die Arbeitsaufträge der Reihe nach, um deine Listenimplementation zu vervollständigen. |
| {{:aufgabe.png?nolink |}} | |
| === (A3) Die Methode "append" === | |
| |
| Beim Anhängen eines weiteren Knotens an die Liste sind zwei Fälle zu unterscheiden: | * [[append|Anhängen eines neuen Elements]] |
| - Die Liste ist leer | * [[lengthvalue|Länge, Wert auslesen]] |
| - Die Liste ist nicht leer | * [[insert|Einfügen von Elementen]] |
| | * [[remove|Löschen von Elementen]] |
| | * [[hasvalue|Suche nach Inhaltselement]] |
| |
| **Liste leer** | Überprüfe deine Implementation, wenn diese vollständig ist durch ausführen der automatisierten Tests, indem du auf der grünen Testklasse ''ListTest'' mit der rechten Maustaste den Punkt ''Alles testen'' auswählst. |
| | |
| Wenn die Liste Leer ist, ist der Vorgang schnell beschrieben, eine Veranschaulichung findet sich im Diagramm unten. | |
| | |
| * Erzeuge eine neuen Knoten mit dem Nachfolger "null" | |
| * Setze das Attribut first der Liste auf den neuen Knoten | |
| | |
| {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:append_empty.drawio.png?500 |}} | |
| | |
| **(A)** Implementiere in der Methode ''append'' den Teil des Codes, der an eine leere Liste einen neuen Knoten anhängt. Die Methode ''isEmpty()'' ist hilfreich. Teste deine Methode von Hand, indem du eine Liste für Integer Zahlen erzeugst und einen Knoten in die leere Liste einfügst. | |
| |
| ---- | ---- |
| **Liste nicht leer** | |
| |
| Das folgende Objektdiagramm veranschaulicht die Schritte, die beim Anhängen eines neuen Knotens an eine nicht leere Liste auszuführen sind. | |
| |
| {{ :faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:append.drawio.png?700 |}} | {{simplefilelist>:faecher:informatik:oberstufe:adt:verkettete_liste:liste_java:praesentationen:*}} |
| |
| **(B)** Schreibe als Merksatz stichwortartig nieder, was beim Anhängen eines neuen Knotens alles passieren muss. | ---- |
| | |
| **Bewegen in der Liste** | |
| | |
| Ein konkretes Problem stellt sich noch in Schritt 2 des Ablaufs zum Einfügen eines neuen Knotens: Wie können wir uns durch die Liste bewegen, wenn das Listenobjekt selbst nur die Referenz auf den ersten Knoten kennt? | |
| | |
| Hier gehen wir ähnlich vor wie bei der Erhöhung einer Zählvariablen: | |
| ^Zähler ^ Liste ^ | |
| |<code java> | |
| // Neuer Zähler | |
| int i=0; | |
| // Zählen bis 99 | |
| while (i < 100) { | |
| i++; | |
| } | |
| // Ende der Zahlenreihe erreicht, i = 99 | |
| </code>|<code java> | |
| // Temporären Knotenzeiger mit dem Start der Liste initialisieren | |
| Node<T> current = first; | |
| // weitergehen bis zum Ende | |
| while(current.getNext()!= null) { | |
| current = current.getNext(); | |
| } | |
| // Jetzt zeigt current auf den letzten Knoten.| | |
| | |
| **(C)** Implementiere den zweiten Fall der Methode ''append'' entsprechend deiner Vorüberlegungen. Teste deine Methode von Hand, indem du eine Liste für Integer Zahlen erzeugst und 3 Knoten mit aufsteigenden Werten einfügst. Wenn du das Listenobjekt inspizierst, solltest du deine Werte in der korrekten Reihenfolge vorfinden. | |
| | |
| ++++ Hilfe 1 zur Methode "anhaengen" | | |
| | |
| | |
| | |
| <code java> | |
| if (anfang == null) { | |
| // FIXME | |
| } else { | |
| // Durch die Knotenliste wandern. | |
| // dazu benötigt man den Startknoten und speichert sich den | |
| // in der Variablen k vom Typ Listenknoten<T> | |
| | |
| Listenknoten<T> k = anfang; | |
| | |
| // k.nachfolger ist jetzt der nächste Knoten, | |
| // so kann man die Liste in einer while-Schleife | |
| // durchgehen... | |
| while ( // Bedingung für das ist nicht der letzte Knoten? ) { | |
| // k soll auf seinen Nachfolger gesetzt werden | |
| } | |
| k.nachfolger = // Was ist der (neue) Nachfolger des letzten Knotens? | |
| } | |
| </code> | |
| | |
| | |
| ++++ | |
| | |
| ++++ Hilfe 2 zur Methode "anhaengen" | | |
| | |
| <code java> | |
| // Um von einer Knoten zum nächsten zu gelangen, kann man den Ausdruck | |
| k = k.nachfolger; | |
| // verwenden. Das ersetzt den Knoten in der Variablen k durch seinen Nachfolger. | |
| | |
| </code> | |
| | |
| ++++ | |
| | |
| | |
| ++++ Lösung zur Methode "anhaengen" | | |
| | |
| | |
| <code java> | |
| if (anfang == null) { | |
| anfang = neu; | |
| } else { | |
| // Durch die Knotenliste wandern. | |
| // dazu benötigt man den Startknoten und speichert sich den | |
| // in der Variablen k vom Typ Listenknoten<T> | |
| | |
| Listenknoten<T> k = anfang; | |
| | |
| // k.nachfolger ist jetzt der nächste Knoten, | |
| // so kann man die Liste in einer while-Schleife | |
| // durchgehen... | |
| while ( k.nachfolger != null ) { | |
| // k soll auf seinen Nachfolger setzen | |
| k = k.nachfolger; | |
| } | |
| k.nachfolger = neu; // Der neue Knoten ist der Nachfolger des (jetzt in k gespeicherten) letzten Knotens | |
| } | |
| </code> | |
| | |
| | |
| ++++ | |
| | |
| ---- | |
| {{:aufgabe.png?nolink |}} | |
| === (A2) Die weiteren Methoden === | |
| |
| Die weiteren Methoden kannst du unter Zuhilfenahme der Kenntnisse aus Aufgabe 1 sicherlich gut implementieren - die Schlüsselstellen sind //"wie komme ich von einem Listenelement zum nächsten"// und //"wie verknüpfe ich neu hinzugekommene Listenelemente"// - für beides findest du im Code zu Aufgabe 1 exemplarische Beispiele. | <btn>[[..:compare_array_list:start|<<< Zurück zum Vergleich: Arrays und Listen]]</btn> |