title: Java Doubly Linked List Clone Method
body: <p>I'm working on coding some data structures on my own time. I've noticed that the clone method is not copying the list as I expect. I'll post my results underneath the code as the main method is near the bottom of the class. Here is the class I have written so far:</p>
  
  <pre><code>public class DoublyLinkedList&lt;E&gt; implements Cloneable {
      //------------nested Node class------------
      private static class Node&lt;E&gt; {
          private E element;       // reference to stored element
          private Node&lt;E&gt; prev;    // reference to previous element
          private Node&lt;E&gt; next;    // reference to next element
  
      /** The constructor that creates a node */
      public Node(E e, Node&lt;E&gt; p, Node&lt;E&gt; n) {
          element = e;
          prev = p;
          next = n;
      }
  
      // methods
      /** getter for the element */
      public E getElement() {
          return element;
      }
  
      /** getter for previous node in list */
      public Node&lt;E&gt; getPrev() {
          return prev;
      }
  
      /** getter for next node in list */
      public Node&lt;E&gt; getNext() {
          return next;
      }
  
      /** setter for previous node */
      public void setPrev(Node&lt;E&gt; p) {
          prev = p;
      }
  
      /** setter for the next node */
      public void setNext(Node&lt;E&gt; n) {
          next = n;
      }
  } //------------end of nested node class------------
  
  // instance variables of DoublyLinkedList
  private Node&lt;E&gt; header;     // head sentinel
  private Node&lt;E&gt; trailer;    // tail sentinel
  private int size = 0;       // number of elements in list
  
  /** List constructor */
  public DoublyLinkedList() {
      header = new Node&lt;E&gt;(null, null, null);      // create header
      trailer = new Node&lt;E&gt;(null, header, null);   // header precedes trailer
      header.setNext(trailer);                     // trailer follows header
  }
  
  // access methods
  /** Returns the size of the doubly linked list */
  public int getSize() {
      return size;
  }
  
  /** Tests whether the linked list is empty */
  public boolean isEmpty() {
      return size == 0;
  }
  
  /** Returns but does not remove the first element in the list */
  public E first() {
      if (isEmpty()) {
          return null;
      } else {
          return header.getNext().getElement();  // return first node's element
      }
  }
  
  /** Returns but does not remove the last element in the list */
  public E last() {
      if (isEmpty()) {
          return null;
      } else {
          return trailer.getPrev().getElement();  // return last node's element
      }
  }
  
  //update methods
  /** Adds element e to the front of the list */
  public void addFirst(E e) {
      addBetween(e, header, header.getNext());
  }
  
  /** Adds element e to the back of the list */
  public void addLast(E e) {
      addBetween(e, trailer.getPrev(), trailer);
  }
  
  /** Removes and returns the first element of the list */
  public E removeFirst() {
      if (isEmpty()) {
          return null;
      } else {
          return remove(header.getNext());
      }
  }
  
  /** Removes and returns the last element of the list */
  public E removeLast() {
      if (isEmpty()) {
          return null;
      } else {
          return remove(trailer.getPrev());
      }
  }
  
  // private update helpers
  /** Does the heavy lifting for adding an element to the list */
  private void addBetween(E e, Node&lt;E&gt; predecessor, Node&lt;E&gt; successor) {
      // create and link a new node
      Node&lt;E&gt; newest = new Node&lt;&gt;(e, predecessor, successor);
      predecessor.setNext(newest);
      successor.setPrev(newest);
      size++;
  }
  
  /** Does the heavy lifting for removing an element from the list */
  private E remove(Node&lt;E&gt; node) {
      Node&lt;E&gt; predecessor = node.getPrev();
      Node&lt;E&gt; successor = node.getNext();
      predecessor.setNext(successor);
      successor.setPrev(predecessor);
      size--;
      return node.getElement();
  }
  // equals and clone methods
      /** Equals method currently assumes that the list must be of the same
       *  type in order to be equal. This means that a doubly linked list will
       *  not be equal to a circularly linked list or a singly linked list even
       *  if the elements are identical. Because of type erasure in Java, we have
       *  to use Objects and casts to handle any type rather than generics. */
      @SuppressWarnings({ "rawtypes" })
      public boolean equals(Object o) {
          if (o == null) {
              return false;
          }
  
          // at this point, the classes have to be the same.
          if (getClass() != o.getClass()) {
              return false;
          }
  
          DoublyLinkedList other = (DoublyLinkedList) o;  // use non-parameterized type (erasure)
  
          // the size must be the same for them to be equal
          if (size != other.size) {
              return false;
          }
  
          Node walkA = header;                             // traverse primary list
          Node walkB = other.header;                       // traverse secondary list
  
          // We don't want to compare the trailers, so size - 1
          for(int i = 0; i &lt; size; i++) {
              if (!walkA.getElement().equals(walkB.getElement())) {
                  return false; // mismatch
              }
              walkA = walkA.getNext();
              walkB = walkB.getNext();
          }
          return true;             // if we reach this, then they are equal.
      }
  
      /** The clone method that performs a deep clone of the list */
      @SuppressWarnings("unchecked")
      public DoublyLinkedList&lt;E&gt; clone() throws CloneNotSupportedException {
          // always use inherited Object.clone() to create initial copy
          DoublyLinkedList&lt;E&gt; other = (DoublyLinkedList&lt;E&gt;) super.clone(); // safe cast
          if (size &gt; 0) {                      // we need independent node chain
              other.header = new Node&lt;&gt;(null, null, null);
              other.trailer = new Node&lt;&gt;(null, other.header, null);
              other.header.setNext(other.trailer);
              Node&lt;E&gt; walk = header.getNext();   // walk through remainder of original list
              Node&lt;E&gt; otherWalk = other.header;  
              for(int i = 0; i &lt; size; i++) {           // make new node storing same element
                  Node&lt;E&gt; newest = new Node&lt;&gt;(walk.getElement(), null, null);
                  otherWalk.setNext(newest);   // link previous node to this one
                  otherWalk = newest;
                  otherWalk.setPrev(newest);   // link node back to the previous one
                  walk = walk.getNext();
              }
          }
          return other;
      }
  
      /** Test driver for the circularly linked list class */
      @SuppressWarnings({ "rawtypes", "unchecked" })
      public static void main(String args[]) {
          DoublyLinkedList theList = new DoublyLinkedList();
          DoublyLinkedList clonedList;
          theList.addFirst(1);
          theList.addFirst(2);
          theList.addLast(3);
          try {
              clonedList = theList.clone();
              System.out.println("Original List values");
              while(theList.first() != null) {
                  System.out.println(theList.removeFirst());
              }
  
              System.out.println("Cloned List values");
              while(clonedList.first() != null) {
                  System.out.println(clonedList.removeFirst());
              }
              System.out.println(theList.equals(clonedList));
          } catch (CloneNotSupportedException e) {
              System.err.println("I AM ERROR: List didn't clone.");
              e.printStackTrace();
          }
      }
  
  } //------------ end of doubly linked list class ------------
  </code></pre>
  
  <p>The main method in this class is just for testing. It should be pretty straightforward. However, whenever I run this code, I get the following result:
  Original List values
  2
  1
  3
  Cloned List values
  2
  2
  2
  true</p>
  
  <p>I'm not sure why the Cloned List values are not the same as those in the original list. I tried changing the 2 in the code to a 4 to see if I would get three 4s out of my cloned list, and indeed I did. Perhaps the list is not walking and grabs the element at the front of the list n times.</p>
  
  <p>Do any of you see my mistake?</p>