text: Java Übung 9 - Grundlagen der Informatik - Fachrat Informatik - Forum
  Sunday, June 24th 2007, 5:09pm
  In Aufgabe 2 sollen wir eine einfach verkettete Liste erzeugen und darin einige Objekte zwecks Weiterverarbeitung reintun.
  Jetzt gibt es allerdings bereits vorgefertigte Listen, siehe LinkedList oder ArrayList. Soweit ich das verstehe, ist LinkedList jedoch doppelt verkettet, also zeigt durchaus auch auf den Vorgänger, womit LinkedList eigentlich bereits aus der Aufgabenstellung herausfällt.
  Aber verstehe ich das richtig, dass wir quasi eine neue Klasse schreiben sollen, in der wir die Datenstruktur der Liste unterbringen (also nicht den Krams in die Klasse "CarRental" tun!) und diese Liste komplett selbst erstellen sollen?
  Oder sollen wir dann in dem Falle ArrayList oder sowas benutzen?
  Sunday, June 24th 2007, 5:40pm
  RE: Java Übung 9
  Implementieren Sie hierzu eine einfach verkettete Liste[...]
  klingt für mich relativ eindeutig. Implementieren heißt ja eigentlich selber schreiben. Ich meine, wozu sollten wir uns sonst in der Wikipedia schlaulesen, was denn eine verkettete Liste überhaupt ist? Ich hab zumindest eine neue Klasse MyLinkedList erstellt, die aus lauter kleinen MyLinkedListItems besteht. Allerdings eine (zyklische) doppelt verkettete Liste, weil ich die für manche Probleme wesentlich eleganter finde als die einfach verkettete.
  Und außerdem: ohne die Liste wäre die Aufgabenstellung keine zwei Wochen wert
  Hm, wo mich grad nochmal jemand drauf aufmerksam gemacht hat
  ... dürfen wir da überhaupt eine doppelt verkettete Liste benutzen? In der Aufgabenstellung steht ja einfach verkettet, aber ich seh irgendwie keinen Sinn darin, ausgerechnet die zu nehmen. Ich meine, mit ner doppelt verketteten erreicht man das selbe, und einfacher ist sie auch nicht.
  Also Frage an die die Ahnung von den Aufgaben haben: (Lars z.B.)
  Muss es unbedingt die einfach verkettete Liste sein, oder können wir auch die doppelte nehmen?
  Monday, June 25th 2007, 3:24pm
  Wenn du die Liste selbst implementiert hast, würde ich kein Problem dabei sehen. Weiß natürlich aber auch nicht, ob Lars damit ein Problem hat Aber ich würde davon ausgehen, dass du für sinnvolle Mehrarbeit keinen Punkt abgezogen bekommst
  Tuesday, June 26th 2007, 10:47am
  So langsam nimmt meine Liste gestalt an, allerdings frage ich mich, wie das mit "Car" aussehen soll.
  Wir sollen ja "Implementieren Sie hierzu eine einfach verkettete Liste** für alle möglichen Varianten von Autos." tun, ist mit "Auto" jetzt die Untergruppe "Passenger Car, Truck und Van" gemeint oder die echte Klasse "Car"?
  Denn die ist doch abstrakt, womit man kein Objekt erzeugen kann, das man später in die Liste steckt, zumal die Methoden "add(Car)" und "remove(Car)" halt ein Car-Objekt haben möchten...
  Natürlich könnte ich meine Liste und deren Knoten mit Object als Parameter gestalten, aber dann könnte man tatsächlich ALLES reinstecken.
  Also was ist gemeint, ein Objekt der echten Klasse Car oder für Passenger Car, Truck und Van jeweils eine eigene Liste, oder eine komplett allgemeine?
  Also ich würde mal behaupten, dass es sicherlich nützlich wäre, wenn du deine Liste später
  auch mit anderen Objekten benutzen kannst.
  Eine Liste, die nur Objekte eines bestimmten Typs aufnehmen kann läßt sich schlecht wiederverwenden (Es sei denn die Elemente sind wieder von gleichen Typ).
  Naja, Van, Truck, und PassengerCar sind doch Unterklassen (ist das der richtige Begriff?) von Car, also wenn du eine Liste hast in die du Objekte vom Typ Car reintun kannst, dann kannst du doch auch alle Objekte reintun die Instanzen von einer Unterklasse von Car sind, also z.B. auch Van, Truck oder PassengerCar-Objekte. Das sind ja im Endeffekt auch alles Cars.
  Und das mit der ganz allgemeinen Liste für Objekte vom Typ Object funktioniert ja genau so. Da kannst du auch nur beliebige Objekte reintun, weil alle Klassen die du erstellst ohne eine Überklasse (Superklasse) anzugeben, automatisch die Superklasse java.lang.Object haben. Das heißt ...
  ... ist in Wirklichkeit ...
  ... und deshalb kannst du auch so Sachen machen wie
  Object neuesAuto = new Vehicle;
  Das ginge sonst nicht!
  This post has been edited 1 times, last edit by "Schokoholic" (Jun 26th 2007, 2:55pm)
  Tuesday, June 26th 2007, 3:51pm
  Habe halt zuerst Object benutzt, weil ich in der Hauptapplikation ja kein "echtes" Car-Objekt erstellen und reinstecken konnte. Aber so kann ich das direkt auf Car zuschneiden.
  Im Moment habe ich halt das Problem, dass ich zwar Knoten in die Liste einsetzen kann, aber mit dem Löschen haperts. Ich fürchte, ich muss mein Konzept nochmal überdenken, weil das mit den Zeigern nicht so klappt.
  Wenn ich das letzte Element löschen möchte, muss ich ja quasi nur den Zeiger vom Vorletzten Element auf "null" deuten lassen.
  Aber das würde bedeuten, ich bräuchte neben dem Next-Element auch ein Previous-Element, oder bin ich da auf dem Holzweg?
  This post has been edited 1 times, last edit by "hamena314" (Jun 26th 2007, 3:51pm)
  Tuesday, June 26th 2007, 4:47pm
  Dann hättest du ja schon fast eine doppelt verkettete List. Eine simple Lösung wäre zB einfach die Liste zu durchlaufen, und für jedes Element abzufragen, ob das folgende Element das letzte ist. Oder du speicherst dir die Länge n der Liste und durchläufst diese bis zum n-1 Element.
  This post has been edited 1 times, last edit by "Markus" (Jun 26th 2007, 4:48pm)
  Okay, dann hänge ich jetzt vollkommen.
  Ich habe 2 Klassen, einmal die Grundlage für den Knoten und einmal eine Knotenliste.
  Im Knoten brauche ich 2 Elemente, einen Datenteil (wo später das Car reinkommt) und einen Zeiger, der wiederrum ein Knoten oder null ist.
  Dem Konstruktor übergebe ich ein Car, setze den Datenteil auf das übergebene Car-Objekt und den Zeiger setze ich auf null (der neue Knoten ist ja automatisch der letzte Knoten in der Kette und zeigt damit auf null).
  In der Kettenliste klappt das mit dem Adden jedoch nicht, laut Aufgabenstellung soll ich ja "add(Car auto)" nutzen.
  Ich erzeuge zunächst einen Knoten "start" mit "public Knoten start".
  Jetzt soll dem in der add-Methode das Car-Objekt übergeben werden, indem man per start = new Knoten(auto) dem Knoten start das zuweist.
  Nun ist mein Problem, dass ich nicht verstehe, was in den next-Teil kommt, denn so kann ich zwar per start.daten.ausgeben() anzeigen lassen, welches Car sich darin befindet, doch adde ich zu der Liste einen weiteren Knoten mit einem neuen Car-Objekt, wird das alte Objekt überschrieben und is weg, bei start.daten.ausgeben() steht also lediglich das neue Car-Objekt und ich verstehe nicht wieso.
  [...]Ich erzeuge zunächst einen Knoten "start" mit "public Knoten start".[...]
  Wieso public? Dann könnte ja jeder Fiesling kommen und ein "deineListe.start = null;" machen, und deine schöne Liste wär futsch
  Da steckt noch ein ziemlich großer Logikfehler drin... Wozu ist denn der next-Teil im Sinne einer verketteten Liste gut?
  Eine verkettete Liste ist ja dadurch charakterisiert, dass man zu Anfang nur weiß wo das erste Element der Liste steht und dass jedes Element auf seinen Nachfolger zeigt. Wenn du also ein neues Element am Ende anhängen wolltest, müsstest du ja dafür sorgen, dass das bis dahin letzte Element dann auf das neue Element zeigt. Und das wiederum zeigt -- wie du schon richtig bemerkst -- auf nix.
  Hoffe, das ist jetzt nicht zu verwirrend
  Tuesday, June 26th 2007, 8:22pm
  Ich verstehe nicht so ganz, was du geschrieben hast, aber ich glaube, ich weiß, was du machen willst.
  Also, du hast ja scheinbar einen ausgewiesenen Startknoten, in dem kein Car steckt, oder? Dann weißt du Start.next den neuen Knoten zu. Wenn du dann noch ein Car hinzufügen willst, muss du halt die Liste von vorne nach hinten durchlaufen, und an den letzten Knoten den neuen Knoten anhängen. Alternativ kannst du auch einfach eine Referenz auf den letzten Knoten speichern, so ersparst du dir den Durchlauf bei jedem add.
  Nachtrag: Mist, zu langsam
  This post has been edited 1 times, last edit by "Markus" (Jun 26th 2007, 8:23pm)
  Tuesday, June 26th 2007, 10:05pm
  Hm, so langsam glaube ich auch, dass ich da was grundlegendes doch nicht verstanden habe, bloß was?
  Wenn ich in der add()-Methode dem next-Teil einen neuen Knoten zuweise, bekomme ich eine NullPointerException.
  public void add(Car auto){
  start.next = new Knoten(auto); // erzeugt NullPointerException
  Aber ich möchte doch hier in den Start-Knoten einen neuen Knoten setzen, der im Daten-Teil das Car-Objekt bestitzt.
  This post has been edited 1 times, last edit by "hamena314" (Jun 26th 2007, 10:06pm)
  Tuesday, June 26th 2007, 10:22pm
  Ich vermute mal, daß zu diesem Zeitpunkt start == null gilt. Daher: Ist beim Aufruf von add(...) die liste leer, so muß es start = new Knoten(auto) heißen.
  Und nochwas: Enthält die Liste bereits zwei oder mehr Elemente, so müssen neue Knoten ans Ende der Liste angefügt werden, nicht jedoch an den Knoten start.
  This post has been edited 1 times, last edit by "Joachim" (Jun 26th 2007, 10:22pm)
  Hm, das Ende ist doch dadurch gekennzeichnet, dass der Next-Teil auf null zeigt. Damit wäre start doch mein erster Knoten, der zu Beginn und damit alleine auf null zeigen müsste.
  Vielleicht verstehe ich auch den Aufbau der Liste selbst falsch?
  Zuerst generiere ich halt eine Kettenliste:
  1) [ ... ] // leere Liste
  2) Jetzt erzeuge ich einen Start- und einen End-Knoten.
  private Knoten start;
  private Knoten ende = new Knoten(null);
  Kettenliste(){
  start = new Knoten(ende);
  ende = new Knoten(null);
  [ (daten|next)-->(daten|next)-->null ] // Knoten 1 = start, Knoten 2 = ende.
  Lasse ich allerdings per System.out.println(start.daten) ausgeben, steht darin der Verweis auf einen anderen Knoten (vermutlich ende) und in start.next steht null.
  3) Ich erstelle in einer Anwendungsklasse zunächst 3 Car's.
  Car vw = new Car("vw)";
  Car skoda = new Car("skoda");
  Car ronda = new Car("ronda");
  Nun erzeuge ich eine leere Kettenliste und füge die Car's in die Liste
  Kettenliste test = new Kettenliste();
  test.add(vw);
  test.add(skoda);
  test.add(ronda);
  neuer.next = start;
  start.next = neuer;
  Ich befürchte allerdings, dass ich damit keine Kette geschaffen habe, sondern immer wieder die Knoten in einen einzigen Knoten stopfe.
  OK. Die leere Liste würde damit bei Dir nur aus einem Knoten bestehen, dessen Nachfolger null ist. Das ist eine Möglichkeit. Etwas eleganter fände ich es, die leere Liste dadurch zu kennzeichnen, daß der Startknoten auf null gesetzt wird. Damit würdest Du es vermeiden, einen Knoten in der Liste zu haben, der selber keinen Inhalt enthält und nur als Markierung dient.
  Bei der leeren Liste müßte in jedem Fall start == ende gelten (egal, welche der beiden oben von mir beschriebenen Designentscheidungen man trifft). Das ist hier aber nicht der Fall. Zudem frage ich mich, warum Du "start = new Knoten(ende)" setzt. Damit wäre start ein neuer Knoten, dessen *Inhalt* wieder ein Knoten ist ...
  Vielleicht hilft es Dir, wenn Du zunächst die Logik der Hilfsklasse Knoten vom restlichen Programm trennst. Implementiere dazu die Knoten-Methoden void setContent(Car), Car getContent(), boolean hasNext(), void setNext(Knoten). Methoden der Listenklasse (wie etwa add) greifen dann nur noch auf diese Methoden zu.
  Der Nachfolger des neuen Knoten soll also der Startknoten sein? Damit würde man die neuen Knoten am Anfang der Liste einfügen. Ist das Absicht?
  Der Nachfolger des Startknotens soll zudem der neue Knoten sein? Damit würdest Du einen Zyklus erschaffen ...
  Wednesday, June 27th 2007, 4:25pm
  Hm, das mit dem Ringschluss ist mir garnicht aufgefallen. Danke für den Hinweis!
  Ich habe jetzt die Klassen angepasst, in der Knotenklasse gibts jetzt die neuen Methoden:
  public Knoten next;
  public Car daten;
  Knoten(Car auto){
  daten = auto;
  public void setDaten(Car wagen){
  daten = wagen;
  public Car getDaten(){
  public void setNext(Knoten node){
  Die Kettenliste selbst habe ich auch angepasst, jetzt probiere ich mal die Ausgabe.
  Leider sieht es so aus, als wenn ich immer wieder in den gleichen Knoten die neuen Car-Objekte stecken würde, aber das kann doch nicht, sein, weil ich mit add() immer wieder einen neuen erzeuge und den next-zeiger weiterwandern lasse.
  public class Kettenliste {
  public Knoten start = new Knoten(null);
  public Knoten ende = new Knoten(null);
  public Kettenliste(){
  start.setNext(ende);
  ende.setNext(null);
  neuer.setNext(ende);
  Knoten aktuell = start;
  while (aktuell != null){
  System.out.println(aktuell.getDaten());
  aktuell = aktuell.next;
  Wenn ich in der Anwendungsklasse alles adde und ausgeben lasse, scheint das Ergebnis falsch zu sein, weil immer nur das letzte Car ausgegeben wird.
  liste.add(ronda);
  liste.add(skoda);
  liste.add(vw);
  liste.print();
  null // entspricht Datenteil vom Start-Knoten
  Name: vw // entspricht Datenteil von ...?
  null // entspricht Datenteil vom Endknoten(?)
  This post has been edited 2 times, last edit by "hamena314" (Jun 27th 2007, 4:30pm)
  Wednesday, June 27th 2007, 4:47pm
  Die Klasse Knoten sieht gut aus.
  Die Klasse Kettenliste ist aber noch ziemlich buggy.
  Ich schlage vor, Du schreibst die Klasse neu und verzichtest dabei auf die beiden Markierungsknoten am Anfang und am Ende. Die machen Dir vermutlich mehr Probleme als nötig.
  Ich fände folgende Implmentierung sinnvoll:
  Die leere Liste enthält keine Knoten (start == ende == null). Wird in die leere Liste ein Knoten namens "neu" eingefügt, so gilt start == ende == neu. Wird in die nicht-leere Liste ein Knoten "neu" eingefügt, so muß der bisherige Knoten "ende" den Knoten "neu" als Nachfolger haben, der Knoten "neu" hat selbst keinen Nachfolger (also null), nach der Einfügung muß der Zeiger "ende" auf den Knoten "neu" gesetzt werden.
  Wenn das dann funktioniert, solltest Du noch Durchläufe durch die Liste ermöglichen. Dazu führst Du einen weiteren Zeiger "current" ein und folgende Methoden: void iteratorReset() setzt current = start; boolean iteratorHasNext() liefert true zurück, wenn der aktuelle Knoten (also der, auf den der Zeiger "current" zeigt) einen Nachfolger hat); Car iteratorGetCurrent() liefert den Inhalt des aktuellen Knotens zurück; void iteratorStep() setzt das aktuelle Element einen Schritt weiter.
  Auf diese Weise sind dann auch elegant Listendurchläufe von außen möglich. (Noch besser wäre es natürlich, die Klasse Kettenliste von AbstractSequentialList abzuleiten, aber das ist schon fortgeschrittene Programmierung.)