在java中制作LinkedList的深层副本

Making a deep copy of a LinkedList in java

提问by user3479191

I have a Linked List and I'm trying to create a copy of another Linked List and this copy is a deep copy because the element type is char. Due to the complexity of linked lists, I've tried not to use the add method. My code is shown below. Also I want to recursively add all the elements from some list to my original list but the problem with my implementation is that it only adds the first element in the list and not all of it. Why is this so?

我有一个链表，我正在尝试创建另一个链表的副本，这个副本是一个深层副本，因为元素类型是 char。由于链表的复杂性，我尽量不使用 add 方法。我的代码如下所示。此外，我想递归地将某个列表中的所有元素添加到我的原始列表中，但我的实现的问题是它只添加了列表中的第一个元素，而不是全部。为什么会这样？

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);

回答by Alejandro

In your constructor for CharLinkedListthat accepts another CharLinkedList, you are only using an ifstatement to check if the other linked list has another element, and if it does, it will add it as this.head.next. However, if there are multiple elements, you would need to make that ifstatement into a whileand use the temp variable nodeas an "iterator" of sorts.

在你的构造函数CharLinkedList中接受 another CharLinkedList，你只使用一个if语句来检查另一个链表是否有另一个元素，如果有，它会将它添加为this.head.next。但是，如果有多个元素，则需要将该if语句放入 awhile并将临时变量node用作各种“迭代器”。

Something like this should do:

这样的事情应该做：

    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
    }

That code will traverse the somelinked list and make a copy of each of its elements into the linked list currently being constructed.

该代码将遍历some链表并将其每个元素的副本复制到当前正在构建的链表中。

There are several flaws in your addAllscheme. The most clear way to add all the elements would be to implement a solution similar to what I've wrote above, modifying where to start adding,etc. However, addressing your current style, the addAllthat only takes a CharLinkedList is good, and correctly calls the recursive addAllwith the additional parameters, however in that other addAllyou are checking

你的addAll计划有几个缺陷。添加所有元素的最明确的方法是实现一个类似于我上面写的解决方案，修改从哪里开始添加等。但是，解决您当前的风格，addAll只需要一个 CharLinkedList 是好的，并且addAll使用附加参数正确调用递归，但是在其他方面addAll您正在检查

   if(node.next == null)

Even though you are passing it node.nextfrom the previous functionm, which is expected to be nullanyways. Also, you cannot be so sure to always add the 0th element, since this could be a deep recursive call several links into the chain. To continue with this implementation, you can add an additional intparameter keeping track of where you are in the list, or an additonal Nodeparameter specifying what to add next -- the choice/stye is yours.

即使您是node.next从上一个函数传递它，也应该如此null。此外，您不能确定总是添加第 0 个元素，因为这可能是链中多个链接的深度递归调用。要继续此实现，您可以添加一个附加int参数来跟踪您在列表中的位置，或者添加一个附加Node参数指定接下来要添加的内容 - 选择/麦粒肿是您的。

Hope this helps

希望这可以帮助

回答by JonK

This seems like an academic exercise to me (otherwise I would expect you to be using a LinkedList<Character>from the Java Collections Framework), so I'm not going to post a completed method for you. Instead I'll try and steer you towards you creating a working deep copy implementation for yourself.

这似乎是一个学术活动，我（否则我也希望你用是LinkedList<Character>从Java集合框架），所以我不打算发布一个完整的方法为您服务。相反，我会尝试引导您为自己创建一个有效的深拷贝实现。

First off - I wouldn't use recursion to copy your list. If you do, you're likely to run into a StackOverflowErroras your list gets larger and larger (admittedly, it won't be a problem for a three-element list). Secondly, rather than having a constructor that returns a deep copy of the CharLinkedListthat you give it, I would instead override Object's clone()method (that's what it's for after all).

首先 - 我不会使用递归来复制您的列表。如果你这样做了，StackOverflowError当你的列表变得越来越大时，你很可能会遇到 a （诚​​然，对于三元素列表来说这不是问题）。其次，与其让构造函数返回CharLinkedList你给它的 的深层副本，不如覆盖Object的clone()方法（毕竟这就是它的用途）。

How would you copy each element into your cloned list?

您将如何将每个元素复制到您的克隆列表中？

Well, you already know how large your list is, you're storing that in in your sizeattribute. You can use this value as the upper bound of a forloop, in which you would copy each list element in sequence.

好吧，您已经知道您的列表有多大，您将它存储在您的size属性中。您可以将此值用作for循环的上限，在该循环中您将按顺序复制每个列表元素。

Because your CharLinkedListclass only maintains a reference to your headelement, you would need to maintain a reference to the currentNodeoutside of your loop, otherwise you'd lose your reference to the next element after each iteration.

因为您的CharLinkedList类只维护对head元素的引用，所以您需要维护对当前Node循环外部的引用，否则每次迭代后都会丢失对下一个元素的引用。

In essence, you want something like this 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();
}

Once you're done, return newList, and don't forget to document that your clone()method returns a deep cloneinstead of a shallow clone. Why? Because it's a good habit to get into.

完成后，return newList不要忘记记录您的clone()方法返回的是深克隆而不是浅克隆。为什么？因为进入是一个好习惯。

Finally, don't forget to take a look at the Java Collections Framework, which already contains an implementation of LinkedListthat you can read through the source code for.

最后，不要忘记查看Java Collections Framework，它已经包含一个实现LinkedList，您可以阅读其源代码。