Linked Lists:
Linked Lists are a type of ‘Abstract Data Types‘ in Python. These data structures are linear in nature. Linked Lists are different from Lists as Linked Lists are stored in non-contiguous (non-continuous) memory whereas lists, in contrast, are stored in contiguous (continuous) memory blocks. The elements stored in Linked Lists are in the form of ‘Nodes‘. Each node consists of two parts: Data and Pointer to the next node.
Creating a Linked List in Python:
Herein, we will be creating a custom Linked List. Let’s look at the steps below to do that:
- First of all, we will be creating a Node class which will have two parts, Data and Next.
- Then, we will create a Linked List class which will have self.head
- We will also add a magic method ‘__str__’ for the user’s to print their created linked list.
- After creating this, we will add an ‘add_node’ method to our class for users to add nodes to their Linked List.
- Here, we will also create a ‘change’ method that will enable the users to change a specific element in their Linked List with their desired element.
That is how we will create our linked list. Below is the implementation of the above idea:
Python3
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class 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
linked_list = LinkedList('One', 'Two', 'Three')
linked_list.add_node('Four')
linked_list.change(2, 2)
print(linked_list)
|
Output
[[Four] -> [Three] -> [2] -> [One]]
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
from copy import copy
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class 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
linked_list = LinkedList('One', 'Two', 'Three')
linked_list.add_node('Four')
shallow_copy = copy(linked_list)
print('Original Linked List: ', linked_list)
print('Shallow Copied Linked List: ', shallow_copy)
|
Output
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
from copy import deepcopy
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class 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
linked_list = LinkedList('One', 'Two', 'Three')
linked_list.add_node('Four')
deep_copy = deepcopy(linked_list)
print('Original Linked List: ', linked_list)
print('Deep Copied Linked List: ', deep_copy)
|
Output
Original Linked List: [[Four] -> [Three] -> [Two] -> [One]]
Deep Copied Linked List: [[Four] -> [Three] -> [Two] -> [One]]
Differences in Shallow Copy and Deep Copy:
Now, we know how we can shallow copy and deep copy a linked list. When we shallow-copied and deep-copied a linked list in the above examples, no differences were seen in their outputs.
Can we conclude that shallow copy and deep copy are exactly the same?
Absolutely NO, They have differences in them. Let’s look at the differences between them with the help of examples.
Let us take into consideration the example below. Here, we will be performing some operations that will prove to us that shallow copy and deep copy are NOT the same things.
Example:
Python3
from copy import copy, deepcopy
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class 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
linked_list = LinkedList('One', 'Two', 'Three')
shallow_copied_linked_list = copy(linked_list)
deep_copied_linked_list = deepcopy(linked_list)
linked_list.add_node('New_Node')
linked_list.change(3, '1')
print('Original Linked List: ', linked_list)
print('Shallow Copied Linked List: ', shallow_copied_linked_list)
print('Deep Copied Linked List: ', deep_copied_linked_list)
|
Output
Original Linked List: [[New_Node] -> [Three] -> [Two] -> [1]]
Shallow Copied Linked List: [[Three] -> [Two] -> [1]]
Deep Copied Linked List: [[Three] -> [Two] -> [One]]
Here, we can clearly see the difference between the Shallow Copied Linked List and the Deep Copied Linked List
When we added a node to the original Linked List, it did not reflect in either of the copied Linked Lists. After that, when we changed one element in the original Linked List, that change was reflected in the shallow copied Linked List while the deep copied Linked List remained in its initial state. Let’s look at the reason behind this.
The reason behind the difference:
As the definition of shallow copy above states, the nested objects in an object are just referenced by both, the original and shallow copy, rather than completely copying them in another memory location. This means, here, the original Linked List and Shallow Copied Linked List shared the same reference to the nested object. The nested object here is every Node in the Linked List as we have nested the Node object in our Linked List object. That is why, when we changed a particular node in our Linked List, as it is a nested object and shallow copied and original linked list shared the same reference to this object, the change was reflected in shallow copied linked List.
There was no difference seen in the Deep Copied Linked List as deep copying an object copies the whole object (nested objects as well) in a completely different memory location.
So now you might think, what is the difference between shallow copying and referencing an object? Let’s the difference below.
Referencing an object:
The action of one variable pointing to the memory location of an object stored in another variable is called ‘referencing’.
As these variables point to the same memory location, changes made by one variable among these in the object are seen in another variable as well. That simply means that the object is not copied but referenced.
In shallow copy, the objects are copied into other memory locations, but in the case of nested objects, only handles are copied and the elements in it are only referenced. In referencing, nothing is copied but only referenced.
Let’s look at an example to differentiate between shallow copy and referencing:
In the below example, we will be making a linked list. Then, we will create two variables that will shallow copy and reference the created linked list respectively. After this, we will add a node to the original linked list. Finally, we will print all three linked lists, the original linked list, shallow copied linked list, and referenced linked list to see the differences between them.
Below is the implementation of the above idea:
Python3
from copy import copy, deepcopy
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
class 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 = '['
if self.head == None:
llist += ']'
else:
itr = self.head
while itr != None:
llist += '[' + str(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
llist = LinkedList(1, 2, 3, 'Four')
shallowCopiedLinkedList = copy(llist)
referencedLinkedList = llist
llist.add_node('New_Node')
print('Original: ', llist)
print('Shallow Copied: ', shallowCopiedLinkedList)
print('Referenced : ', referencedLinkedList)
|
Output
Original: [[New_Node] -> [Four] -> [3] -> [2] -> [1]]
Shallow Copied: [[Four] -> [3] -> [2] -> [1]]
Referenced : [[New_Node] -> [Four] -> [3] -> [2] -> [1]]
Please Login to comment...