Question

Long Integer Addition

For this assignment you are to write a class that supports the addition of extra long integers, by using linked-lists. Longer than what is supported by Java's built-in data type, called long.

Your program will take in two strings, consisting of only digits, covert each of them to a linked-list that represents an integer version on that string. Then it will create a third linked-list that represents the sum of both of the linked lists. Lastly, it will print out the result of the sum.

Conceptual Example
For the string: "12", create a list: head->1->2->null
For the string: "34", create a list: head->3->4->null
Add the two lists to create a third list: head->4->6->null
print the resulting linked list as "46"
Where "->" represents a link.

Keep in mind that the conceptual example above is conceptual. It does suggest a certain implementation. However as you read on you will see that you have several options for implementing your solution. You need not use the suggested implementation above.

For this class you are to implement a minimum of three methods. They are:

1. A method called makeSDList() that takes in a string, consisting only of digits, as an argument, and creates and returns a linked-link representation of the argument string.

   The method has the following header:

   SDList makeSDList(String s) { }

   where s is a string, and SDList is the class name of the linked list.  

2. A method called addLists() that takes takes two lists, adds them together, and creates and returns a list that represents the sum of both argument lists.

   The method has the following header:

   SDList addLists(SDList c) { }

   wherec  linked-list of type SDList .

3. A method called displayList() that takes takes a list, prints the value of each digit of the list.  

   The method has the following header:

   void displayList() { }

Programming Notes

1. You need not add any methods you don't need.
2. You can add any methods use wish.
3. You can use any type of linked list like: singly-linked, doubly-linked, circular, etc.
4. You can choose you own list implementation such-as with or without sentinels, with head and/or tail points, etc.
5. Do not assume any maximum length for either addend.
6. You can assume that an each addend is a least one digit long.
7. You need not test for the null or empty string ("") cases.
8. The addends need not be the same length.

Programming Rules:

1. You are not allowed to change the signature of the three methods above.
2. You are not allowed to use arrays or ArrayLists anywhere in your solution.
3. You are not allowed to use any Java built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues, Deques, Trees, Graphs, Heaps, etc. Or make any class that inherits any of those ADTs.
4. You are to create your own node and list class. For your node and list class you can use the code that was used in the book, video and lecture notes related to the node and lists class examples.
5. You are only allowed to have one class for your nodes and one class for your lists.
6. You are not allowed to use Java Generics.
7. You can use any data type to represent the digits (in the node). However, each node must represent one and only one digit.
8. If hard-coding detected in any part of your solution your score will be zero for the whole assignment.

Submission Rules:

1. Submit only one Homework5.java file for all test cases. The starter file is names Homework5a.java so you will need rename the file before you begin submitting your solution.

2. Anything submitted to Mimir is considered to be officially submitted to me and is considered to be 100% your work. Even if it is not your last planned submission.

3. Any extra testing code that you wrote and used to do your own testing should be deleted from the file that gets used in the final grading. I emphasize the word deleted. Commenting out code is not sufficient and not considered deleted. It must be completely removed. English comments written to explain your code are perfectly fine.

STARTER CODE

import java.util.Scanner;  // Import the Scanner class

public class Homework5a {

  

  public static void main(String[] args) {

    SDList x, y, z;

    String a, b;

    Scanner input = new Scanner(System.in);  // Create a Scanner object

    System.out.print("A: ");

    a = input.nextLine();

    x = makeSDList(a);               // convert first string to a linked list

    x.displayList();                 // call function that displays list x

    System.out.print("B: ");   

    b = input.nextLine();

    y = makeSDList(b);               // convert second string to a linked list

    y.displayList();                 // call function that displays list z

    z = x.addLists(y);               // add lists x & y and store result in list y

    System.out.print("A+B: ");

    z.displayList();                 // call function that displays list z

  }

   

  public static SDList makeSDList(String s) {

  // put your solution here

    return null;

  }

}

class SDList {

  // put your solution here

  

  public SDList addLists(SDList c) {   

  // put your solution here

    return null; //replace if necessary

  }

  

  public void displayList() {

  // put your solution here

  }

}

Answer 1

Program:

import java.util.Scanner; // Import the Scanner class

public class Homework5a {

public static void main(String[] args) {

SDList x, y, z;

String a, b;

Scanner input = new Scanner(System.in); // Create a Scanner object

System.out.print("A: ");

a = input.nextLine();

x = makeSDList(a); // convert first string to a linked list

x.displayList(); // call function that displays list x

System.out.print("B: ");   

b = input.nextLine();

y = makeSDList(b); // convert second string to a linked list

y.displayList(); // call function that displays list z

z = x.addLists(y); // add lists x & y and store result in list y

System.out.print("A+B: ");

z.displayList(); // call function that displays list z

}

public static SDList makeSDList(String s) {
   
   SDList temp = new SDList();
for(int i=s.length()-1; i>=0; i--)
{
   temp.insert(s.charAt(i));
}
return temp;

}

}

class SDList {
  
   class SDNode{
       char digit;
       SDNode next;
       SDNode prev;
      
       public SDNode (char digit) {
           this.digit = digit;
           next = null;
           prev = null;
       }
   }
  
   private SDNode head;
  
   public SDList() {
       head = null;
   }
  
   public void insert(char a) {
       if (head == null) {
           head = new SDNode(a);
           return;
       }
       SDNode temp = new SDNode(a);
       temp.next = head;
       head.prev = temp;
       head = temp;
   }

   public SDList addLists(SDList c) {
       SDList temp = new SDList();
       int sum = 0, carry = 0;
       char digit;
      
       SDNode p = head;
       while(p.next!=null)
           p = p.next;

       SDNode q = c.head;
       while(q.next!=null)
           q = q.next;

       while (p != null || q != null) {
           sum = (p.digit-'0') + (q.digit-'0') + carry;
           digit = (char)((sum % 10) + '0');
           temp.insert(digit);
           carry = sum / 10;
           if (p != null)
           p = p.prev;
           if (q != null)
           q = q.prev;
       }
       if (carry!=0)
       temp.insert((char)(carry+'0'));
      
       return temp;
}

  
public void displayList() {
  
   SDNode current = head;
   while (current != null) {
       System.out.print(current.digit);
       current = current.next;
   }
   System.out.println ();
}
}

Output:

A: 123
123
B: 999
999
A+B: 1122

Solving your question and helping you to well understand it is my focus. So if you face any difficulties regarding this please let me know through the comments. I will try my best to assist you. However if you are satisfied with the answer please don't forget to give your feedback. Your feedback is very precious to us, so don't give negative feedback without showing proper reason.
Thank you.