在Java中制作LinkedList的深层副本 [英] Making a deep copy of a LinkedList in java

问题描述

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

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?

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

推荐答案

对我来说这似乎是一次学术练习（否则我会希望您使用 LinkedList< Character> technotes / guides / collections / overview.html rel = nofollow noreferrer> Java Collections Framework ），因此我不会为您发布完整的方法。相反，我会引导您帮助您为自己创建一个有效的深度复制实现。

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.

首先-我不会使用递归来复制您的列表。如果这样做的话，当列表越来越大时，很可能会遇到 StackOverflowError （诚然，对于三元素列表而言，这将不是问题） 。其次，与其让构造函数返回您提供的 CharLinkedList 的深层副本，不如覆盖 Object 的 clone（）方法（毕竟就是这样）。

First off - I wouldn't use recursion to copy your list. If you do, you're likely to run into a StackOverflowError as 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 CharLinkedList that you give it, I would instead override Object's clone() method (that's what it's for after all).

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

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

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

因为您的 CharLinkedList 类仅维护对 head 元素的引用，您将需要维护对 current 的引用节点不在循环之外，否则每次迭代后您都会丢失对下一个元素的引用。

Because your CharLinkedList class only maintains a reference to your head element, you would need to maintain a reference to the current Node outside of your loop, otherwise you'd lose your reference to the next element after each iteration.

本质上，您想要一些东西像这样的伪代码：

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

完成后，返回newList ，并且不要忘记记录您的 clone（）方法返回的是深层克隆而不是浅层克隆 >。为什么？ 因为要养成良好的习惯。

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

最后，不要忘了看看 Java集合框架 ，该框架已经包含了 LinkedList ，您可以阅读源代码。

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

这篇关于在Java中制作LinkedList的深层副本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！