How to Deep Clone Doubly Linked List?

Question

I need to write a program that (implementing a doubly linked list):

• Prints out a list of the items in the list from front of the list to end of the list (this is my toArrayFromFirst() method)
• Prints out a list of the items in the list from the end of this to the front of the list (reverse order) (this is my toArrayFromLast() method)
• DeepClones the list (which is my deepClone() method)
• Prints out a list of the items in the copy of the list from front of the list to end of the list.

My issues:

• I think I'm getting code for a Singly Linked List and a Doubly Linked mixed up in my deepClone() method.
• My program is not outputting correctly, and I'm not sure if it's because I'm inserting elements into the list incorrectly, or if I'm displaying the list incorrectly, or if it's both.
• I'm getting this error: "Exception in thread "main" java.lang.CloneNotSupportedException: DLL.DLL" (the error is in this line of code: DLL<E> other = (DLL<E>)super.clone(); (in my deepClone() method)

This is what my code is currently outputting:

List from first to last: Belgium Germany

List from last to first: England Germany France Belgium

(And then I get an error right here when I try to deep clone the list)

This is what I want my code to output:

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

Here is my 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;
    }

}

And here is my 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

You're using more than once these two lines together in your loops:

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

Beside that, you're not updating your DLL size anywhere. So your deepClone doesn't even enter your condition if (size > 0).

Lastly, instead of using super.clone() just create a new DLL and add your values.

Answer 2

I spotted a problem in addFirst(). You should always be setting the 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;
}