title: Deep copy of a Doubly Linked List in Python
body: <p>I'm having trouble implementing a deep copy method for a <code>DoublyLinkedList</code> class. A deep copy is supposed to return a new, original Doubly Linked List that does not reference the original DLL (unlike a shallow copy).</p>
  
  <p>Here's what I have so far:</p>
  
  <pre><code>class EmptyCollection(Exception):
      pass
  
  
  class DoublyLinkedList:
      class Node:
          def __init__(self, data=None, next=None, prev=None):
              self.data = data
              self.next = next
              self.prev = prev
  
          def disconnect(self):
              self.data = None
              self.next = None
              self.prev = None
  
      def __init__(self):
          self.header = DoublyLinkedList.Node()
          self.trailer = DoublyLinkedList.Node()
          self.header.next = self.trailer
          self.trailer.prev = self.header
          self.size = 0
  
      def __len__(self):
          return self.size
  
      def is_empty(self):
          return (len(self) == 0)
  
      def first_node(self):
          if (self.is_empty()):
              raise EmptyCollection("List is empty")
          return self.header.next
  
      def last_node(self):
          if (self.is_empty()):
              raise EmptyCollection("List is empty")
          return self.trailer.prev
  
      def add_first(self, elem):
          return self.add_after(self.header, elem)
  
      def add_last(self, elem):
          return self.add_after(self.trailer.prev, elem)
  
      def add_after(self, node, elem):
          prev = node
          succ = node.next
          new_node = DoublyLinkedList.Node()
          new_node.data = elem
          new_node.prev = prev
          new_node.next = succ
          prev.next = new_node
          succ.prev = new_node
          self.size += 1
          return new_node
  
      def add_before(self, node, elem):
          return self.add_after(node.prev, elem)
  
      def delete(self, node):
          prev = node.prev
          succ = node.next
          prev.next = succ
          succ.prev = prev
          self.size -= 1
          data = node.data
          node.disconnect()
          return data
  
      def __iter__(self):
          if(self.is_empty()):
              return
          cursor = self.first_node()
          while(cursor is not self.trailer):
              yield cursor.data
              cursor = cursor.next
  
      def __str__(self):
          return '[' + '&lt;--&gt;'.join([str(elem) for elem in self]) + ']'
  
      def __repr__(self):
          return str(self)
  
  
  
  
  def deepCopy(lnk_lst):
      currenthead = lnk_lst.first_node()
      temp = DoublyLinkedList()
      while currenthead is not lnk_lst.trailer:
          temp.add_last(currenthead.data)
          currenthead = currenthead.next
      return temp
  
  
  lnk_lst1 = DoublyLinkedList()
  elem1 = DoublyLinkedList()
  elem1.add_last(1)
  elem1.add_last(2)
  lnk_lst1.add_last(elem1)
  elem2 = 3
  lnk_lst1.add_last(elem2)
  lnk_lst2 = deepCopy(lnk_lst1)
  e1 = lnk_lst1.first_node()
  e1_1 = e1.data.first_node()
  e1_1.data = 10
  e2 = lnk_lst2.first_node()
  e2_1 = e2.data.first_node()
  print(e2_1.data) #should print 1
  </code></pre>
  
  <p>My deep copy method seems to return a shallow copy. The output of the program should be 1 (since <code>lnk_lst2</code> should not reference any elements in <code>lnk_lst1</code>.)</p>
  
  <p>Can someone explain how I can modify my deep copy method to produce a deep copy of the linked list and not a shallow copy? </p>
  
  <p>I cannot use python's built in deep or shallow copy for this. Any help would be appreciated.</p>