# Adding two extremely large numbers using a custom data structure

I have an implementation to add 2 extremely large numbers, greater than the ceiling provided by long, e.g. 1238913893838383813813813813838... I created a LinkedList of my own as this is the homework requirement:

LinkedList.java

public class LinkedList {

private Node tail;

private int size;

private Node currentNode; //its using for iterarion, like point to currentNode

size = 0;
}

//when addLast method invokes if there is no node in list, it creates one and set the node as header and tail. Next time, next node will be added to last, and it will be new tail.
Node newNode;

if(size == 0){
newNode = new Node(data);
tail = newNode;

}else {

Node temp = tail;

newNode = new Node(data);

tail = newNode;

temp.next = tail;
}

size++;

}

public String getNumberAsString(){ //addLast methods adds numbers to string one by one and header node represents unit digits, after that tens digist and so on ...
//This LinkedList is single directory so we have to go header to tail. For example our number is 123456. But list keeps it header =6, secondNode = 5.
//if I get with this way, it returns me 654321, as you see I need to reverse it to become 123456.

StringBuilder sb = new StringBuilder();

while(currentNode != null){
sb.append(currentNode.data);
currentNode = currentNode.next;
}
sb = sb.reverse();

return sb.toString();

}

public boolean hasNext(){ //method uses for does currentNode hasNext node ? or its end of list ?
if(currentNode == null) return false; // if currentNode is not assaigned or it assigned as null return false
if(currentNode.next == null) return false;
else return true;
}

public Node next(){
if(hasNext()){
currentNode = currentNode.next;
}
else{
currentNode = null;
}
return currentNode;

}

public void resetCurrent(){
//just set currentNode to first node(header)
}

public Node getCurrentNode() {
return currentNode;
}

public int size(){
return size;
}

public boolean isEmpty(){
if(size == 0) return true;
else return false;
}
}


Node.java

public class Node {
byte data;
Node next;

public Node(byte data) {
this.data = data;
}

}


Main.java

public class Main {
public static void main(String[] args) {

Scanner scn = new Scanner(System.in);

Main m = new Main();

System.out.println(thirdList.getNumberAsString());

}

// this method gets an instance of LinkedList and it fills list up from string(number).

for (int i = number.length()-1; i >= 0 ; i--) {
//I've written Character.getNumericValue(number.charAt(i)) because when I try to get 1 as a char from string wtih charAt() and assigned it to byte, byte variable will be assigned 1's ascii
//code and I don want that. I want 1 as number like byte = 1. So thats why I used Character.getNumericValue(char a) it takes a char and it gives numeric value of that char.
}

}

byte sum, first,second,flag = 0; //flag = carry flag

if(firstList.isEmpty() && secondList.isEmpty()) return null;  //if both list are empty there will be no sum so just return null.

firstList.resetCurrent(); // currentNode now points header
secondList.resetCurrent();

while(firstList.getCurrentNode() != null || secondList.getCurrentNode() != null ){ // this loops works until both linkedList currentNode will be null, it means list is over.

//for example 1345 + 1234, if this situation comes, it works like 12345 + 01234. If we didnt check it, it could throw NullPointerException, you know byte = null (NullPointerException)

first = firstList.getCurrentNode() == null ? 0 : firstList.getCurrentNode().data;
second = secondList.getCurrentNode() == null ? 0 : secondList.getCurrentNode().data;

sum = (byte)(first + second + flag);

if( sum >= 10){
flag = 1;
sum = (byte) (sum - 10);
}else{
flag = 0;
}

firstList.next(); //set current node as currentNode.next, this way gives us to goes end of list from to beginning
secondList.next();

}

if(flag>0){ //9523 + 902 = 10425,  after loop if our flag still on, we need to add flag to end of list. If we dont, it will be like 9523 + 902 = 0425 and we dont want that.
flag = 0;
}

}

}


I am open to all comments and feedback.

• "You know its actually out of range." Out of range of what?
– Mast
Mar 1, 2017 at 12:02
• I meant integer but the number might be more digits like 100-200 digits. I know I could use BigInteger. However It was my homework so I had to implement methods by myself. Mar 1, 2017 at 12:09
• Do you intend to allow algebraic add subtract? If not you may want to consider it at this time. That is in sign (+-). Mar 1, 2017 at 15:19
• I thought about that, I will probably improvement my code which contains subtract method. Thank you for your suggestion :) Mar 1, 2017 at 16:06

First of all, code could be more aligned with the pencil-and-paper algorithm, which is used here for addition of numbers. I.e. it operates on columns of digits, minor to major. So, from the very beginning you can take input strings and make List.

Then, all that is left to be done is, speaking functionally, to make left fold of the list, beginning with empty list of digits and applying a function which takes remaining list of columns, accumulated result bytes and carry flag and returns a tuple of new remaining list of columns, new accumulated result bytes and new carry flag. Then you need to take care of the last carry. Either be prepending zero to the initial list, or by checking it after left fold.

In functional language with support of tail-call elimination that would be quite expressive and brief.

But Java is more imperative and verbose, so you should either make your own implementation of left fold, or use iterators.

At last, you could use more functional singly-linked list. You even use names "head" and "tail". Functional list is recursively defined as construct ("Cons") of "head", which is single item, and "tail", which is the remaining list. Or, it could be just empty list ("Nil"). This data structure is immutable, memory-effective, thread-safe, allowing reuse of lists in new lists. And it is fast to iterate from the last added to the first item.

In general, functional approach makes a code easier to reason about, to test and to parallelise. Functional composition and higher order functions like foldLeft or map make it more readable once you get to know, what that higher order functions calculate.

So, my two cents:

Main.java

package itollu;

import java.util.Scanner;
import itollu.list.List;
import itollu.summator.ColumnOfDigits;
import static itollu.summator.SumFunctions.columnsFromStrings;
import static itollu.summator.SumFunctions.trim;
import static itollu.summator.SumFunctions.formatNumber;

public class Main {
public static void main(String[] args) {

Scanner scn = new Scanner(System.in);

System.out.println("Enter first number: ");
String firstNumber = scn.nextLine();
System.out.println("Enter second number: ");
String secondNumber = scn.nextLine();

List<Byte> trimmedSumNumber = trim(sumNumber);
String formattedSum = formatNumber(trimmedSumNumber);

System.out.println("Sum is: ");
System.out.println(formattedSum);

}

}


List.java

package itollu.list;

public interface List<T> {

List<T> tail();

int length();

}


Cons.java

package itollu.list;

public class Cons<T> implements List<T> {

private final List<T> tail;
private final int length;

this.tail = tail;
length = tail.length() + 1;
}

@Override
}

@Override
}

@Override
public List<T> tail() {
return tail;
}

@Override
public int length() {
return length;
}

}


Nil.java

package itollu.list;

public class Nil<T> implements List<T> {
private static Nil instance = new Nil();

public static Nil getInstance() {
return instance;
}

private Nil() {
}

@Override
}

@Override
throw new IllegalStateException("Nil cannot have head");
}

@Override
public List<T> tail() {
throw new IllegalStateException("Nil cannot have tail");
}

@Override
public int length() {
return 0;
}

}


ColumnOfDigits.java

package itollu.summator;

public class ColumnOfDigits {
final byte firstDigit;
final byte secondDigit;

public ColumnOfDigits(byte firstDigit, byte secondDigit) {
validateDigit(firstDigit);
validateDigit(secondDigit);
this.firstDigit = firstDigit;
this.secondDigit = secondDigit;
}

public ColumnOfDigits(int firstDigit, int secondDigit) {
this((byte) firstDigit, (byte) secondDigit);
}

public ColumnOfDigits(char firstDigit, char secondDigit) {
this(
Character.getNumericValue(firstDigit),
Character.getNumericValue(secondDigit)
);
}

private void validateDigit(byte digit) {
if (digit < 0 || digit > 9) {
String msg = String.format(
"Digit [%d] if out of valid range 0-9", digit
);
throw new IllegalArgumentException(msg);
}
}
}


SumFunctions.java

package itollu.summator;

import itollu.list.List;
import itollu.list.Nil;

import static java.lang.Math.max;

public class SumFunctions {

// Result is represented with minor digits at head, as is required
public static List<ColumnOfDigits> columnsFromStrings(String number1, String number2) {
int totalColumns = max(number1.length(), number2.length());

@SuppressWarnings("unchecked") List<ColumnOfDigits> result = Nil.getInstance();
for (int i = 0; i < totalColumns; i++) {
ColumnOfDigits column = new ColumnOfDigits(n1.charAt(i), n2.charAt(i));
result = result.prepend(column);
}

return result;
}

// Pad zeros to the beginning of numeric String leaving value intact, till the given length
int initialLength = numString.length();
int zerosLength = paddedLength - initialLength; // that many zeros to pad

// We cannot pad negative amount of zeros
throw new IllegalArgumentException("Initial string cannot be longer than padded string");
}

StringBuilder result = new StringBuilder();
for (int i = 0; i < zerosLength; i++) {
result.append('0');
}

result.append(numString);
return result.toString();
}

// Result is represented with major digit at head, which is expected order
@SuppressWarnings("unchecked") List<Byte> result = Nil.getInstance();
boolean carry = false;

while (remainingColumns.length() > 0) {
sumDigit = carry ? sumDigit + 1 : sumDigit;
if (sumDigit > 9) {
sumDigit = sumDigit - 10;
carry = true;
} else {
carry = false;
}
result = result.prepend((byte) sumDigit);
remainingColumns = remainingColumns.tail();
}

if (carry) {
result = result.prepend((byte) 1);
}

return result;
}

// Trim meaningless major zero digits
public static List<Byte> trim(List<Byte> number) {
Byte zero = (byte) 0;
List<Byte> result = number;
while (result.length() > 1 && result.head().equals(zero)) {
result = result.tail();
}
return result;
}

public static String formatNumber(List<Byte> sumNumber) {
StringBuilder result = new StringBuilder();
List<Byte> remainingDigits = sumNumber;

while (remainingDigits.length() > 0) {