Java Queue mit oder ohne Knoten?
Z.B. lautet die Aufgabe, folgende Situation mit einer geeigneten Datenstruktur umzusetzen: Eine Warteschlange von Kunden an der Kasse.
Ich nehme hier eine Queue (Warteschlange). Da die Warteschlange beliebig lang sein kann, will ich das Konzept der Queue auf die Datenstruktur "LinkedList" anstatt Array anwenden. Wie auch immer. Egal, was ich wählen werde, im Unterricht gab es auf den ABs immer zusätzlich einen Knoten, der Objekte speichert. Hier heißt mein Objekt Kunde und ich will einfach nur Kundenobjekte in der Warteschlange abspeichern, ich will keine "Knoten", einfach nur Kunden - Objekte. (Ich verstehe hier also nicht den Sinn von Knoten in einer Datenstruktur Queue)
Im Unterricht wird das dann aber so umgesetzt wie hier auf meiner Zeichnung:
Ich würde das aber so umsetzen (ohne Speicherung des Kunden - Objekts in einem Knoten):
Geht das? Was ist der Sinn eines sog. "Knotens"?
3 Antworten
Dann wäre die Frage, wie du die Knoten miteinander verknüpfen möchtest bzw. wie du die Reihenfolge regelst. Die Daten, die in der Queue gespeichert werden, sollen doch nicht extra Eigenschaften/Methoden dafür bereitstellen müssen.
Stell dir vor, du speicherst Personen-Objekte und die müssen allesamt eine getNext-Methode bereitstellen und eine Referenz auf ein anderes Objekt speichern, welches sie, sollten sie niemals in der Queue gespeichert werden, nie brauchen würden.
Die Knoten dienen dazu, die Struktur der Queue umzusetzen.
Eine Alternativlösung zu eigenen Knoten wäre die Nutzung einer bereits implementierten Liste (ArrayList/LinkedList/...).
class Queue<T> {
private List<T> nodes;
// add, remove, etc. ...
}
Den letzten Teilsatz verstehe ich nicht ganz. Daher anders formuliert: Statt ein Array als interne Speicherquelle oder eigene Node-Objekte setzt du ein Listenobjekt ein. Die Implementation von Methoden wie add, remove, etc. gestaltet sich somit leichter, da du in denen fast nur noch die Methoden des Listenobjekts aufrufen musst. Wenn du dir einmal die LinkedList anschaust: Die implementiert selbst bereits das Queue-Interface.
Ob dein Aufgabensteller/Prüfer wiederum von so einer Lösung begeistert wäre, kann ich nicht garantieren. Gerade für Anfänger wäre die Aufgabe, mit einer eigenen Node-Klasse zu arbeiten, interessanter/empfehlenswerter, denn auf diesem Weg muss mehr Logik selbst implementiert werden.
Eine Linked-List ist als ein sogenannter zyklischer gerichteter Graph mit Knoten und Kanten darstellbar. Jedes Objekt in der Liste wird als ein Knoten repräsentiert
Jeder Objekt-Knoten kennt je nach Implementierung der Linked-List seinen Vorgänger und seinen Nachfolger-Knoten. Das sind die Kanten.
Da Anna die erste Person in der Schlange ist, hat sie keinen Nachfolger-Knoten (NULL). Sie kam als erste rein und wird in dieser Situation als erste wieder herauskommen (FIFO). Nicht vom Begriff verwirren lassen: Nachfolger bezieht sich auf den "next"-Knoten, also die Person vor einem in einer Schlange.
Peter ist das letzte Element der Schlange. Er hat sie als letztes betreten. Somit hat er (noch) keine Vorgänger-Knoten. Wie du siehst, kann man mit dieser Graphen-Notation eindeutig die Struktur einer Warteschlange modellieren.
Die Liste selbst kann auch als Knoten in diesem System aufgefasst werden.
Der Listen-Knoten weiß stets, wer das erste und letzte Element der Schlange ist. Das ist so geregelt, da man hier schneller rechnen kann, also die Liste schneller von vorne oder von hinten durchlaufen kann und Listenoperationen schneller durchführen kann. Das sind Operationen zum Einfügen eines Elements in die Schlange oder zum Entnehmen eines Elements aus der Schlange.
Die Linked-List hat ggü. der Array-List einige Vorteile und Nachteile. Hier gekennzeichnet über die sogenannte O-Notation oder Landau-Notation (O(1) ist weniger komplex und damit schneller als O(n)):
Der Zugriff ist bspw. in der Array List schneller, die Manipulation (Einfügen/Löschen) hingegen in der LinkedList.
Der Wrapper rüstet die Person mit einem Zeiger auf next aus. Den hat die Person ja normalerweise nicht. So kannst du die Klasse Person unverändert lassen und belastest sie nicht mit der Tatsache, dass du sie in eine Queue stellen willst.
Ah, also jede Person hat von Natur aus keinen Nachfolger, kein Attribut Nachfolger. Sie hat erst einen Nachfolger, wenn man sie z.B. in eine Warteschlange reintut.
Datenstrukturen sollten völlig unabhängig vom späteren Inhalt implementiert werden. Was für Objekte gespeichert werden, spielt für die Datenstruktur keine Rolle.
Das Objekt Knoten dient gemeinsam mit der Liste zur Realisierung einer Queue, d. h. eine Queue kann beliebig viele Knoten haben. Der Knoten speichert dann intern eine Referenz auf die eigentlichen Daten.
Wenn du eine Queue ohne diese Knoten-Klasse implementierst, dann musst du Logik für die Queue (diese next-Referenz) in der Klasse Kunde unterbringen. Wenn du später eine weitere Klasse wie Käufer hast und für diese eine Queue benötigst, wäre diese nicht wiederverwendbar.
Eine Alternativlösung zu eigenen Knoten wäre die Nutzung einer bereits implementierten Liste (ArrayList/LinkedList/...).
Damit meinen Sie doch, dass man, anstatt selbst 60 Zeilen Code für eine Klasse Knoten zu schreiben, einfach strg xyz machen kann und dann so eine vorgefertigte Liste nutzen kann, oder?