Linked list with 2 values
Do not miss this exclusive book on Binary Tree Problems. Get it now for free. Show In this article, we will represent an Integer as Singly Linked List and define an addition algorithm to add two integers as Linked Lists. This is used to add very large integers which is not stored in existing data types. Table of Contents:
Introduction to Linked listsLinked lists are a type of data structure that stores data in a dynamically allocated memory space. The data is stored in nodes. Each node has a pointer or reference link that points to the next node. So, a node consists of two components: one to store the required data and another to point to the next node. Hence we can come to a conclusion that linked lists are a collection of nodes. The pointer of the last node always points to 'NULL' indicating the end of the list. The above represented linked list is called a Singly Linked list as a given node has a pointer that points to only one other node i.e. the next node. If a given node of a linked list points to two other nodes i.e.both the previous node and the next node, such a list is called Doubly linked list. Addition of 2 integers as linked listsFor adding two integers as linked lists, the approach used here is given below. AlgorithmThe steps to add two integers as Linked Lists are:
Here, the digits of the numbers are stored in the linked list in reverse order so that addition operation can start from the least significant bit of the numbers. We have made use of the singly linked list here. ImplementationThe below given is the python code to perform this operation. Initializationimport math class node: def __init__(self,value): self.value=value self.next=None class LList: def __init__(self): self.head=NoneFor execution, two classes are defined:
In the class node, the pointers characteristic to the node like self.value and self.next are initialized as the value that is given to be stored in that node and None respectively. The pointer self.value is used to point to the value or data stored in that particular node and the pointer self.next is used to point to the next corresponding node in the linked list and store its address. The following functions are defined under the class LList:
Represent Numbers as Linked Listsdef insertnumber(self): number=int(input("Enter the number: ")) temp=number # to create linked list in reverse power = 1 while( power * 10 < temp): power = power * 10; while temp>0: #get inidividual digits of the number and push it into the linked list digit = math.floor(temp / power) self.push(digit) temp = temp % power power = power / 10
For example, lets take the number to be 123. Iteration 1: Digit=23/10=1 (2 is pushed into the linked list) Iteration 2: Digit=3/1=3 (3 is pushed into the linked list) Since temp=0, the iteration is terminated. Pushing the number into linked listdef push(self,data): new_node = node(data) new_node.next = self.head self.head = new_node
Let's continue with our previous example. Say, 2 and 3 are pushed into the linked list. First, a new node is created with 2 as its data. Then, another node is inserted befor this node and 3 is inserted. So the linked list looks like 3 -> 2 Adding the linked listsdef add(self,list1,list2): carry=0 prev=None temp=None Sum=0 while(list1 is not None or list2 is not None): #If either of the two numbers are short, 0 is taken as the value for the shorter number's digit; #else the respective digits of the two numbers are added l1_data=0 if list1 is None else list1.value l2_data=0 if list2 is None else list2.value Sum=l1_data+l2_data+carry # to re-initialize the values of sum and carry if Sum<10: carry = 0 Sum=Sum else: carry = 1 Sum=Sum%10 #create a new node to store the Sum value temp=node(Sum) if self.head is None: self.head = temp else: prev.next = temp prev = temp #moving the pointer to the next digit if list1 is not None: list1=list1.next if list2 is not None: list2=list2.next
Reverse the resultant linked listdef reverse(self): #To reverse the linked list prev = None current = self.head while(current is not None): next = current.next current.next = prev prev = current current = next self.head = prev
Printing the result#to print the result def printList(self): temp = self.head while(temp): print(temp.value, end=" "), temp = temp.next
Driver codenum1=LList() #creating a linked list to store the addend num2=LList() #creating a linked list to store the augend result=LList() # A linked list to store the result num1.insertnumber() num2.insertnumber() result.add(num1.head,num2.head) result.reverse() result.printList()
ExampleLet the inputs be 1234 and 1. InputEnter the number: 1234 Enter the number: 1The linked lists will be : 4 and 1 are the head nodes of both the linked lists.The addition will take place as follows: Iteration 1: l1_data=4 , l2_data=1Sum=4+1+0 Sum=5 , carry=0 temp= 5 Iteration 2:l1_data=3 , l2_data=0 Sum=3+0+0 Sum=3 , carry=0 temp= 5 -> 3 Iteration 3:l1_data=2 , l2_data=0 Sum=2+0+0 Sum=2 , carry=0 temp= 5 -> 3 -> 2 Iteration 4:l1_data=1 , l2_data=0 Sum=1+0+0 Sum=1 , carry=0 temp= 5 -> 3 -> 2 -> 1 After iteration 4, the nodes of both the linked lists have been traversed. So the iteration is stopped and the result is 5 -> 3 -> 2 -> 1. The linked list result is then reversed to give 1 -> 2 -> 3 -> 5 and it is then printed. Output1235Time and space ComplexityLet m and n be the number of nodes in the linked lists of addend and augend respectively. Since each node is traversed only once, the time complexity is O(M+N). The space complexity is also O(M+N) as the memory is occupied by the two linked lists only and the result is stored in a temporary linked list. By the end of this article at OpenGenus, you will have a clear understanding on what are linked lists and how to add two integers that are represented by linked lists. Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS. |