Macht eine Tiefe Kopie einer LinkedList in java

Ich habe eine verkettete Liste und ich bin versucht, zu erstellen eine Kopie von einer anderen Verlinkten Liste und diese Kopie wird eine Tiefe Kopie, da der element-Typ ist char. Aufgrund der Komplexität der verknüpften Listen, die ich ausprobiert habe nicht die add-Methode verwenden. Mein code ist unten dargestellt. Auch will ich rekursiv alle Elemente aus einer Liste zu meiner ursprünglichen Liste, aber das problem mit meiner Umsetzung ist, dass es fügt nur das erste element in der Liste und nicht alle. Warum ist das so?

public class CharLinkedList {

    private static class Node {
        private char info;
        private Node next;


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

    private int size;
    private Node head;


    public CharLinkedList() {
        this.size = 0;
        this.head = null;
    }


    public CharLinkedList(CharLinkedList some) {
        this.size = some.size;
        Node node = some.head;
        this.head = new Node(other.head.info);
        if(node.next != null)
        {
            this.head.next = new Node(node.next.info);
            node = node.next;
            this.head.next.next = new Node(node.next.info);
        }
    }

    public void addAll(CharLinkedList some) {
        if(some == null){
            return;
        }
        if (this.size == 0) {
            Node someNode = new Node(some.get(0));
            this.head = someNode;
        }
        else {
            CharLinkedList.addAll(some, this.head.next);
        }
        this.size++;
    }

    private static void addAll(CharLinkedList some, Node node) {
        if(node.next == null)
        {
            Node someNode = new Node(some.get(0));
            node.next = someNode;
        }
        else {
            CharLinkedList.addAll(some, node.next);
        }

    }



public static void main(String[] args) {
    CharLinkedList l = new CharLinkedList();
    l.add('z');
    l.add('o');
    l.add('m');

    CharLinkedList some = new CharLinkedList(l);
    some.add('b');
    some.add('i');
    some.add('e');
    System.out.println(l);
    System.out.println(some);
    //now i change the state of l and append all of some
    l.set(1,  'p');
    l.addAll(some);
    System.out.println(l);

Warum nutzen Sie nicht die LinkedList kommt das mit den JCF?
Also... hast du dir schon mal diese Arbeit? Es wäre höflich von Ihnen zu akzeptieren, eine Antwort.

InformationsquelleAutor user3479191 | 2014-03-31

3

Scheint dies wie eine Akademische übung für mich (sonst würde ich erwarten, dass Sie mit einem LinkedList<Character> von der Java Collections Framework), so werde ich nicht zu posten, eine abgeschlossene Methode für Sie. Stattdessen werde ich versuchen und Steuern Sie in Richtung Sie die Schaffung einer Arbeitsgruppe deep-copy-Implementierung für sich selbst.

First off - ich würde es nicht verwenden Rekursion, um kopieren Sie Ihre Liste. Wenn Sie das tun, sind Sie wahrscheinlich, um führen Sie in eine StackOverflowError Ihrer Liste größer und größer wird (zugegeben, es wird nicht ein problem sein für ein drei-element-Liste). Zweitens, anstatt einen Konstruktor liefert eine Tiefe Kopie des CharLinkedList dass Sie es geben, ich würde stattdessen überschreiben Object's clone() - Methode (das ist, was es ist, nachdem alle).

Wie würden Sie kopieren Sie jedes element in Ihrem geklonten Liste?

Gut, Sie bereits wissen, wie groß Ihre Liste ist, Sie zu speichern in Ihrem size Attribut. Sie können diesen Wert als die Obergrenze ein for Schleife, in die Sie kopieren Sie jedes element in der Liste in der Reihenfolge.

Weil Ihre CharLinkedList - Klasse stellt nur eine Referenz zu Ihrem Kopf element, Sie würde halten müssen, um einen Verweis auf die aktuellen Node außerhalb der Schleife, sonst würden Sie verlieren Ihre Referenz auf das nächste element nach jeder iteration.

Im wesentlichen, Sie wollen so etwas wie pseudo-code:
```
CharLinkedList newList = new CharLinkedList();
Node currentNode = head;

//There are plenty of other ways to do this, you could also use a while loop 
//checking that next is not null.
for (each element up until size) {
    //You may need to implement getData()
    Node newNode = new Node(currentNode.getData()); 
    newList.add(newNode);
    //You may need to implement getNextNode()
    currentNode = currentNode.getNextNode();
}
```
Sobald Sie fertig sind, return newList, und vergessen Sie nicht, um zu dokumentieren, dass Ihre clone() Methode gibt eine deep clone statt einer shallow clone. Warum? , Denn es ist eine gute Angewohnheit, in zu erhalten.

Schließlich, vergessen Sie nicht, einen Blick auf die Java Collections Framework, die enthält bereits eine Implementierung von LinkedList dass Sie Lesen können, durch den source code für.

Gute Antwort, @JonK. Das einzige, was ich ändern würde, ist, dass der Konstruktor nicht return newList und die addAll Methoden sind void, so gibt es nirgends zu Ihnen zurückkehren.
Danke, obwohl der rest Ihres Kommentars hat mich ein bisschen verwirrt (ich hatte sehr wenig Schlaf in der letzten Nacht, also kann ich einfach nicht mehr klar denken!). Ich bin nicht dafür, diese sollte Hinzugefügt werden, um den Konstruktor, ganz im Gegenteil, dieses sollte nicht werden im Konstruktor, es sollte ein überschreiben von clone(). Der code oben ist nur pseudo-code, habe ich absichtlich nicht geben will, eine funktionierende Implementierung, wie es wäre, die Niederlage der Zweck der Akademische übung.
Das ist der Punkt, den ich übersehen -- ich verpasst hatte, wo Sie sagte der override für clone(). Ja, das wäre eine große override für clone(). Ich habe auch vorgeschlagen, eine Antwort weiter unten, aber ich habe nicht erwähnt nichts über die Verwendung von clone, +1, um Sie

InformationsquelleAutor JonK
0

In Ihrem Konstruktor für CharLinkedList akzeptiert andere CharLinkedList Sie sind nur mit einem if - Anweisung überprüft, ob die verlinkten Liste ist ein weiteres element, und wenn es das tut, wird es fügen Sie es als this.head.next . Jedoch, wenn es mehrere Elemente, die Sie benötigen würde, zu machen, dass if - Anweisung in eine while und verwenden Sie die temp-variable node als "iterator" Art.

Etwas soll dies gerne tun:
```
    Node node = some.head;
    this.head = new Node(some.head.info);
    Node adder = this.head; //keep track of the  adding nodes
    node = node.next; //advance the pointer to the next node
    while(node.next != null) //keep adding to the linked list while there are things to add
    {
        adder.next = new Node(node.info);
        node = node.next; //advance the pointer to the next node
    }
```
Dieser code wird Durchlaufen die some verlinkten Liste und machen Sie eine Kopie von jedem seiner Elemente in der verknüpften Liste, die derzeit gebaut wird.

Gibt es mehrere Fehler in Ihrem addAll Schema. Die meisten klaren Weg, um alle Elemente wäre eine Lösung implementieren, ähnlich zu dem, was ich schon oben schrieb, ändern, wo zu beginnen, hinzufügen,etc. Allerdings, um Ihre aktuellen Stil, die addAll das dauert nur ein CharLinkedList ist gut und richtig, ruft die rekursive addAll mit den zusätzlichen Parametern, jedoch im anderen addAll prüfen Sie
```
   if(node.next == null)
```
Obwohl Sie auf der Durchreise sind es node.next von der vorherigen functionm, die voraussichtlich null sowieso. Außerdem können Sie so sicher sein, fügen Sie immer das 0. element, da dies könnte eine Tiefe rekursiver Aufruf mehrerer links in die Kette. Weiterhin mit dieser Implementierung können Sie eine zusätzliche int parameter die Verfolgung von wo Sie sind in der Liste, oder ein zusätzliches Node parameter, der angibt, was Sie als Nächstes-die Wahl/Schweinestall ist dein.

Hoffe, das hilft

InformationsquelleAutor Alejandro

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.