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.
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()
Linked-List 1 contains number: 1 8 6 2 Linked-List 2 contains number: 1 5 3 Result of difference: 1 7 0 9