In this article, we will go through the process of subtracting two large numbers using a linked list. Now you may be asking yourself, why do I need to store a number in a linked list and not in a regular variable? The thing is, variables have ranges, and we cannot store numbers outside those ranges. For example, in Python and C++, the largest possible integer that can get stored in a variable is 4,294,967,295. Because of that, we may need to put large numbers in data structures like LinkedList. A LinkedList is a data structure that stores a sequence of nodes. A node typically contains a value and a reference to the next node.
More like this:
- Find the Number of Occurrences of an Element in the Linked List using Recursion
- Implement Queue using Linked List
- Solve Josephus Problem using Linked List
Using a linked list to subtract two Large numbers
Let’s get back to our problem. Given two large numbers in a LinkedList, we need to subtract them and return the result. In this article, we subtract the smaller number from the larger one. However, we can also easily minus one value from the other in a given order, as we will see later.
The steps to solve the above problem are as follows:
First, we check if one number contains fewer digits than the other. If this is the case, we pad zeroes at the beginning of the smaller number to make the digits of both numbers equal. For example, if list1 contains the number 1562 and list2 stores 193. Then, we need to add a single zero at the start of list2 to make the digits equal, i.e., 0193. Moreover, this padding will make the length of both linked lists the same as they have an equal number of nodes (containing digits as values).
We also follow the convention of storing the larger number in the list1 and the smaller one in the list2. Therefore, if the given list2 contains a larger value, we swap the lists.
Now that we are ready with the preprocessing, the next step is to find the difference. We create two global variables, result and borrow. Borrow is a Boolean variable that keeps track of borrowing while subtracting and is False at the beginning. The result, on the other hand, is a LinkedList that stores the difference between two numbers.
We find the difference by using a recursive function. First, we traverse to the end of both lists. Once we reach the end, we start subtracting digits while keeping track of borrowing.
- If borrow is
true, we subtract one from the current digit (node’s value) of the list1.
diff = list1.value – 1 (if borrow is true) diff = list1.value (if borrow is false)
- Then, we compare diff and the current digit in list2. If diff is greater than or equal to the current node’s value of list2, we only subtract them and set the borrow variable to false.
diff = diff-list2.value
- Otherwise, borrowing is required. Therefore, we calculate the difference in the following way.
diff = 10 + diff-list2.value
- We also set borrow to true because borrowing is done.
- Finally, we add diff to the result list.
Substruction Order
If we want to perform subtraction in a specific order, i.e., subtract list2 from list1, then we calculate the difference in the same way. However, we keep track of the smaller number and add a negative sign accordingly. For example, if list1’s number is smaller than the value in list2, a negative sign gets added to the result.
Implementation of Subtract Two Large Numbers using Linked List
The code is given below.
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
#implementation of linked list
class LinkedList:
def __init__(self):
self.head = None
self.length = 0
#Insert a node at the front of the list
def prepend(self, value):
node = Node(value) #create a node
temp = self.head
self.head = node #make the head point to the new node
self.head.next = temp #make the new head next pointer refer to previous head
self.length += 1 #increment the length
#Insert a node at the end of the list
def insert(self, value):
node = Node(value) #create a node
if self.head == None: #if list is empty insert a node at the start
self.head = node
self.length += 1
else:
temp = self.head
#iterate through the list till last node is found
while temp.next:
temp = temp.next
temp.next = node #adding a new node
self.length += 1
#Return the length of the linked list
def len(self):
return self.length
#print all values of the list
def traverse(self):
temp = self.head
while temp:
print(temp.value, end="\t")
temp = temp.next
print("")
#Add zero at the start of the linked list
def addZero(ll, length):
for i in range(0, length):
zero_node=Node(0)
temp = ll.head
ll.head = zero_node
ll.head.next = temp
return ll
#Set the order of two lists such that the list_1 contains the larger value and list_2 contains the smaller number
def findListOrder(list_1, list_2):
temp_1 = list_1.head
temp_2 = list_2.head
while temp_1 != None:
if temp_2.value > temp_1.value:
return list_2, list_1
if temp_1.value > temp_2.value:
return list_1, list_2
temp_1 = temp_1.next
temp_2 = temp_2.next
return list_1, list_2
def preprocessingFunction(list_1, list_2):
if list_1.len() < list_2.len():
diff = list_2.len()-list_1.len() #find the number of zeroes to be added at the beginning of the smaller list
list_1 = addZero(list_1, diff)
elif list_2.len() < list_1.len():
diff = list_1.len()-list_2.len()
list_2 = addZero(list_2, diff)
#make list_1 the larger number and list_2 the smaller one
list_1 , list_2 = findListOrder(list_1, list_2)
subtractTwoLargeNumber(list_1.head, list_2.head)
borrow = False
result = LinkedList()
#recursive method to find the difference
def subtractTwoLargeNumber(list_1, list_2):
global borrow
global result
if list_1 == None and list_2 == None:
return None
subtractTwoLargeNumber(list_1.next, list_2.next)
if borrow == True:
diff = list_1.value - 1
else:
diff = list_1.value
if diff >= list_2.value:
diff = diff - list_2.value
borrow = False
else:
diff = 10+diff-list_2.value
borrow = True
result.prepend(diff) #add difference at the start of the result linked list
ll1 = LinkedList() #create list_1
ll1.insert(1)
ll1.insert(8)
ll1.insert(6)
ll1.insert(2)
ll2 = LinkedList() #create list_2
ll2.insert(1)
ll2.insert(5)
ll2.insert(3)
print("Linked List 1 contains number:")
ll1.traverse()
print("Linked List 2 contains number:")
ll2.traverse()
#calulating the difference by first calling the preprocessing function that in turns calls the main function for calculating difference, i.e., subtractTwoLargeNumber
preprocessingFunction(ll1, ll2)
print("Result of difference:")
result.traverse()
Output
Linked-List 1 contains number: 1 8 6 2 Linked-List 2 contains number: 1 5 3 Result of difference: 1 7 0 9