Copying a Linked List in Python
Now that we have done with our introduction part, let’s begin with our main topic: ‘How do we copy Linked Lists?’ In this section, we will have a look at two types of copying, Shallow and Deep copy. Also, we’ll look at the implementation of functions on Linked Lists which we use for shallow copy and deep copy in Python. Finally, we’ll look at the differences between deep-copied linked lists and shallow-copied linked lists with the help of examples.
What is a Shallow Copy?
In Shallow Copy, the object is copied into another variable but nested objects are just referenced. When we have nested lists in a list, those nested list objects are copied but the elements inside it are only referenced and not wholly copied. That means, the original object and the copied object reference the same nested object elements. That is why changes made by one object among the original and copied object in the elements of the nested object will be seen in the other object as well.
What is Deep Copy?
In Deep Copy, the objects are copied completely. That means, nested objects are copied into separate memory locations rather than just referencing them. That means changes made in the elements of the nested object by the original object will NOT be seen in copied object and vice versa.
Copy Method in Python involves two functions:
- copy.copy() function (Used in Shallow copy)
- copy.deepcopy() function (Used in Deep copy)
Shallow Copying a Linked List using copy.copy() Function:
Herein, we will talk a little about the copy module and copy.copy() function
Copy Module:
Copy module has two functions to copy objects in Python. It provides functions to shallow copy and deep copy objects in Python.
copy.copy() Function: copy.copy() function is used for shallow copying of an object. Shallow copying of any object can be easily done with the copy.copy() function.
Now as we know the copy module and the copy.copy() function, we will look at how we can implement it on our linked list.
First of all, we will import copy module. Then we will create a deque object to use as our Linked List and store it in our variable. Finally, we’ll create a variable and use the copy.copy() function with the linked list variable as its parameter.
Below is an example that shows us how to do that.
Python3
# importing copy function from copy modulefrom copy import copyclass Node: def __init__(self, data, next = None): self.data = data self.next = nextclass LinkedList: def __init__(self, *args): self.head = None for arg in args: node = Node(data = arg, next = self.head) self.head = node def __str__(self): llist = '[' itr = self.head if itr == None: llist += ']' else: while itr != None: llist += f'[{itr.data}]' if itr.next != None: llist += ' -> ' itr = itr.next llist += ']' return llist def add_node(self, data): new_node = Node(data, next = self.head) self.head = new_node def change(self, index, with_element): itr = self.head if itr == None: return '[]' else: i = 0 while i <= index: if i == index: itr.data = with_element break else: i += 1 itr = itr.next# creating the Linked Listlinked_list = LinkedList('One', 'Two', 'Three')# adding a new node to the Linked Listlinked_list.add_node('Four')# shallow copying the Linked Listshallow_copy = copy(linked_list)# Printing the Linked Listsprint('Original Linked List: ', linked_list) print('Shallow Copied Linked List: ', shallow_copy) |
Original Linked List: [[Four] -> [Three] -> [Two] -> [One]] Shallow Copied Linked List: [[Four] -> [Three] -> [Two] -> [One]]
Deep copying a Linked List:
Now that we know what is deep copy, let’s see how we can actually deep copy a linked list in Python. Before that, let’s look at what is copy.deepcopy() function.
copy.deepcopy() function: deepcopy() function is present in the copy module. With the help of copy.deepcopy() function, we can deep copy objects in Python.
Let us now look at how we can deep copy a linked list with the help of the examples below.
Herein, we will deep copy our linked list. So, the first step is to import the copy module. Then, we will create a linked list and deep copy it into another variable using copy.deepcopy() function.
Python3
# importing copy function from copy modulefrom copy import deepcopyclass Node: def __init__(self, data, next = None): self.data = data self.next = nextclass LinkedList: def __init__(self, *args): self.head = None for arg in args: node = Node(data = arg, next = self.head) self.head = node def __str__(self): llist = '[' itr = self.head if itr == None: llist += ']' else: while itr != None: llist += f'[{itr.data}]' if itr.next != None: llist += ' -> ' itr = itr.next llist += ']' return llist def add_node(self, data): new_node = Node(data, next = self.head) self.head = new_node def change(self, index, with_element): itr = self.head if itr == None: return '[]' else: i = 0 while i <= index: if i == index: itr.data = with_element break else: i += 1 itr = itr.next# creating the Linked Listlinked_list = LinkedList('One', 'Two', 'Three')# adding a new node to the Linked Listlinked_list.add_node('Four')# deep copying the Linked Listdeep_copy = deepcopy(linked_list)# Printing the Linked Listsprint('Original Linked List: ', linked_list) print('Deep Copied Linked List: ', deep_copy) |
Original Linked List: [[Four] -> [Three] -> [Two] -> [One]] Deep Copied Linked List: [[Four] -> [Three] -> [Two] -> [One]]