Pythonの二重リンクリストの詳細コピー

Question

DoublyLinkedListクラスのディープコピーメソッドの実装に問題があります。深いコピーは元のDLLを参照していないオリジナルの二重リンクリストを返します（浅いコピーとは異なります）。

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 '[' + '<-->'.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 

私の深いコピー方法は浅いコピーを返すようだ：

は、ここで私がこれまで持っているものです。プログラムの出力は、（lnk_lst1内の任意の要素を参照するべきではありませんlnk_lst2以来。）1でなければなりません

は、誰かが私は深いリンクリストのコピーではなく、浅いコピーを生成するために、私の深いコピー方法を変更することができますどのように説明できますか？

私はこのために深いか浅いコピーでpythonの内蔵を使用することはできません。どんな助けもありがとう。

Answer 1

深いコピーを実行するには、埋め込まれたリンクリストをコピーする必要があります。

def deepCopy(lnk_lst): 
    currenthead = lnk_lst.first_node() 
    temp = DoublyLinkedList() 
    while currenthead is not lnk_lst.trailer: 
     if isinstance(currenthead.data, DoublyLinkedList): 
      temp.add_last(deepCopy(currenthead.data)) 
     else: 
      temp.add_last(currenthead.data) 
     currenthead = currenthead.next 
    return temp 

Answer 2

多くの基本的なオブジェクトがtype(obj)(obj)にコピーすることができます。例えば。 dict(dct)またはlist(lst)がコピーを作成します。不変型は同じオブジェクトを返します。それは問題ありません。 int(42)は42であり、str("string")は"string"などである。

以下の解決策はこのようなタイプに限定される。

これを利用して、コピーを作成するタイプのセットにDoublyLinkedListを追加しましょう（ここでは深いコピーですが、最初のネスティングレベルのみ）。 __init__を更新：

def __init__(self, iterable=()): 
    self.header = DoublyLinkedList.Node() 
    self.trailer = DoublyLinkedList.Node() 
    self.header.next = self.trailer 
    self.trailer.prev = self.header 
    self.size = 0 
    for item in iterable: 
     self.add_last(type(item)(item)) 

今、私たちはもはやdeepCopy()を必要としません。

lnk_lst2 = deepCopy(lnk_lst1) 

によって：

lnk_lst2 = DoublyLinkedList(lnk_lst1)