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

Question

I am trying to implement a deep copy function that is given a nested doubly linked list of integers (code for DoublyLinkedList at the end). So far, my code doesn't do what it's suppose to even with the deep copy method. I'm not sure what else to try so any pointers would be amazing!

My Code

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

I'm still learning about nodes so I'm not sure if slicing head.data in place of copying is allowed. This is the code I'm using to test. The expected output is 1 but I keep getting 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)

Doulby Linked List 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

This is a nice implementation of a doubly linked list class!

However, the deep copy function has several issues:

• In the first if you are not calling is_empty. The parentheses are missing.

• In the first if block you return the original list lnk_lst. This should never be returned, even when it is empty. Even in that case you need to return a new instance of DoublyLinkedList.

• You call lnk_lst.delete_first, but that mutates the original list. You should not change anything to the original list. Instead use the fact that a DoublyLinkedList is iterable (it implements __iter__) and simply iterate over the values that are in the list.

• The while not isinstance(head.data, DoublyLinkedList) will never enter the block, because this condition is false -- the opposite condition was just found to be true in the previous if condition.

• headcopy = head.data[:] assumes that head.data is a standard list, but this type check was never made. Are you sure you are supposed to also copy standard lists? If that is true, you have a lot more to do, like duplicating dicts, sets, and any other custom object that might be there, and do a deep copy of them, not just a shallow one.

  I find it more likely that the assignment is to deep copy only what is a doubly linked list. If however you need to deep copy anything, then don't try to code that yourself -- it is a pain. Instead use the standard library for that, like copy.deepcopy. But then this whole exercise is useless, as it would also deep copy your doubly linked list. So again, I don't think this assignment is about deep copying standard lists, but only doubly linked lists.

• Your code does not deal with nested doubly linked lists. You can use recursion to do that: the function can be called on data when that data happens to be a doubly linked list.

Here is a working implementation:

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

With this implementation your test will work (if you add one missing statement marked with a comment):

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]