# Subtract Two Large Numbers using Linked List

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:

## 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

def __init__(self):
self.length = 0

#Insert a node at the front of the list
def prepend(self, value):
node = Node(value) #create a node
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.length += 1
else:
#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):
while temp:
print(temp.value, end="\t")
temp = temp.next
print("")

for i in range(0, length):
zero_node=Node(0)
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):
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
elif list_2.len() < list_1.len():
diff = list_1.len()-list_2.len()

#make list_1 the larger number and list_2 the smaller one
list_1 , list_2 = findListOrder(list_1, list_2)

borrow = False

#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

ll1.insert(1)
ll1.insert(8)
ll1.insert(6)
ll1.insert(2)

ll2.insert(1)
ll2.insert(5)
ll2.insert(3)

ll1.traverse()
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