Wie Elemente in einer verknüpften Liste durch Rekursion hinzugefügt werden?

Question

Ich habe eine private rekursive Methode namens "hinzufügen" gemacht, die rekursiv Elemente hinzufügen sollte, aber es funktioniert nicht. Ich weiß, dass Java nicht als Referenz existiert, also wie würde man Elemente rekursiv hinzufügen? Es wäre toll, wenn Sie mir sagen könnten, wo ich falsch liege. Danke

public class linkedIt2 { 
private int length = 0; 
private Node head; 


private class Node { 
    Node next; 
    int data; 
    public Node(int data, Node next) { 
     this.data = data; 
     this.next = next; 
    } 

    public Node(int data) { 
     this.data = data; 
     this.next = null; 
    } 
} 


public linkedIt2() { 
    head = null; 
} 

private void add(Node cur, int data) { 
    if (cur != null) { 
     add(cur.next, data); 
    } else { 
     cur = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    add(this.head, data); 
    length++; 
    return this; 
} 
} 

Answer 1

Das Problem ist, Sie können die Referenz nicht ändern. Die cur.next wird nie geändert, da die Referenzen nach Wert aufgerufen werden. Sie müssen cur.next vor dem Rekursionsaufruf ändern.

Sie müssen das Java-Konzept von "call by value" verstehen, es gibt keinen Aufruf als Referenz. Die Referenzen werden als Wert übertragen, also ändern Sie den Referenzparameter selbst, es passiert nichts mit dem ursprünglich verwendeten Objekt. vielleicht: http://javadude.com/articles/passbyvalue.htm macht es klarer.

Eine Lösung: ähnlich Ihre:

Zunächst müssen Sie sicherstellen, dass Köter nicht null ist. Dann können Sie innerhalb der Funktion auf cur.next zugreifen. Wenn es Null ist, beenden Sie die Rekursion, wenn nicht, dann gehen Sie tiefer.

private void add(Node cur, int data) { 
    if (cur.next != null) { 
    add(cur.next, data);  
    } else { 
    cur.next = new Node(data, null); 
    } 
} 

public linkedIt2 insert(int data) { 
    if (this.head == null) { 
    this.head = new Node(data, null); 
    } else { 
    add(this.head, data); 
    } 
    length++; 
    return this; 
} 

oder lassen Sie Node die Rekursion durchführen und sich selbst manipulieren. Wie die andere Lösung sagt. Das ist noch schöner.

Answer 2

Ihr Fehler ist hier in der Linie

cur = new Node(data, null); 

Wenn Sie dies nennen es die lokale Variable cur aktualisiert auf einen neuen Knoten zu verweisen, die tatsächlich die Variable Sie die Methode mit aktualisieren nicht dazu führt, genannt . Geben ein einfacheres Beispiel

public static void setToFive(int num) { 
    num = 5; 
    System.out.println(num); //Always prints 5 
} 

public static void test() { 
    int test = 3; 
    setToFive(test); 
    System.out.println(test); //Still prints 3 since only num was updated, not test 
} 

zum ursprünglichen Problem zurück So und fügen Sie Elemente rekursiv könnten Sie so etwas wie

private class Node { 
    //... 
    public void add(int data) { 
     if (next == null) { 
      next = new Node(data, null); 
     } else { 
      next.add(data); 
     } 
} 

dann rufen Sie einfach head.add (Daten) tun und Ihre Längenzähler erhöhen.

Diese Version funktioniert besser, da beim Erstellen des neuen Knotens die Instanzvariable der Klasse so gesetzt wird, dass sie auf sie verweist, und nicht auf eine in der Methode enthaltene Variable.