Task back to top Large Integers addition using Linked Lists The largest value of an integer number in any programming language is limited by the number of bits used to represent the integer. However,...

Addition/.DS_Store
__MACOSX/Addition/._.DS_Store
Addition
in/.myfile.txt.swp
Addition
in/.DS_Store
__MACOSX/Addition
in/._.DS_Store
Addition
in/LinkedListATN.class
public synchronized class LinkedListATN {
LinkedListATN$node head1;
LinkedListATN$node head2;
LinkedListATN$node result;
int ca
y;
LinkedListATN$node cur;
public void LinkedListATN();
void printlist(LinkedListATN$node);
void push(int, int);
void addsamesize(LinkedListATN$node, LinkedListATN$node);
void propogateca
y(LinkedListATN$node);
int getsize(LinkedListATN$node);
void addlists();
public static void main(String[]);
}
Addition
in/LinkedListATN$node.class
synchronized class LinkedListATN$node {
int val;
LinkedListATN$node next;
public void LinkedListATN$node(LinkedListATN, int);
}
Addition/.classpath

    
    
    
Addition/.settings/org.eclipse.jdt.core.prefs
eclipse.preferences.version=1
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
org.eclipse.jdt.core.compiler.compliance=1.8
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
org.eclipse.jdt.core.compiler.debug.localVariable=generate
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
org.eclipse.jdt.core.compiler.problem.assertIdentifier=e
o
org.eclipse.jdt.core.compiler.problem.enumIdentifier=e
o
org.eclipse.jdt.core.compiler.source=1.8
Addition/.project

     Addition
    
    
    
    
        
             org.eclipse.jdt.core.javabuilde
            
            
        
    
    
         org.eclipse.jdt.core.javanature
    
Addition/myfile.txt
12345
12345
__MACOSX/Addition/._myfile.txt
Addition/src/.DS_Store
__MACOSX/Addition/src/._.DS_Store
Addition/src/LinkedListATN.java
Addition/src/LinkedListATN.java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class LinkedListATN {
    class node  
    { 
        int val; 
        node next; 
  
        public node(int val)  
        { 
            this.val = val; 
        } 
    } 
      
    
 Function to print linked list 
    void printlist(node head)  
    { 
        while (head != null)  
        { 
            System.out.print(head.val + " "); 
            head = head.next; 
        } 
    } 
  
    node head1, head2, result; 
    int ca
y; 
  
    /* A utility function to push a value to linked list *
    void push(int val, int list)  
    { 
        node newnode = new node(val); 
        if (list == 1)  
        { 
            newnode.next = head1; 
            head1 = newnode; 
        }  
        else if (list == 2)  
        { 
            newnode.next = head2; 
            head2 = newnode; 
        }  
        else 
        { 
            newnode.next = result; 
            result = newnode; 
        } 
  
    } 
  
    
 Adds two linked lists of same size represented by 
    
 head1 and head2 and returns head of the resultant  
    
 linked list. Ca
y is propagated while returning  
    
 from the recursion 
    void addsamesize(node n, node m)  
    { 
        
 Since the function assumes linked lists are of  
        
 same size, check any of the two head pointers 
        if (n == null) 
            return; 
  
        
 Recursively add remaining nodes and get the ca
y 
        addsamesize(n.next, m.next); 
  
        
 add digits of cu
ent nodes and propagated ca
y 
        int sum = n.val + m.val + ca
y; 
        ca
y = sum / 10; 
        sum = sum % 10; 
  
        
 Push this to result list 
        push(sum, 3); 
  
    } 
  
    node cur; 
  
    
 This function is called after the smaller list is  
    
 added to the bigger lists's sublist of same size.  
    
 Once the right sublist is added, the ca
y must be  
    
 added to the left side of larger list to get the  
    
 final result. 
    void propogateca
y(node head1)  
    { 
        
 If difference number of nodes are not traversed, add ca
y 
        if (head1 != cur)  
        { 
            propogateca
y(head1.next); 
            int sum = ca
y + head1.val; 
            ca
y = sum / 10; 
            sum %= 10; 
  
            
 add this node to the front of the result 
            push(sum, 3); 
        } 
    } 
  
    int getsize(node head)  
    { 
        int count = 0; 
        while (head != null)  
        { 
            count++; 
            head = head.next; 
        } 
        return count; 
    } 
  
    
 The main function that adds two linked lists  
    
 represented by head1 and head2. The sum of two  
    
 lists is stored in a list refe
ed by result 
    void addlists()  
    { 
        
 first list is empty 
        if (head1 == null)  
        { 
            result = head2; 
            return; 
        } 
  
        
 first list is empty 
        if (head2 == null)  
        { 
            result = head1; 
            return; 
        } 
  
        int size1 = getsize(head1); 
        int size2 = getsize(head2); 
  
        
 Add same size lists 
        if (size1 == size2)  
        { 
            addsamesize(head1, head2); 
        }  
        else 
        { 
            
 First list should always be larger than second list. 
            
 If not, swap pointers 
            if (size1 < size2)  
            { 
                node temp = head1; 
                head1 = head2; 
                head2 = temp; 
            } 
            int diff = Math.abs(size1 - size2); 
  
            
 move difference number of nodes in first list 
            node temp = head1; 
            while (diff-- >= 0)  
            { 
                cur = temp; 
                temp = temp.next; 
            } 
  
            
 get addition of same size lists 
            addsamesize(cur, head2); 
  
            
 get addition of remaining first list and ca
y 
            propogateca
y(head1); 
        } 
            
 if some ca
y is still there, add a new node to  
            
 the front of the result list. e.g. 999 and 87 
            if (ca
y > 0) 
                push(ca
y, 3); 
          
    } 
  
    
 Driver program to test above functions 
    public static void main(String args[]) 
    { 
        LinkedListATN list = new LinkedListATN(); 
        list.head1 = null; 
        list.head2 = null; 
        list.result = null; 
        list.ca
y = 0; 
        int choice;
        BufferedReader reader;
        
        
        System.out.println("=========== Large integer addition ==========");
        System.out.println("| Enter 1 to Read numbers from File         |");
        System.out.println("| Enter 2 to Display integers stored in SILL|");
        System.out.println("| Enter 3 to Display addition result        |");
        System.out.println("| Enter 4 to Exit                           |");
        System.out.println("=============================================");
        Scanner sc=new Scanner(System.in);
        choice=sc.nextInt();
        
        while(true)
        {
            System.out.println("=========== Large integer addition ==========");
            System.out.println("| Enter 1 to Read numbers from File         |");
            System.out.println("| Enter 2 to Display integers stored in SILL|");
            System.out.println("| Enter 3 to Display addition result        |");
            System.out.println("| Enter 4 to Exit                           |");
            System.out.println("=============================================");
            choice=sc.nextInt();
            switch(choice)
            {
            case 1:
                try {
                reader = new BufferedReader(new FileReader("myfile.txt"));
                String line = reader.readLine();
                
                
create first list
                for (int i = line.length()-1; i >= 0; --i) 
                    list.push(Character.getNumericValue(line.charAt(i)), 1);
                
 read next line
                line = reader.readLine();
                
System.out.println(line);
                
create second list
                for (int i = line.length()-1; i >= 0; --i) 
                   list.push(Character.getNumericValue(line.charAt(i)), 2);
                
System.out.println(line);
                reader.close();
                } catch (IOException e) {
                System.out.println("The required file is not found");
                e.printStackTrace();
                }
                
eak;
            case 2:             
                list.printlist(list.head1);
                System.out.println("Number of nodes: "+list.getsize(list.head1));
                list.printlist(list.head2);
                System.out.println("Number of nodes: "+list.getsize(list.head2));
                
eak;
            case 3:
                list.addlists(); 
                list.printlist(list.result);
                System.out.println(" ");
                
eak;
            case 4:
                System.exit(0);
                
eak;
            default:
                System.out.println("Invalid choice");
            }
        
        }
       
    } 
}