如何深度克隆双向链表？

Question

我需要编写一个程序（实现双向链表）：

从列表前面到列表末尾打印列表中的项目列表（这是我的toArrayFromFirst()方法）
打印出列表中的项目列表，从这个列表的末尾到列表的前面（倒序）（这是我的toArrayFromLast()方法）
DeepClones 列表（这是我的 deepClone() 方法）
打印出列表副本中从列表前面到列表末尾的项目列表。

我的问题：

我想我在我的 deepClone() 方法中混合了一个单链表和一个双链表的代码。
我的程序没有正确输出，我不确定是因为我没有正确地将元素插入到列表中，还是我没有正确显示列表，或者两者都是。
我收到此错误："Exception in thread "main" java.lang.CloneNotSupportedException: DLL.DLL"（错误在这行代码中：DLL<E> other = (DLL<E>)super.clone();（在我的 deepClone()方法)

这是我的代码当前输出的内容：

List from first to last: Belgium Germany

List from last to first: England Germany France Belgium

（然后当我尝试深度克隆列表时，这里出现错误）

这是我希望我的代码输出的内容：

List from first to last: Belgium France USA Germany England

List from last to first: England Germany USA France Belgium

Deep cloned list: Belgium France USA Germany England

这是我的 DoublyLinkedList class:

package DLL;

public class DLL<E>
{
    private Node header = null;                         //header sentinel
    private Node trailer = null;                        //trailer sentinel
    private int size = 0;                               //number of elements in list

//nested Node class
private static class Node<E>
{   
    private E element;                              //reference to element stored at this node
    private Node prev;                              //reference to previous node in list
    private Node next;                              //reference to subsequent node in list

    public Node(E e)
    {
        element = e;
    }
    public E getElement()
    {
        return element;
    }       
    public Node<E> getPrev()
    {
        return prev;
    }
    public Node<E> getNext()
    {
        return next;
    }
    public void setPrev(Node<E> p)
    {
        prev = p;
    }
    public void setNext(Node<E> n)
    {
        next = n;
    }
    public void displayNode()
    {
        System.out.println(element + " "); 
    }
}

//returns number of elements in linked list
public int size()
{
    return size;
}

//tests whether linked list is empty
public boolean isEmpty()
{
    return header == null;
}

//adds element e to front of list
public void addFirst(E e)
{
    Node newNode = new Node(e);

    if (isEmpty())
    {
        trailer = newNode;
    }
    else
    {
        size++;
        header.prev = newNode;
        newNode.next = header;
    }
    header = newNode;
}

//adds element e to end of list
public void addLast(E e)
{
    Node newNode = new Node(e);

    if (isEmpty())
    {
        header = newNode;
    }
    else
    {
        size++;
        trailer.next = newNode;
        newNode.prev = trailer;
    }
    trailer = newNode;
}

//removes and returns first element of list
public Node removeFirst()
{
    Node temp = header;

    if (header.next == null)
    {
        trailer = null;
    }
    else
    {
        size--;
        header.next.prev = null;                    //null <-- old next
    }
    header = header.next;
    return temp;
}

//removes and returns last element of list
public Node removeLast()
{
    Node temp = trailer;

    if (header.next == null)
    {
        header = null;
    }
    else
    {
        size--;
        trailer.prev.next = null;                   //old prev --> null
    }
    trailer = trailer.prev;
    return temp;
}

//displays array of strings with elements in order from head to tail
    public void toArrayFromFirst()
    {
        System.out.println("List from first to last: ");
        Node current = header;

        while (current != null)
        {
            current.displayNode();
            current = current.next;
        }
        System.out.println("");
    }

    //displays array of strings with elements in order from tail to head
    public void toArrayFromLast()
    {
        System.out.println("List from last to first: ");
        Node current = trailer;

        while (current != null)
        {
            current.displayNode();
            current = current.prev;
        }
        System.out.println("");
    }

    //displays cloned array with elements in order from head to tail
            public void clonedToArrayFromFirst()
            {
                System.out.println("Deep cloned list: ");
                Node current = header;

                while (current != null)
                {
                    current.displayNode();
                    current = current.next;
                }
                System.out.println("");
            }

    //returns copy of list (deep clone)
    public DLL<E> deepClone() throws CloneNotSupportedException
    {
        DLL other = new DLL<E>();

        if (size > 0)
        {
            other.header = new Node<>(header.getElement());
            Node<E> walk = header.getNext();
            Node<E> otherTrailer = other.header;

            while (walk != null)
            {
                Node<E> newest = new Node<>(walk.getElement());
                otherTrailer.setNext(newest);
                otherTrailer = newest;
                walk = walk.getNext();
            }
        }
        return other;
    }

}

这是我的 main():

package DLL;

public class DLLTest 
{

    public static void main(String[] args) throws CloneNotSupportedException 
    {
        DLL myList = new DLL();
        DLL clonedList = new DLL();

        myList.addFirst("USA");
        myList.addLast("Germany");
        myList.addFirst("France");
        myList.addLast("England");
        myList.addFirst("Belgium");

        myList.toArrayFromFirst();
        myList.toArrayFromLast();

        clonedList = myList.deepClone();
        clonedList.clonedToArrayFromFirst();
    }
}

Answer 1

我在 addFirst() 中发现了一个问题。您应该始终设置 header:

//adds element e to front of list
public void addFirst(E e)
{
    Node newNode = new Node(e, null);

    if (isEmpty())
    {
        trailer = newNode;
    }
    else
    {
        header.prev = newNode;
        newNode.next = header;
    }
    header = newNode;
}

Answer 2

您在循环中不止一次地同时使用这两行：

current = current.getNext();
current = current.next;

除此之外，您不会在任何地方更新 DLL 大小。所以你的 deepClone 甚至没有输入你的条件 if (size > 0).

最后，不要使用 super.clone()，只需创建一个新的 DLL 并添加您的值即可。

如何深度克隆双向链表？

How to Deep Clone Doubly Linked List?

java

clone

list

output