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

#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
Back to: Data Structure > Data Structure - Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *