Erste Schritte Verkettete Liste will einfach nicht in meinen Schädel

[Redbeard]

Guten Tag liebe Leute,
ich bräuchte bitte einen Tipp oder einen Denkanstoß in die richtige Richtung. Ich zerbreche mir nun schon seit Wochen den Schädel über eine Aufgabe aus meinem Java-Kurs und bekomme ich es einfach nicht hin. Ich scheine da auch nicht allein zu sein, weil ich dieses Listing schon ein paar mal hier im Forum gefunden habe - nur kann ich mit den Lösungsansätzen dort nicht wirklich was anfangen. Hier erstmal da Listing und dann mein Lösungsansatz mit den Fragen dazu:

package liste;

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);
       
        }


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

public class Liste {
    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();
    }
}

Die Aufgabe lautet:
Erweitern Sie das Programm so, dass das Listenende beim Anhängen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente direkt am Ende der Liste angehängt werden können. Hängen Sie zum Test mindestens 20 Elemente an.

Dazu ein paar Hilfestellungen:
• Sie müssen neben dem Anfang der Liste jetzt auch das Ende der Liste in einer Variablen speichern können.
• Erstellen Sie eine Methode, die Ihnen das aktuelle Ende der Liste zurückliefert.

Alternativ können Sie sich das Listenende auch von der Methode zum Anhängen liefern lassen.

• Setzen Sie den Wert der Variablen für das Listenende nach dem Anhängen neuer Elemente jeweils auf das aktuelle Ende der Liste und rufen Sie dann die Methode zum Anhängen neuer Listenelemente mit diesem Wert neu auf.

So weit so gut, die Aufgaben Stellung ist eigentlich klar. Nun mein Lösungsansatz, den ich aber nicht hinbekomme.

Ich würde die Klasse um ein Element erweitern, so dass Sie jetzt ein Feld "Listenelement letzter" enthält, welches ich nur im ersten Knoten speichern will, alle anderen sollen null sein. Wenn ich jetzt einen neuen Knoten anlegen will möchte ich ihm sagen, dass er ein neuen Knoten nach "letzter" anlegt und dann den neue angelegten Knoten in letzter referenzieren, aber ich bekomme es nicht hin.

Mache ich irgendwo einen Denkfehler?

Vielen Dank und viele Grüße
Red

 

[DrZoidberg]

Ich bin mir nicht sicher, ob du die Variable "letzter" in der "Listenelement" Klasse hinzufügen sollst oder in der "main" Methode.
Aber in jedem Fall wüde ich damit anfangen, die "anhaengen" Methode so zu verändern, dass sie das letzte Listenelement zurückliefert.

 

[Jardcore]

Ich würde behaupten das du 3 Klassen brauchst, "Liste", "ListenElement" und eine "Main" Klasse.
In der Main Klasse erstellst du deine Liste. Die Liste hat zwei Zeiger/Referenzen, "erstesElement" und "letztesElement" und die Methoden "anhaengen(ListenElement element)", "gibLetztesElement", "gibErstesElement".
Die Klasse "ListenElement" benötigt eine Referenz auf das nächste Element "ListenElement naechstesElement", dafür dann auch die getter und setter implementieren.

In "anhaengen" prüfst du ob das "ersteElement" null ist, wenn ja -->
erstesElement = element;
letztesElement = element;
Andernfalls:
letztesElement.setzeNaechstesElement(element);
letztesElement = element;

Das letzte Element bekommst du dann in der "gibLetztesElement" Methode durch ein "return letztes Element;"

Beste Grüße,
Jar

 

[Jardcore]

Hab die Gedanken mal 1 zu 1 in Code gegossen... nur die Logik an der wichtigen Stelle hab ich mal für Übungszwecke ausgelassen

public class Element {
    private String data;
    private Element next;
 
    public Element(String data) {
        setData(data);
    }
 
    public Element getNext() {
        return next;
    }
 
    public void setNext(Element next) {
        this.next = next;
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    @Override
    public String toString() {
        return data;
    }
}

public class ListExample {
    public static void main(String[] args) {
        List list = new List();
     
        for(int i = 1; i <= 20; i++) {
            list.add(new Element("Data"+i));
        }
     
        System.out.println(list);
        System.out.println(list.getFirst());
        System.out.println(list.getLast());
    }
}

public class List {
    private Element first;
    private Element last;
 
    public Element add(Element element) {
        // hier fehlt noch die Logik
    }
 
    public Element getFirst() {
        return first;
    }
 
    public Element getLast() {
        return last;
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Element cur = first;
        while(cur != null) {
            sb.append(cur);
            sb.append(" ");
            cur = cur.getNext();
        }
        return sb.toString();
    }
}

Ausgabe:

Data1 Data2 Data3 Data4 Data5 Data6 Data7 Data8 Data9 Data10 Data11 Data12 Data13 Data14 Data15 Data16 Data17 Data18 Data19 Data20
Data1
Data20

 

[JStein52]

Hab die Gedanken mal 1 zu 1 in Code gegossen...

Dein Code ist natürlich völlig ok so aber wenn der TO seinen obigen Code als Vorgabe hat und diesen erweitern soll natürlich ein bisschen davon weg.

 

[Jardcore]

Ich wollte ja nicht die Aufgabe für ihn erledigen

Frage an den TE, ist der Code den du gepostet hast schon von dir verändert oder der vorgegebene?

 

[Redbeard]

Es ist der vorgegebene Code. Meine Herangehensweise sieht mittlerweile so aus (habe die Namen der Variablen (für mich) sprechender gemacht:

package java05b_05_02;


class Element {
        String data;
        Element nextElement;
        Element previousElement;
        Element lastElement;
        Element firstElement;

        Element getLastElement() {
            return lastElement;
        }
       
        void setLastElement(Element lastElement) {
            this.lastElement = lastElement;
        }

        Element getFirstElement() {
            return firstElement;
        }
       
        void setFirstElement(Element firstElement) {
            this.firstElement = firstElement;
        }
       
        Element getPreviousElement() {
            return previousElement;
        }
       
        void setPreviousElement(Element previousElement) {
            this.previousElement = previousElement;
        }
       
        Element getNextElement() {
            return nextElement;
        }
       
        void setNextElement(Element nexElement) {
            this.nextElement = nextElement;
        }
       
        String getData() {
            return data;
        }
        void setData(String data) {
            this.data = data;
        }
   
       
        void addElement(Element list) {
           
            Element knoten = new Element();
            setLastElement(knoten);
       
           
        }
       
        void output() {
            System.out.println(data);
            if (nextElement != null)
                nextElement.output();
        }
       
       
    }

public class Java05b_05_02 {
    public static void main(String[] args) {
   
        Element list = new Element();
        list.setFirstElement(list);
        list.setLastElement(list);
        list.setPreviousElement(null);
        list.setNextElement(null);
        list.setData("Element 1");
        list.addElement(list);
       
       
    }
}

 

[JStein52]

void addElement(Element list) {

Element knoten = new Element();
setLastElement(knoten);


}

Da fällt mir schon mal als erstes auf: wofür brauchst du da einen Parameter ?

 

[JStein52]

Und als zweites frage ich mich gerade: wo verknüpfst du die Elemente eigentlich miteiander ?

 

[Redbeard]

Sorry, soweit bin ich mit dem neuen Code noch nicht. Habe das hier nur gepostet um meinen Gedankengang und meine Herangehensweise zu verdeutlichen. War doof formuliert von mir.

 

[Jardcore]

Du brauchst übrigens keine Getter / Setter wenn alle deine Attribute / Variablen die gleiche Sichtbarkeit haben wie deine Getter / Setter

Und scheinbar hast du uns nicht alles mitgeteilt, mittlerweile hat sich ja auch noch ein previous eingeschlichen^^ also eine doppelt verkettete Liste?

Edit: Irgendwie kann ich auch nicht nachvollziehen wieso ein Element Kenntnis über irgendwas erstes und irgendwas letztes haben soll. Ich könnte mir nur vorstellen, dass es zwei boolean flags gibt isFirst, isLast, welche angeben ob das Element an erster oder letzer Stelle ist.

 

[Jardcore]

Hier nochmal mehr auf dein ursprünglichen Code gemünzt, also 2 Klassen aber die Klasse mit der Main Methode ist auch die Liste.

public class List {
    private Element firstElement;
    private Element lastElement;
 
    public static void main(String[] args) {
        List list = new List();
     
        for(int i = 1; i <= 20; i++) {
            list.addElement(new Element("Data"+i));
        }
     
        System.out.println(list);
        System.out.println(list.getFirstElement());
        System.out.println(list.getLastElement());
     
    }
 
    public Element addElement(Element element) {
        if(firstElement == null) {
            firstElement = element;
        } else {
            lastElement.setNext(element);
        } 

        lastElement = element;
     
        return getLastElement();
    }
 
    public Element getLastElement() {
        return lastElement;
    }
 
    public Element getFirstElement() {
        return firstElement;
    }
 
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Element current = firstElement;
        while(current != null) {
            sb.append(current);
            sb.append(" ");
            current = current.getNext();
        }
        return sb.toString();
    }
}

public class Element {
    private String data;
    private Element nextElement;
 
    public Element(String data) {
        setData(data);
    }
 
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public Element getNextElement() {
        return nextElement;
    }
 
    public void setNextElement(Element nextElement) {
        this.nextElement = nextElement;
    }
 
    @Override
    public String toString() {
        return data;
    }
}

Beachte die toString() Methoden, die dir eine einfache Ausgabe erlauben.
Dann kannst du einfach System.out.println(ELEMENT); aufrufen

Vielleicht kommt das irgendwann noch, aber als Erweiterung könnte ich mir die Lösch-Operation vorstellen, das Implementieren einer size() Methode. Die Erweiterung zu einer doppelt verketteten Liste oder zu einem Ring. Und zu guter letzt natürlich der Umbau zu einer generischen Liste.