Knoten-Reihenfolge einer LinkedList invertieren

H

hornmarder

Mitglied
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!!
 
mihe7

mihe7

Top Contributor
Ohne mir jetzt die Funktionsweise im Detail angesehen zu haben: die Methode invert gibt etwas zurück, das Du nirgends zuweist.
 
mihe7

mihe7

Top Contributor
Meinst Du List#addFirst? Die Methode wird bei einem invert() nie aufgerufen. Aufgerufen wird ListNode#addFirst.
 
H

hornmarder

Mitglied
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?
 
L

lennero

Bekanntes Mitglied
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.
 
mihe7

mihe7

Top Contributor
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.
 
H

hornmarder

Mitglied
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?
 
mihe7

mihe7

Top Contributor
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 :)
 
H

hornmarder

Mitglied
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?
 
mihe7

mihe7

Top Contributor
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
 
kneitzel

kneitzel

Top Contributor
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
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Y Knoten an einem gegebenen Index aus einer Liste entfernen. Java Basics - Anfänger-Themen 6
Y Wie greift man auf die Knoten in einem Binärbaum zu? Java Basics - Anfänger-Themen 5
J ActionListener von JCheckBox im Knoten von JTree funktioniert nicht Java Basics - Anfänger-Themen 2
S Binärbäume knoten zählen Java Basics - Anfänger-Themen 16
T Collections Methode (Knoten hinzufügen) für Graphen Java Basics - Anfänger-Themen 32
G Binärer Suchbaum Knoten zählen Java Basics - Anfänger-Themen 1
M Dijkstra Algorithmus in Graphen auf mehrere verschiedene Knoten anwenden lassen Java Basics - Anfänger-Themen 11
O Suchbaum Elternknoten finden Level eines Knoten bestimmen Java Basics - Anfänger-Themen 24
O Knoten und Liste verarbeitung Java Basics - Anfänger-Themen 20
E Knoten eines Baumes unter Bedinung zählen Java Basics - Anfänger-Themen 2
R Methoden Entferne alle identische Knoten (Typ String) aus verkettete Liste Java Basics - Anfänger-Themen 8
L Baum Knoten zählen Java Basics - Anfänger-Themen 6
L B+Baum innere Knoten erstellen Java Basics - Anfänger-Themen 3
L Graphen: Anzahl Knoten // Knoten in Array speichern Java Basics - Anfänger-Themen 4
I Erste Schritte Referenz zum Knoten davor, in einer Liste Java Basics - Anfänger-Themen 4
J Max. Anzahl von Knoten im Binärbaum Java Basics - Anfänger-Themen 3
M Werte der Knoten in Binärbaum addieren (iterativ) Java Basics - Anfänger-Themen 6
S Baumstruktur: tiefsten Knoten finden Java Basics - Anfänger-Themen 3
B Methoden BinärBaum als String Knoten löschen Java Basics - Anfänger-Themen 5
J Baum Knoten löschen Java Basics - Anfänger-Themen 10
T Datentypen Knoten Großvater finden? Java Basics - Anfänger-Themen 12
S Methoden Abtrennen ab einem gegebenen Knoten eines Binärbaums Java Basics - Anfänger-Themen 4
M Binärbaum - Problem bei Knoten anhängen / löschen Java Basics - Anfänger-Themen 5
B JTree knoten wird nicht übernommen Java Basics - Anfänger-Themen 4
L BinärTree, Knoten löschen Java Basics - Anfänger-Themen 6
Luk10 Anzahl der Knoten in einem Baum ausgeben! Java Basics - Anfänger-Themen 6
T gebe mir den ersten eltern knoten Java Basics - Anfänger-Themen 3
K verkettete Listen - Klasse Knoten Java Basics - Anfänger-Themen 19
L LinkedList vorgänger Knoten zurück geben Java Basics - Anfänger-Themen 4
H B-Baum: Knoten Position als Parameter oder als Variable im Objekt? Java Basics - Anfänger-Themen 4
D An bestimmten Knoten einer Liste zugreifen Java Basics - Anfänger-Themen 4
S Binärbaum - Klasse Knoten - Methode Suchen Java Basics - Anfänger-Themen 5
M Nachbar von Knoten bestimmen Java Basics - Anfänger-Themen 8
0x7F800000 zwei adjazenzlisten für jeden knoten eines graphen sinnvoll? Java Basics - Anfänger-Themen 17
C Bäume in Java. Knoten in Array speichern Java Basics - Anfänger-Themen 3
G eine Knoten aus einem Baum löschen. [SOLVED] Java Basics - Anfänger-Themen 7
F JTree-Knoten (DefaultMutableTreeNode) formatieren ? Java Basics - Anfänger-Themen 3
Y JTree: ein Knoten als Objekt Java Basics - Anfänger-Themen 2
Q Besitzen zwei Strings identische Buchstaben, nur in anderer Reihenfolge? Java Basics - Anfänger-Themen 10
M Feste Reihenfolge von dem Ablauf von Methoden Java Basics - Anfänger-Themen 7
L Richtige Reihenfolge der Dateien Java Basics - Anfänger-Themen 5
C Werte im Vector in zufällige Reihenfolge bringen Java Basics - Anfänger-Themen 14
C Vector-Inhalt in zufällige Reihenfolge bringen Java Basics - Anfänger-Themen 6
A String in umgekehrter Reihenfolge ausgeben Java Basics - Anfänger-Themen 7
L Reihenfolge Ausgabe Java Basics - Anfänger-Themen 5
J Algorithmus - Strings auf eigene Reihenfolge miteinander vergleichen Java Basics - Anfänger-Themen 4
D TAB Reihenfolge im JSinner Java Basics - Anfänger-Themen 1
RowdyN Methoden Befehle in zufälliger Reihenfolge ausführen lassen Java Basics - Anfänger-Themen 5
B Arrays in Reihenfolge vertauschen Java Basics - Anfänger-Themen 6
J Reihenfolge im Vector lässt sich nicht drehen Java Basics - Anfänger-Themen 9
M Array Reihenfolge umdrehen Java Basics - Anfänger-Themen 9
J Klassen Reihenfolge beim Aufruf von Klassen Java Basics - Anfänger-Themen 1
L zweidimensionales char array reihenfolge ändern ? Java Basics - Anfänger-Themen 2
S Warum muss ich die operationen mit AffineTransform in umgekehrter Reihenfolge ausfuehren..? Java Basics - Anfänger-Themen 4
M Reihenfolge von Testmethoden in JUnit beeinflussen Java Basics - Anfänger-Themen 2
M Ausgabe in falscher Reihenfolge Java Basics - Anfänger-Themen 7
S Vokal Reihenfolge Java Basics - Anfänger-Themen 1
C if Reihenfolge Java Basics - Anfänger-Themen 2
W String von hinten alle drei Zeichen abschneiden und in umgekehrter Reihenfolge ausgeben. Java Basics - Anfänger-Themen 9
F Reihenfolge des Quelltexts Java Basics - Anfänger-Themen 6
S Jede Reihenfolge einer zufällig langen Liste ausprobieren Java Basics - Anfänger-Themen 3
B AffineTransform - Reihenfolge der Operationen Java Basics - Anfänger-Themen 3
B Methoden Logische Reihenfolge in Programmen? Java Basics - Anfänger-Themen 4
D Problem mit Initialisierung und Reihenfolge Java Basics - Anfänger-Themen 10
O Zwingende Reihenfolge von Methoden Java Basics - Anfänger-Themen 33
P Vereinfachte for-Schleife wird in umgekehrter Reihenfolge ausgewertet Java Basics - Anfänger-Themen 7
X Collections Reihenfolge bestimmter Objekte in einer ArrayList verändern Java Basics - Anfänger-Themen 2
S Buttons übereinander legen - Reihenfolge Java Basics - Anfänger-Themen 2
G Zahlen in zufälliger Reihenfolge ausgeben/speichern. Java Basics - Anfänger-Themen 2
R Reihenfolge im Konstruktor der Objekte Java Basics - Anfänger-Themen 13
L Properties Reihenfolge vorgeben Java Basics - Anfänger-Themen 13
N Reihenfolge von Methoden Java Basics - Anfänger-Themen 5
F Reihenfolge in der Events abgearbeitet werden Java Basics - Anfänger-Themen 2
A Wörter umgekehrten Reihenfolge ausgeben Java Basics - Anfänger-Themen 3
A Reihenfolge bei equals() Java Basics - Anfänger-Themen 2
K Reihenfolge Modifikatoren Java Basics - Anfänger-Themen 6
U Zuweisungen - Reihenfolge Java Basics - Anfänger-Themen 9
S Falsche Reihenfolge von Methodenaufrufen Java Basics - Anfänger-Themen 8
G Array Reihenfolge ändern Java Basics - Anfänger-Themen 6
M Reihenfolge von Objekten im Vektor Java Basics - Anfänger-Themen 3
A Liste von Listen mit fester reihenfolge Java Basics - Anfänger-Themen 6
P Frage zu OO (Reihenfolge der Klassen) Java Basics - Anfänger-Themen 2
G Feld in umgekehrter Reihenfolge an zweites Feld übergeben Java Basics - Anfänger-Themen 5
T Reihenfolge von Strings prüfen Java Basics - Anfänger-Themen 3
B Stack mit Strings in zufälliger Reihenfolge füllen Java Basics - Anfänger-Themen 4
K Array umgedrehte Reihenfolge Java Basics - Anfänger-Themen 2
M String Reihenfolge umkehren Java Basics - Anfänger-Themen 2
M Array anders sortieren, aber die Reihenfolge beibehalten Java Basics - Anfänger-Themen 4
V Reihenfolge von Befehlen - hier repaint() zu spät Java Basics - Anfänger-Themen 13
N Zahlen einlesen und in umgekehrter Reihenfolge ausgeben Java Basics - Anfänger-Themen 5
D Array in umgekehrter Reihenfolge Java Basics - Anfänger-Themen 4
A Reihenfolge erfassen Java Basics - Anfänger-Themen 11
A String Zeichen löschen in einer bestimmten Reihenfolge Java Basics - Anfänger-Themen 25
G Zahlen in umgekehrter Reihenfolge ausgeben Java Basics - Anfänger-Themen 6
A Exception Reihenfolge Java Basics - Anfänger-Themen 3
M Sorry,ne blöde Frage Focus setzen und Focus Reihenfolge Java Basics - Anfänger-Themen 15
L Reihenfolge der Methodenaufrufe Java Basics - Anfänger-Themen 6
LetsSebi Methode, die einen arry von objekten speichert in einer datei Java Basics - Anfänger-Themen 6
Abraham42 Prozentsatz einer Zahl mehrmals Java Basics - Anfänger-Themen 2
M Nach einer erstmaligen Eingabe, eine zweite Eingabe nur noch gegen bestätigung möglich Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben