Knoten-Reihenfolge einer LinkedList invertieren

Hallo,

ich habe eine selbstgeschriebene Klasse List und für die Knoten die Klasse ListNode entworfen. In der Klasse ListNode soll jetzt die Methode funktionale Methode ListNode<E> invert() implementiert werden. Diese Methode gibt alle Elemente der Liste in umgedrehter Reihenfolge zurück. Aus der Liste mit den Elementen 1,2,3 soll also die Liste 3,2,1 werden.

Auch in der List-Klasse wurde die invert(), allerdings ohne Rückgabetyp, implementiert, die den head der Liste die invert()-Methode von ListNode aufrufen lässt. Rufe ich in einer Testklasse mittels list.invert() diese Methode auf, bleibt die Reihenfolge der Elemente jedoch unverändert.

Liste:
Java:
public class List<E> {
      
      protected ListNode<E> head = null;

      public List(E value) {
        head = new ListNode(value, null);
      }

      public List() {
      }

      public void addFirst(E e) {
        if (isEmpty()) {
          head = new ListNode(e); // neuer Head-Knoten.
        } else {
          head = head.addFirst(e);
        }
      }
      
      public void invert() {
          head.invert();
      }


    }
Java:
public class ListNode<E> {
    
    public E value;
    public static int counter = 0;
    
    public ListNode<E> next = null;

    public ListNode(E value, ListNode<E> n) {
        this.value = value;
        next = n;
    }

    public ListNode(E value) {
        this.value = value;
    }

    
    public E getHead() {
        return value;
    }

    
    public ListNode<E> getTail() {
        return next;
    }

    
    public ListNode<E> addFirst(E value) {
        return new ListNode<>(value, this);
    }

    

    
    ListNode<E> invert(){
        if (getTail() == null) {
            return this.addFirst(value);
        } else {
            return getTail().invert();
        }
    }
}
Wieso funktioniert diese invert()-Methode nicht?

Vielen Dank für Eure Hilfe!!
 
Ohne mir jetzt die Funktionsweise im Detail angesehen zu haben: die Methode invert gibt etwas zurück, das Du nirgends zuweist.
 
Danke! Das war mir bis jetzt noch nicht bewusst. Jetzt weiß ich wenigstens, dass ich auf der falschen Fährte war. Ich habe es jetzt eine Stunde lang mit verschiedenen Ansätzen versucht, musste es jedoch immer wieder verwerfen, weil es nicht funktioniert hat. Wärst Du oder jemand anderes bitte so nett, mir etwas auf die Sprünge zu helfen?
 
Du hast verschiedene Möglichkeiten. Die einfachste wäre parallel beim durchgehen der Liste eine neue Liste zu erstellen (temporäre Head variable der neuen Liste mitführen) und das jeweilige Element der alten Liste an den Anfang der neuen Liste einzufügen. Am Ende weisst du dann head = tempHead zu.

Eine andere Möglichkeit wäre die Liste mit 3 temporären Referenzen (vorheriges Element, aktuelles Element, nächstes Element) durchzugehen und jedes next feld auf das vorherige Feld zu setzen. Dabei musst du darauf achten die Objekte am Leben zu erhalten indem du die Referenzen "herumschiebst".

Ich würde das auf Papier mit Pfeilen und Referenzen aufzeichnen dann wird es klarer.
 
Verkettete Listen kann man wunderbar visualisieren:
Code:
Einfach verkettete Liste list mit den Elementen e1, e2 und e3

list 
 | head
 v  
 e1 ---> e2 ---> e3 ---> null
    next    next    next
Wie sieht nun die zu list inverse Liste list' aus?
  1. Falls list leer, dann wie list
  2. Falls list nur ein Element enthält, dann wie list
  3. Falls list mindestens zwei Elemente enthält, dann?
Tja, dann muss man sich das im Detail ansehen:
Code:
Für zwei Elemente wird aus list -> e1 -> e2 -> null    
            offensichtlich list' -> e2' -> e1' -> null

Für drei Elemente wird aus list -> e1 -> e2 -> e3 -> null
            offensichtlich list' -> e3' -> e2' -> e1' -> null
Das hilft Dir jetzt vermutlich nicht direkt weiter. Allerdings: entfernt man das erste Element einer Liste, erhält man wieder eine (ggf. leere) Liste, d. h. man kann jede Liste in ein "erstes Element" (head) und den Rest aufteilen, wobei der Rest selbst wieder eine Liste ist.

Stellen wir die Listen oben mal mit einer Restliste dar, dann spielt es keine Rolle, wie viele Elemente die Liste besitzt: so lange es wenigstens zwei Elemente gibt, sieht die Liste immer so aus: list -> e1 -> Rest -> null.

Jetzt könnte man auf die Idee kommen list' zu erhalten, indem man Rest und e1 einfach vertauscht:
Code:
    list' -> Rest -> e1 -> null
Ersetzt man Rest durch die tatsächlichen Elemente (sagen wir mal e2 -> e3) wird klar, dass es nicht ganz so einfach funktioniert:
Code:
    list' -> e2 -> e3 -> e1 -> null
Warum? Naja, offensichtlich, weil der Rest nicht invertiert wurde. Invertiert man dagegen Rest zu Rest', dann erhält man:
Code:
    list' -> Rest' -> e1 -> null
=>  list' -> e3 -> e2 -> e1 -> null
D. h. um eine verkettete Liste zu invertieren, muss lediglich der Rest der Liste invertiert werden und das ursprünglich erste Element zum letzten Element dieser neuen Liste werden:
Code:
inverse(e1 -> e2 -> ... -> en -> null) = inverse(e2 ->... -> en) -> e1 -> null
    = en -> ... -> e2 -> e1 -> null
Weil die Elemente verkettet sind, reicht es aus, mit dem Kopfelement zu arbeiten. Für eine Liste e1 -> e2 -> ... -> en -> nul, liefert also inverse(e1) das Element en mit en -> ... -> e2 -> e1 -> null. Die Funktion liefert also das Kopfelement der neuen Liste.

Mit diesem Wissen lässt sich das Problem nun sehr einfach und elegant per Rekursion im Code lösen.
 
Vielen Dank für Eure ausführlichen Antworten.
Ich habe die Methoden jetzt entsprechend verändert:
Java:
public List <E> invert() {
         List<E> k = new List<E>();
         head.invert(k);
          return k;
      }
Java:
ListNode<E> invert(List<E> list){

        list.addFirst(value);

        if (getTail() == null) {

            return this;     

        } else {

            return getTail().invert(list);

        }

    }
Dies liefert tatsächlich auch die invertierte Liste, allerdings habe ich hierzu die neuerstellte Liste k als Parameter übergeben, obwohl in der Aufgabenstellung eine leere Parameterliste gefordert ist.
Kann mir hier vielleicht auch noch jemand weiterhelfen?
 
Nein, den Parameter brauchst Du nicht - der ist über das aktuelle Objekt schon gegeben. Der Funktionsaufruf inverse(e1) entspricht also einem Methodenaufruf e1.inverse(). In der Methode musst Du ebenfalls statt getTail().invert(list) einfach nur getTail().invert() aufrufen.

Außerdem stimmt die Logik IMO noch nicht ganz, aber das findest Du schon noch heraus :)
 
Ich glaube ich hatte das anfangs mißverständlich formuliert, aber die Liste soll nicht verändert werden, sondern es soll eine neue Liste mit der invertierten Reihenfolge der Elemente der vorherigen Liste zurückgegeben werden. Das heißt, wenn ich die Methode ohne Liste als Parameter aufrufe, dann müsste doch die invertierte Liste an die ursprüngliche Liste vorne hinzugefügt werden. Es würde nun also keine Kopie der Liste bestehen, sondern die ursprüngliche Liste hätte doppelt so viele Elemente als davor.
Oder übersehe ich etwas?
 
aber die Liste soll nicht verändert werden, sondern es soll eine neue Liste mit der invertierten Reihenfolge der Elemente der vorherigen Liste zurückgegeben werden.
OK, dann muss ListElement#invert einfach mit einer Kopie von this arbeiten.

Code:
e1 -> e2 -> e3 -> null wird zu
e3' -> e2' ->e1' -> null
Gleiches Prinzip: Wenn die Liste nur aus einem Element besteht, iefert invert eine Kopie von this. Ansonsten wird eine Kopie von this an den invertierten Rest gehängt.

Beispiel:
Code:
e1 -> e2 -> e3 -> null

e1: es gibt einen Rest, also e2.invert
  e2: es gibt einen Rest, also e3.invert
    e3: es gibt keinen Rest, also e3' zurückgeben
  e2: invertierter Rest = e3', also Kopie von e2 (this) anhängen, macht e3' -> e2' -> null
e1: invertierter Rest = e3' -> e2', also Kopie von e1 (this) anhängen, macht e3' -> e2' -> e1' -> null
 
Hmm, was hast Du denn für ein insert? Wenn Du ein Insert hast, das immer am Kopf einfügt, dann ist das doch trivial zu lösen:
- neue Liste erzeugen
- Dann Liste durchgehen und bei jedem Node den Wert bei der neuen Liste einfügen.

Also Einfügen von enew bei
head -> e1 -> e2 -> null
muss nur sein:
head -> enew -> e1 -> e2 -> null
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben