verkettete Liste

[bandy]

Hallo an alle!!
Brauche mal wieder eure Hilfe. Ich habe eine Aufgabe zu loesen, bei der ich seit wochen nicht weiter komme. Entweder weil es schlecht erklaert worden ist, oder weil es sehr kompliziert ist, oder beides. Es geht hierbei um den Umbau einer einfach verketetten Liste!
Hier die Aufgabenstellung:


Erweitern Sie die Aufgabe der einfach verketteten Liste so, dass das Listenende beim Anhaengen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente direkt am Ende der Liste angehaengt werden koennen.

Dazu ein paar Hilfestellungen:

*Sie muessen neben dem Anfang der Liste jetzt auch das Ende der Liste in einer Instanz speichern koennen.
*Erstellen Sie eine Methode, die Ihnen das aktuelle Ende der Liste zurueckliefert. Alternativ koennen Sie sich
das Listenende auch von der Methode zum Anhaengen liefern lassen.
*Setzen Sie den Wert der Instanz fuer das Listenende nach dem Anhaengen neuer Elemente jeweils auf das aktuelle
Ende der Liste und rufen Sie dann die Methode zum Anhaengen neuer Listenelemente mit diesem Wert neu auf.


Und hier der Quelltext der Aufgabe:
[JAVA=42]

class Listenelement{
String daten;
Listenelement naechster;

void setDaten(String datenNeu){
daten=datenNeu;
naechster=null;
}

void anhaengen(String datenNeu){
if (naechster==null){
naechster=new Listenelement();
naechster.setDaten(datenNeu);
}
else
naechster.anhaengen(datenNeu);
System.out.println("Daten "+datenNeu+" wurden eingefuegt.");
}
void ausgeben() {

if (naechster != null)
naechster.ausgeben();
System.out.println(daten);
}
}
public class Hausaufgabe2 {


public static void main(String[] args) {

Listenelement listenAnfang=new Listenelement();
listenAnfang.setDaten("Element 1");
for (int element =2; element<4;element++)
listenAnfang.anhaengen("Element "+element);
listenAnfang.ausgeben();


}

}
[/code]

Hat jemand eine Idee wie man die Aufgabe loesen kann????

 

[javimka]

Ich würde eine neue Klasse Liste schreiben, der du dann Listenelemente anhängen kannst. Diese neue Klasse soll dann ständig das erste und letzte Element gespeichert haben, so dass man schnell darauf zugreifen kann.

 

[jule37]

halte doch einfach eine referenz auf das ende der liste, die immer aktualisiert wird, wenn ein element angehängt wird

pseudocode

public class List {

    private Node head;
    private Node tail;

    ...

    public void add(Node node){
    
        tail.next = node;
        tail = tail.next;
    }
}

public class Node {
    public Node next;
    public Object data;
}

und schon läuft das

 

[Landei]

Mal etwas OT: Einfach verkettete Listen: Warum veränderlich?

 

[bandy]

Naja, ich denke es wird nicht ganz das gesucht was hier vorgeschlgen wird. Die wollen von uns eine Methode haben, keine Klasse! Hier nochmal der Ausschnitt aus der Aufgabenstellung:

"*Erstellen Sie eine Methode, die Ihnen das aktuelle Ende der Liste zurueckliefert. Alternativ koennen Sie sich das Listenende auch von der Methode zum Anhaengen liefern lassen."

Also so etwas:
[JAVA=1]void ende(){

}[/code]

Dann wollen die noch das:

"*Sie muessen neben dem Anfang der Liste jetzt auch das Ende der Liste in einer Instanz speichern koennen."

Ich nehme an, dass es dann so etwas ist:

[JAVA=1]Listenelement ende;
[/code]Also Variable vom Typ der Klasse.
Aber wie das ganze Umbauen und was ich dann beim alten Quelltext weglassen muss ist hier die Frage fuer mich. Danke aber trotzdem fuer Vorschlaege, warte auf weitere.

 

[Michael...]

Die wollen von uns eine Methode haben, keine Klasse!

Man soll in die bestehende Klasse eine Methode einfügen und darf dazu bestehende Methoden anpassen:

*Setzen Sie den Wert der Instanz fuer das Listenende nach dem Anhaengen neuer Elemente jeweils auf das aktuelle
Ende der Liste und rufen Sie dann die Methode zum Anhaengen neuer Listenelemente mit diesem Wert neu auf.

Siehe Post von Jule37

 

[Michael...]

Also so etwas:
[JAVA=1]void ende(){

}[/code]

Wohl eher so etwas:

public Listenelement getEnde() {
    return ende;
}

 

[Wortraum]

Warum sollte man in ein Listenelement das Wissen einer Liste stopfen? Ein Element kann den Vorgänger und den Nachfolger kennen, aber warum soll es etwas über das Ende wissen? Da sich das Ende ändert, müßte zudem bei allen Elementen das Ende aktualisiert werden, sobald ein Element angehängt wird. :toll:

Ich sehe hier das Problem, daß Liste und Listenelement in einen Topf geworfen und dann ordentlich vermischt wurden. listenAnfang.ausgeben() bedeutet eigentlich liste.ausgeben(), und listenAnfang.einfuegen() bedeutet liste.anhaengen(). In einem Listenelement selbst werden übrigens die Nachfolger vergessen, wenn man die Daten ändert.

Vielleicht ist das folgende gemeint, aber das ist weder schön, noch sollte das jemandem gelehrt werden (man verzeihe mir, daß ich den Quelltext richtig einrücke):

public class Listenelement {
    private String daten;
    private Listenelement naechster;
    private Listenelement ende = this;

    public void setDaten(String datenNeu) {
        daten = datenNeu;
        naechster = null;
        /* Alle Nachfolger gehen verloren, wenn neue Daten gesetzt werden! */
    }

    public Listenelement anhaengen(String datenNeu) {
        if (ende == this) {
            naechster = new Listenelement();
            naechster.setDaten(datenNeu);
            ende = naechster;
            System.out.println("Daten " + datenNeu + " wurden eingefuegt.");
        } else {
            ende = ende.anhaengen(datenNeu);
        }
        return ende;
    }

    public void ausgeben() {
        if (naechster != null) {
            naechster.ausgeben();
        }
        System.out.println(daten);
    }
}

Das ist ein ziemliches Durcheinander. :shock: Nun hat auch jedes Listenelement eine Variable ende, aber nur beim ersten und letzten Listenelement stimmt der Wert immer; wenn man ein anderes Listenelement hat, kann man über das kein Element mehr ans Ende der Liste einfügen, oder anders gesagt: dort ist die Variable Ende sinnlos. Würde man bei jedem Einfügen das Ende in jedem Element aktualisieren, könnte man beim Einfügen auch gleich wieder alle Elemente durchlaufen.

Bei jedem Einfügen, außer beim ersten, wird einfuegen() nun nur noch zweimal aufgerufen: einmal beim ersten Listenelement, das das Ende kennt, dann bei ende.einfuegen() aus, womit ein neues Listenelement eingefügt wird. Jedes Endelement erkennt, daß es selbst das Ende ist (ende == this) und hängt ein neues Element an.

 

[bandy]

Warum sollte man in ein Listenelement das Wissen einer Liste stopfen? Ein Element kann den Vorgänger und den Nachfolger kennen, aber warum soll es etwas über das Ende wissen? Da sich das Ende ändert, müßte zudem bei allen Elementen das Ende aktualisiert werden, sobald ein Element angehängt wird. :toll:

Ich sehe hier das Problem, daß Liste und Listenelement in einen Topf geworfen und dann ordentlich vermischt wurden. listenAnfang.ausgeben() bedeutet eigentlich liste.ausgeben(), und listenAnfang.einfuegen() bedeutet liste.anhaengen(). In einem Listenelement selbst werden übrigens die Nachfolger vergessen, wenn man die Daten ändert.

Vielleicht ist das folgende gemeint, aber das ist weder schön, noch sollte das jemandem gelehrt werden (man verzeihe mir, daß ich den Quelltext richtig einrücke):

public class Listenelement {
    private String daten;
    private Listenelement naechster;
    private Listenelement ende = this;

    public void setDaten(String datenNeu) {
        daten = datenNeu;
        naechster = null;
        /* Alle Nachfolger gehen verloren, wenn neue Daten gesetzt werden! */
    }

    public Listenelement anhaengen(String datenNeu) {
        if (ende == this) {
            naechster = new Listenelement();
            naechster.setDaten(datenNeu);
            ende = naechster;
            System.out.println("Daten " + datenNeu + " wurden eingefuegt.");
        } else {
            ende = ende.anhaengen(datenNeu);
        }
        return ende;
    }

    public void ausgeben() {
        if (naechster != null) {
            naechster.ausgeben();
        }
        System.out.println(daten);
    }
}

Das ist ein ziemliches Durcheinander. :shock: Nun hat auch jedes Listenelement eine Variable ende, aber nur beim ersten und letzten Listenelement stimmt der Wert immer; wenn man ein anderes Listenelement hat, kann man über das kein Element mehr ans Ende der Liste einfügen, oder anders gesagt: dort ist die Variable Ende sinnlos. Würde man bei jedem Einfügen das Ende in jedem Element aktualisieren, könnte man beim Einfügen auch gleich wieder alle Elemente durchlaufen.

Bei jedem Einfügen, außer beim ersten, wird einfuegen() nun nur noch zweimal aufgerufen: einmal beim ersten Listenelement, das das Ende kennt, dann bei ende.einfuegen() aus, womit ein neues Listenelement eingefügt wird. Jedes Endelement erkennt, daß es selbst das Ende ist (ende == this) und hängt ein neues Element an.

Hast mich richtig verstanden und geholfen, nur das die Liste bei Dir Rueckwaerts ausgegeben wird, aber das habe ich schon hingekriegt:applaus: