如何在Java中深度复制双向链表

Question

我在尝试在我的java程序中制作双向链表的深层副本时遇到了相当大的麻烦。

到目前为止我的方法是：

public class DblLinkQueue Implements Queue {

public Object clone() {
    DblLinkQueue copy = null;
    Node currNode, tmp = null;

    try {
        copy = (DblLinkQueue)super.clone();
    } catch (CloneNotSupportedException err) {}   

    for (currNode = mHead.next; currNode.next != mHead; currNode = currNode.next) {

    }
    System.out.println("i: " + i);
    return copy;
}

}

mHead 是我列表中的第一个 Node，并且这个链表也是循环的。

我的 for 循环出了问题，因为它遍历了列表中的所有元素，然后无限地卡在最后一个元素上。

任何帮助将不胜感激！

Answer 1

您的循环结束条件是当前节点之前的节点不是头。我不确定你为什么会有这个，我猜这就是你被卡住的原因。在不知道 Node 类的设计的情况下，我猜测当没有后续节点时，您的 next 成员不会抛出任何类型的迭代异常，因此循环将永远进行（null 节点永远不会与 mHead 具有相同的参考值）。

Answer 2

如果我打算复制一个双向链接列表，我只需迭代该列表，复制每个项目，然后将其附加到一个新列表中。计算出插入/追加和迭代函数，然后复制函数就很简单了。

Answer 3

运行当前列表并将每个节点复制到新列表。在下面的列表中，将“theCurrentQueue”替换为您用于存储当前队列的任何内容。

public Object clone()
{
  Node cloneNode;
  DblLinkQueue returnValue = new DblLinkQueue();

  for (Node currentNode : theCurrentQueue)
  {
    cloneNode = currentNode.clone(); // probabaly need to wrap this in a try catch block.
    returnValue.add(cloneNode);
  }

  return returnValue;
}