Python 中双向链表的深拷贝

Question

我在为 DoublyLinkedList class 实施深层复制方法时遇到问题。深拷贝应该 return 一个新的、原始的双向链表，它不引用原始 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

我的深拷贝方法似乎是return浅拷贝。程序的输出应该是 1（因为 lnk_lst2 不应该引用 lnk_lst1 中的任何元素。）

谁能解释一下我如何修改我的深拷贝方法来生成链表的深拷贝而不是浅拷贝？

我不能为此使用 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) 将创建一个副本。不可变类型将 return 相同的对象，这很好。 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)

Python 中双向链表的深拷贝

Deep copy of a Doubly Linked List in Python

python

algorithm

linked-list

deep-copy

doubly-linked-list