Passing values between two doubly linked lists in python

Question

I would like to pass a value of my doubly linked list into a new, empty doubly linked list so that I can work on sorting and removing nodes in DLL without changing my core one.

Here's how it looks like:

dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList      #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display()                  #contents of dllToBeSorted here: 0 1 2 3 4 
newDoublyLinkedList.display()            #contents of newDoublyLinkedList here: 0 1 2 3 4 

But when I try to display values, both of DLLs are the same. I don't know why this is happening, because this method works on usual variables (strings, ints and whatnot) but here for some reason it changes both of my DLLs.

I'm putting below my whole executable code:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.start_node = None

    def insertToEmptyList(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node

    def insertToEnd(self, data):
        if self.start_node is None:
            new_node = Node(data)
            self.start_node = new_node
            return
        n = self.start_node
        while n.next is not None:
            n = n.next
        new_node = Node(data)
        n.next = new_node
        new_node.prev = n

    def display(self):
        if self.start_node is None:
            print(" ")
            return
        else:
            n = self.start_node
            while n is not None:
                print(n.item, end=" ")
                n = n.next
            print("\n")

    def searchNode(self, data):
        if self.start_node is None:
            print("0")
            return
        else:
            n = self.start_node
            counter = 0
            while n is not None:
                if n.item == data:
                    counter += 1
                n = n.next
            print(counter)

    def sortList(self):
        if self.start_node is not None:
            n = self.start_node
            while n.next is not None:
                index = n.next
                while index is not None:
                    if n.item > index.item:
                        temp = n.item
                        n.item = index.item
                        index.item = temp
                    index = index.next
                n = n.next

    def removeDuplicates(self):
        if self.start_node is not None:
            n = self.start_node
            while n is not None:
                index = n.next
                while index is not None:
                    if n.item == index.item:
                        temp = index
                        index.prev.next = index.next
                        if index.next is not None:
                            index.next.prev = index.prev
                        temp = None
                    index = index.next
                n = n.next

newDoublyLinkedList = DoublyLinkedList()
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(3)
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(4)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(2)
newDoublyLinkedList.insertToEnd(3)
    
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList      #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display()                  #contents of dllToBeSorted here: 0 1 2 3 4 
newDoublyLinkedList.display()            #contents of newDoublyLinkedList here: 0 1 2 3 4 

Answer 1

This is because you are working on 2 different variables that point to the same data structure (https://www.geeksforgeeks.org/copy-python-deep-copy-shallow-copy/). Overriding copy in DoublyLinkedList should do the trick.

def __copy__(self):
    newList = DoublyLinkedList()
    # add all data from self to newList
    return newList

So your code would become:

dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList.copy()      #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display()                  #contents of dllToBeSorted here: 0 1 2 3 4 
newDoublyLinkedList.display()            #contents of newDoublyLinkedList here: 0 1 2 3 4 

Answer 2

To understand your problem you will have to understand this small example.

my_data = [1,2,3]

def my_func(data):
    data.append(100)
    return data

print("You sent: ", my_data)

# Calling my function to add an element to the list and returning the result
result_data = my_func(my_data)

print("I changed it to: ", result_data)
print("Your original input: ", my_data)

We didn't expected the list passed as an argument to get modified but it got modified. For detailed answer you can read this article

So basically you are performing all the sorting actions on your original lists/items behind the scenes and you are getting same outputs for your display functions.

You can use python lists copy function (or create an implementation for your class)

to make my example work as expected you can call the function my_func using

# result_data = my_func(my_data) Old way
result_data = my_func( my_data.copy() )

Answer 3

I would suggest a different approach.

Make your doubly linked list:

• circular, including a sentinel node. This sentinel node can be instantiated by subclassing DoublyLinkedList from Node.
• iterable, so to ease iteration, printing, searching without repeating code
• to use native sorting as a solution (this is debatable, but at least it will be faster than bubble sort).
• to return a new list when sorting, instead of sorting in-place
• with a constructor that takes optional arguments, with which the list will be populated

Let the Node constructor take optional arguments for its prev/next attributes, and give it an isolate method which detaches it from its neighbors, closing the gap, so those neighbors become eachother's neighbors.

See what this approach brings to your code:

class Node:
    def __init__(self, data=None, prev=None, nxt=None):  # optional arguments
        self.item = data
        # Avoid that any next/prev becomes None. Should always reference a Node
        self.next = nxt or self  # default to referring to itself
        self.prev = prev or self
        # Make consistent
        self.next.prev = self
        self.prev.next = self

    # Method to detach the node from its neighbors
    def isolate(self):
        self.prev.next = self.next
        self.next.prev = self.prev
        self.next = self.prev = self


# Subclassing makes the list a sentinel node.
#   It does not count as a data node, but its next attribute will
#   reference the first node (if any, else itself), and its prev
#   attribute will reference the last node (if any, else itself)
class DoublyLinkedList(Node):  
    def __init__(self, *values): 
        super().__init__()
        for data in values:
            self.insertToEnd(data)

    def insertToFront(self, data):
        Node(data, self, self.next)

    def insertToEnd(self, data):
        Node(data, self.prev, self)

    def __iter__(self):  # This is very useful to have!!
        node = self.next
        while node is not self:
            yield node.item
            node = node.next

    def __repr__(self):
        return " ".join(map(repr, self))
    
    def display(self):  # Not really needed, as 
        print(self)  # ... the list is printable

    def search(self, data):
        # Return the index of first occurrence, -1 if not found:
        return next((i for i, item in enumerate(self) if item == data), -1)

    def sorted(self):
        return DoublyLinkedList(*sorted(self))

    def removeDuplicates(self):
        node = self.next
        while node.next is not self:
            if node.item == node.next.item:
                node.next.isolate()
            else:
                node = node.next

myList = DoublyLinkedList(0, 3, 0, 4, 1, 1, 2 ,3)
print(myList)

mySorted = myList.sorted()
mySorted.removeDuplicates()
print(mySorted)  # 1 2 3 4