DoubleLinkedList

[Waterman]

Hallo ich bearbeite gerade eine Aufgabe zum Thema DoubleLinkedList.
Als erstes werde ich die Aufgabenstellung posten und dann meine ersten Gedankenschritte.

Aufgabe 1
Ergänzen Sie die aus der Vorlesung bekannte Klasse DoubleLinkedList<T>. Gehen Sie bei der
Implementierung der geforderten Methoden aber davon aus, dass Ihnen in dieser Klasse keine Methoden
zur Verfügung stehen und Sie auch nur genau die in der Teilaufgabe geforderte Methode hinzufügen
dürfen. Änderungen und Ergänzungen außerhalb der jeweils geforderten Methode sind bei keiner
Teilaufgabe erlaubt.

a) Vervollständigen Sie die Methode DoubleLinkedList<T> split( T o ).
Die Methode split soll alle Elemente aus der Liste entfernen, die vor dem ersten Element stehen, dessen
Inhalt bei einem Vergleich mit o über die Methode equals den Wert true ergibt. Eine Liste mit den
entfernten Elementen soll als Ergebnis des Aufrufs von split zurückgegeben werden.

Hier sind die Klassen:

public class DoubleLinkedList<T> 
{
private Element first, last;
private int size;
    protected class Element {
        private T content;
        private Element previous, next;
        public Element( T c ) {
            content = c; previous = next = null;
        }
        public T getContent() { return content; }
        public void setContent( T c ) { content = c; }
        public Element getPrev() { return previous; }
        public void setPrev( Element e ) { previous = e; }
        public Element getNext() { return next; }
        public void setNext( Element e ) { next = e; }
        public boolean isFirst() { return previous == null; }
        public boolean isLast() { return next == null; }
    }
}

Die Methode die ich nun schreiben soll ist hier:
In dieser Ausführung habe ich erst mal die Tatsache das ich keine zusätzlichen Methoden implementieren darf ignoriert und einige Methoden implementiert mit denen ich dann eine DoubleLinkedList Object verändern kann.(Ich weiß nicht ob dieser Versuch funktioniert)

public class DoubleLinkedList<T> 
{
    public void addFirst(T o){
        if(first==null){
            first=last=new Element(o);
        }else{
            Element neuEle=new Element(o);
            neuEle.setNext(first);
            first.setPrev(neuEle);
            first=neuEle;
        }
        size++;
    }

    public T removeFirst(){
        T result = null;
        if(first!=null){
            result=first.getContent();
            first=first.getNext();
            if(first!=null){
                first.setPrev(null);
            }else{
                last=null;
            }
            size--;
        }
        return result;
    }

    public DoubleLinkedList<T> split(T o){
        DoubleLinkedList neu= new DoubleLinkedList();
        Element actual = first;
        boolean b = false;
        while(actual!=null && !b){
            if(actual.getContent().equals(o)){
                b=true;
                return neu;
            }else{
                T ob=first.getContent();
                neu.addFirst(ob);
                removeFirst();
            }
        }
        return neu;
    }

}

Leider weiß ich nicht wie ich die Methode schreiben soll ohne durch andere Methoden das DoubleLinkedList Objecte zu verändern.

Gruß Luc

 

[Defqon84]

Hallo,

prinzipiell ist das gar nicht so schwierig. Nachfolgend ein paar Gedanken dazu:

1. In einer Schleife sollte man zunächst ermitteln, wo der fragliche Eintrag der Liste ist
2. Ist man an diesem Punkt angelangt, welche Methode kommt dann in Frage um alle Elemente bis zum Anfang zu durchlaufen?
3. Welche Aktionen sind bei jedem Schritt des 'Durchlaufens' notwendig, um eine neue Liste mit den 'gelöschten' Elementen zu erzeugen / füllen?
4. Am Listenkopf angekommen, welcher 'Trick' ist notwendig, damit die Liste weiterhin funktioniert bzw. an der richtigen Stelle startet?

Ich hoffe das gibt die richtigen Denkanstöße.

Viele Grüße

 

[Waterman]

Hallo,

Also ich habe ein die Methode nochmal umgestaltet(sprich wie in der Aufgabenstellung verlangt wird keine zusätzlichen Methoden zu verwenden)

    public DoubleLinkedList split(Object o){
        DoubleLinkedList neu= new DoubleLinkedList();
        Element actual = first;
        boolean b = false;
        while(actual!=null && !b){
            if(actual.getContent().equals(o)){
                b=true;
                return neu;
            }else{
                Object obj=first.getContent();
                Element actualNeu=neu.first;
                if(actualNeu==null){
                    neu.first=neu.last=new Element(obj);
                    neu.size++;
                }else{
                    Element neuEle= new Element(obj);
                    neuEle.setNext(actualNeu);
                    actualNeu.setPrev(neuEle);
                    actualNeu=neuEle;
                    neu.size++;
                }
                if(first!=null){
                    first=first.getNext();
                    if(first!=null){
                        first.setPrev(null);
                        size--;
                    }else{
                        last=null;
                        size--;
                    }
                }
                actual=actual.getNext();
            }
        }
        return neu;
    }

1.wo der fragliche eintrag ist mache ich ja mit meiner Methode while(actual!=null && !b)
sprich actual!=null setzt mein Element weiter bis ich am Ende angekommen bin oder eben b=true gesätzt wird was ich ja bei meiner if-Bedingung abfrage

        while(actual!=null && !b){
            if(actual.getContent().equals(o)){
                b=true;
                return neu;
            }else{

2.ich darf ja leider keine Zusätzlichen Methoden benutzten. In meinem neuen Code vesuche ich ja so lange wie das entsprechende Object noch nicht gefunden wurde das erste Element in die neue Liste einzufügen und es aus der alten zu löschen.
3.alten Liste: erstes Element löschen(erstes Element null setzten(ist die liste leer oder nicht?...) und first anpassen).
neue Liste: element einfügen(liste noch leer oder nicht?...)

 

[Defqon84]

Hallo,

ok prinzipiell als Ablauf:

1. Setze aktuelles Element auf erstes Element (so schon vorhanden)
2. Solange aktuelles Element nicht den gesuchten Wert entspricht und nicht null ist (spar dir den boolean; die Abfrage im Schleifen-Kopf ist einfacher)
2.a Hänge das aktuelle Element in die neue Liste ein (keine weiteren Abfragen notwendig)
2.b Gehe zum nächsten Element
3. Setze ErstesElement auf nächstes Element des aktuellen Elements
4. Gebe die neu erstellte Liste zurück

Deinen Ansatz kann ich leider nicht in allen Details nachvollziehen; wenn Du die obigen Zeilen in Code umsetzt, dürfte aber:

1. Das Problem gelöst sein
2. Deutlich 'übersichtlicherer' Code entstehen

3. + 4. muss man noch ein wenig aufpassen; stichwort 'Wert wurde überhaupt nicht gefunden'; aber auch das ist einfach (nach Ausführung des Schleifenkörpers) lösbar (Prüfung des aktuellen Elements). Auch wenn die gesamte Ursprungsliste gelöscht wurde muss man noch etwas aufpassen (letztes Element der Liste)

Viele Grüße

 

[Waterman]

    public DoubleLinkedList split(Object o){
        DoubleLinkedList neu= new DoubleLinkedList();
        Element actual = first;
        boolean b = false;
        while(actual!=null && actual.getContent().equals(o)){ //1 Bedingung in while schleife
                if(neu.first==null){ //Falls die neue Liste noch leer ist first last anpassen
                    neu.first=neu.last=actual;
                    neu.size++;
                }else{ //Falls die neue Liste nicht mehr Leer ist actual am Kopf anfügen und first neu setzen
                    actual.setNext(neu.first);
                    neu.first.setPrev(actual);
                    neu.first=actual;
                    neu.size++;
                }
                /* if(first!=null){
                    first=first.getNext();
                    if(first!=null){
                        first.setPrev(null);
                        size--;
                    }else{
                        last=null;
                        size--;
                    }
                }*/ // Wenn ich das hier nicht mache ist dann nicht die Struktur der alten Liste im Eimer ?
                actual=actual.getNext();
        }
        return neu;
    }

Was ich jetzt geändert habe ist das mit der while-Schleife+Bedingung und das ich jetzt nicht mehr den Inhalt eines Element speichere und in der neuen List in ein neues Element einfüge sonder das komplette Element neu zuweise. Aber lösche ich dadurch wirklich das Element in der alten Liste und ist deren Funktionalität noch vorhanden (First zeigt auf das erste Element das noch übrig ist)?
Vielleicht könntest du mir ja einen Code zeigen damit ich es besser verstehe ?

viele Grüße

 

[Waterman]

Ok habe die Aufgabe jetzt gelöst.

Lösung:

    public DoubleLinkedList split(Object o){
        DoubleLinkedList neu= new DoubleLinkedList();
        Element actual = first;
        while(actual!=null && !actual.getContent().equals(o)){
                if(neu.first==null){ //Falls die neue Liste noch leer ist first last anpassen
                    neu.first=neu.last=actual;
                    neu.size++;
                }else{
                    neu.last=actual;
                    neu.size++;
                }
                if(actual.getNext()==null){
                    first=last=null;
                }else{
                    first=actual.getNext();
                }
                actual=actual.getNext();
        }
        if(actual!=null && neu.size>0){
            neu.last.setNext(null);
            first.setPrev(null);
        }
        return neu;
    }