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/bin/.myfile.txt.swp
Addition/bin/.DS_Store
__MACOSX/Addition/bin/._.DS_Store
Addition/bin/LinkedListATN.class
public synchronized class LinkedListATN {
LinkedListATN$node head1;
LinkedListATN$node head2;
LinkedListATN$node result;
int carry;
LinkedListATN$node cur;
public void LinkedListATN();
void printlist(LinkedListATN$node);
void push(int, int);
void addsamesize(LinkedListATN$node, LinkedListATN$node);
void propogatecarry(LinkedListATN$node);
int getsize(LinkedListATN$node);
void addlists();
public static void main(String[]);
}
Addition/bin/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=error
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
org.eclipse.jdt.core.compiler.source=1.8
Addition/.project

     Addition
    
    
    
    
        
             org.eclipse.jdt.core.javabuilder
            
            
        
    
    
         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 carry; 

    /* 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. Carry 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 carry 
        addsamesize(n.next, m.next); 

        // add digits of current nodes and propagated carry 
        int sum = n.val + m.val + carry; 
        carry = 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 carry must be
    // added to the left side of larger list to get the
    // final result. 
    void propogatecarry(node head1)  
    { 
        // If difference number of nodes are not traversed, add carry 
        if (head1 != cur)  
        { 
            propogatecarry(head1.next); 
            int sum = carry + head1.val; 
            carry = 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 referred 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 carry 
            propogatecarry(head1); 
        } 
            // if some carry is still there, add a new node to
            // the front of the result list. e.g. 999 and 87 
            if (carry > 0) 
                push(carry, 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.carry = 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();
                }
                break;
            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));
                break;
            case 3:
                list.addlists(); 
                list.printlist(list.result);
                System.out.println(" ");
                break;
            case 4:
                System.exit(0);
                break;
            default:
                System.out.println("Invalid choice");
            }

        }

    } 
}