实现无拷贝库的嵌套双向链表的深拷贝功能

Question

我正在尝试实现一个深度复制函数，该函数给出了一个嵌套的整数双向链表（最后是 DoublyLinkedList 的代码）。到目前为止，即使使用深拷贝方法，我的代码也没有达到预期的效果。我不确定还能尝试什么，所以任何指示都会很棒！

我的代码

def deep_copy_linked_list(lnk_lst):
    if lnk_lst.is_empty:
        return lnk_lst
    head = lnk_lst.delete_first()
    temp = DoublyLinkedList()
    while not lnk_lst.is_empty():
        if isinstance(head.data, DoublyLinkedList):
            while not isinstance(head.data, DoublyLinkedList):
                headcopy = head.data[:]
                temp.add_last(headcopy)
        else:
            temp.add_last(head.data)
        head = head.next
    return temp

我仍在学习节点，所以我不确定是否允许切片 head.data 代替复制。这是我用来测试的代码。预期输出为 1，但我一直得到 10。

elem1 = DoublyLinkedList()
elem1.add_last(1)
elem1.add_last(2)
lnk_lst1.add_last(elem1)
elem2 = 3
lnk_lst1.add_last(elem2)

lnk_lst2 = deep_copy_linked_list(lnk_lst1)

e1 = lnk_lst1.header.next
e1_1 = e1.data.header.next
e1_1.data = 10
e2 = lnk_lst2.header.next
e2_1 = e2.data.header.next
print(e2_1.data)

杜比链表class

class DoublyLinkedList:
    class Node:
        def __init__(self, data=None):
            self.data = data
            self.next = None
            self.prev = None

        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 add_after(self, node, val):
        new_node = DoublyLinkedList.Node(val)
        prev_node = node
        next_node = prev_node.next
        prev_node.next = new_node
        new_node.prev = prev_node
        next_node.prev = new_node
        new_node.next = next_node
        self.size += 1
        return new_node

    def add_first(self, val):
        return self.add_after(self.header, val)

    def add_last(self, val):
        return self.add_after(self.trailer.prev, val)

    def add_before(self, node, val):
        return self.add_after(node.prev, val)

    def delete_node(self, node):
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node
        self.size -= 1
        data = node.data
        node.disconnect()
        return data

    def delete_first(self):
        if(self.is_empty() == True):
            raise Exception("List is empty")
        return self.delete_node(self.header.next)
 
    def delete_last(self):
        if(self.is_empty() == True):
            raise Exception("List is empty")
        return self.delete_node(self.trailer.prev)

    def __iter__(self):
        cursor = self.header.next
        while(cursor is not self.trailer):
            yield cursor.data
            cursor = cursor.next

    def __repr__(self):
        return "[" + " <--> ".join([str(elem) for elem in self]) + "]"

Answer 1

这是双向链表的一个很好的实现class！

但是，深拷贝功能有几个问题：

在第一个 if 中，您没有调用 is_empty。括号不见了。
在第一个if块中你return原来的列表lnk_lst。这永远不应该被 return 编辑，即使它是空的。即使在那种情况下，您也需要 return DoublyLinkedList.
的新实例
您调用 lnk_lst.delete_first，但这会改变原始列表。您不应该对原始列表进行任何更改。而是使用 DoublyLinkedList 是可迭代的（它实现了 __iter__）这一事实，并简单地迭代列表中的值。
while not isinstance(head.data, DoublyLinkedList)永远不会进入block，因为这个条件为假——正好相反的条件在之前的if条件中被发现为真。
headcopy = head.data[:] 假定 head.data 是一个标准列表，但这种类型检查从未进行过。您确定还应该复制标准列表吗？如果那是真的，你还有很多事情要做，比如复制字典、集合和任何其他可能存在的自定义对象，并对它们进行 deep 复制，而不仅仅是复制浅一个。

我发现赋值更有可能是深拷贝仅什么是双向链表。但是，如果您需要深度复制 任何东西，那么不要尝试自己编写代码——这很痛苦。而是为此使用标准库，例如 copy.deepcopy。但是这整个练习是无用的，因为它也会深度复制你的双向链表。再说一次，我不认为这个作业是关于深度复制标准列表的，而只是双向链表。
您的代码不处理嵌套双向链表。您可以使用递归来做到这一点：当 data 恰好是双向链表时，可以在 data 上调用该函数。

这是一个有效的实现：

def deep_copy_linked_list(lnk_lst):
    copy_lst = DoublyLinkedList()
    # You should not mutate the original list. Just iterate it...
    for data in lnk_lst:
        if isinstance(data, DoublyLinkedList):
            # Use recursion to copy nested lists
            data = deep_copy_linked_list(data)
        copy_lst.add_last(data)
    return copy_lst

使用此实现，您的测试将起作用（如果您添加一个带有注释标记的缺失语句）：

elem1 = DoublyLinkedList()
elem1.add_last(1)
elem1.add_last(2)

lnk_lst1 = DoublyLinkedList()  # <--- this was missing
lnk_lst1.add_last(elem1)
lnk_lst1.add_last(3)

lnk_lst2 = deep_copy_linked_list(lnk_lst1)

e1 = lnk_lst1.header.next
e1_1 = e1.data.header.next
e1_1.data = 10
e2 = lnk_lst2.header.next
e2_1 = e2.data.header.next

print(e2_1.data)  # 1
print(lnk_lst1)  # [[10 <--> 2] <--> 3]
print(lnk_lst2)  # [[1 <--> 2] <--> 3]

实现无拷贝库的嵌套双向链表的深拷贝功能

Implement deep copy function for nested doubly linked list without copy library

python

linked-list

deep-copy

doubly-linked-list