java - 如何深度克隆双向链表？

Question

我需要编写一个程序(实现双向链表):

• 打印列表中从列表前面到列表末尾的项目列表(这是我的 toArrayFromFirst() 方法)
• 打印出列表中从末尾到列表前面的项目列表(逆序)(这是​​我的 toArrayFromLast() 方法)
• 深度克隆列表(这是我的 deepClone() 方法)
• 从列表前面到列表末尾打印列表副本中的项目列表。

我的问题:

• 我想我在我的 deepClone() 中得到了混合的单链表和双向链表的代码。方法。
• 我的程序无法正确输出，我不确定这是因为我错误地将元素插入到列表中，还是因为我错误地显示了列表，或者两者兼而有之。
• 我收到此错误:“线程“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 类:

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

您在循环中多次使用这两行:

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

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

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