Addition Of Two Numbers Using Linked Lists

Another very frequently searched algorithm is to add two very long numbers (in the order of zillions) using Linked Lists.

IMPLEMENTATION:

We use the Linked List to implement such a logic. Here, we make use of the fact that “int” in java has the range -2^31 to 2^31 which is 10 digits long. Therefore, every node in the list can hold maximum upto 10 digits. If the number has more than 10 digits, the More Significant Digits are pushed in the previous node. Thus 2 Lists are created for 2 numbers and they are then added node-by-node. The carry, if generated is added to the next pair of nodes to get the proper answer.

As usual, we have used our own version of Linked List to make the addition, deletion, and searching nodes processes transparent.

	public class LinkedListNode {
	String info;
	LinkedListNode address;
	public LinkedListNode(){
	info = "";
	address = null;
	}
	}

view raw Linked List Node hosted with ❤ by GitHub

	import java.util.Scanner;
	public class LinkedList {
	LinkedListNode listPointer = null;
	LinkedListNode lastNodePointer = null;
	int numberOfNodes = 0;
	static Scanner input = new Scanner(System.in);
	public LinkedList() {
	}
	public static void main(String[] args) {
	String info;
	LinkedList newList = new LinkedList();
	System.out.println("Enter the info in first node");
	info = input.next();
	newList.addFirstNode(info);
	int choice;
	do{
	System.out.println("Enter 1 for adding a node to the end, 2 for adding a node at a particular position, 3 for deleting a node, 4 to search for a node, 5 to exit");
	System.out.println("What do you want to do?");
	choice = input.nextInt();
	switch(choice){
	case 1 : {
	System.out.println("Enter the info in the node");
	info = input.next();
	newList.addNodeToEnd(info);
	break;
	}
	case 2 :{
	System.out.println("Enter the position of the new node");
	int position = input.nextInt();
	System.out.println("Enter info of the new node");
	info = input.next();
	newList.addNodeAtPosition(position, info);
	break;
	}
	case 3 :{
	System.out.println("Enter the position of the node you want to delete");
	int position = input.nextInt();
	newList.deleteNode(position);
	break;
	}
	case 4 : {
	System.out.println("Enter the info of the node you want to search");
	info = input.next();
	newList.searchForNode(info);
	break;
	}
	default : System.out.println("Give appropriate choice");
	}
	}while(choice != 5);
	}
	public void addFirstNode(String info){
	LinkedListNode firstNode = new LinkedListNode();
	firstNode.info = info;
	firstNode.address = null;
	listPointer = firstNode;
	lastNodePointer = firstNode;
	numberOfNodes = 1;
	viewList();
	}
	public void addNodeToEnd(String info){
	LinkedListNode newNode = new LinkedListNode();
	newNode.info = info;
	newNode.address = null;
	lastNodePointer.address = newNode;
	lastNodePointer = newNode;
	numberOfNodes++;
	System.out.println("Node added");
	viewList();
	}
	public void addNodeAtPosition(int position, String info){
	LinkedListNode tempPointer = listPointer;
	for (int tempPosition = 0; tempPosition < position-1; tempPosition++) {
	try{
	tempPointer = tempPointer.address;
	}
	catch(NullPointerException e){
	System.out.println("Position " + (position-1) + " has not been occupied yet!");
	System.out.println("Adding node at the end");
	addNodeToEnd(info);
	return;
	}
	}
	LinkedListNode newNode = new LinkedListNode();
	newNode.info = info;
	newNode.address = (tempPointer.address).address;
	tempPointer.address = newNode;
	System.out.println("Node added");
	viewList();
	}
	public void deleteNode(int positionOfNode){
	LinkedListNode tempPointer = listPointer;
	for (int tempPosition = 0; tempPosition < positionOfNode-1; tempPosition++) {
	tempPointer = tempPointer.address;
	}
	tempPointer.address = (tempPointer.address).address; // this is the main shifting statement
	System.out.println(tempPointer.info + " deleted");
	numberOfNodes--;
	viewList();
	}
	public void viewList(){
	LinkedListNode temp = listPointer;
	for (int counter = 0; counter < numberOfNodes; counter++) {
	System.out.print("[" + temp.info + ", " + temp.address + "]");
	temp = temp.address;
	}
	System.out.println();
	}
	public LinkedListNode searchForNode(String info){
	LinkedListNode temp = listPointer;
	while(!temp.info.equals(info)){
	temp = temp.address;
	if(temp == null){
	System.out.println("Node not in the list!");
	return null;
	}
	}
	return temp;
	}
	}

view raw Linked List hosted with ❤ by GitHub

The main Addition class which calls the above class is as follows:

NOTE: We have created the program keeping in mind only positive integers. Floating point numbers may/may not work in this program depending on the number!

	package labWorkDSA;
	import java.util.Scanner;
	public class AdditionOfTwoNumbers {
	/* SENTINEL is kept at 1 followed by 9 zeroes. This is the most efficient SENTINEL because :
	* The range of 'int' is -(2^31) to +(2^31) -1 which is a 10 digit number.
	*/
	public static final int SENTINEL = 1000000000;
	public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	System.out.println("Enter a number");
	String exp1 = input.next();
	LinkedList list1 = arrangeInList(exp1);
	System.out.println("Enter another number");
	String exp2 = input.next();
	LinkedList list2 = arrangeInList(exp2);
	System.out.println("The sum of the two numbers is:" + addLists(list1, list2));
	input.close();
	System.exit(0);
	}
	public static LinkedList arrangeInList(String numberString){
	boolean isFirstNode = true;
	String info;
	LinkedList newList = new LinkedList();
	while(true){
	/*The entire while loop mainly contains a single if-else condition
	* It checks whether the number remaining to be evaluated (initially the entire number) has a length>9
	* This is because if it does, we need to break it down into numbers with max 9 digits
	* if not, we simply add the whole number into a new node and break
	* We break because this is obviously, the last node
	*/
	if(numberString.length() > 9){
	info = convertLast9CharsIntoDigits(numberString);
	if (isFirstNode){
	newList.addFirstNode(info);
	isFirstNode = false;
	}
	else{
	newList.addNodeToEnd(info);
	}
	numberString = getHigherDigits(numberString);
	}
	else{
	if(isFirstNode){
	newList.addFirstNode(numberString);
	}
	else{
	newList.addNodeToEnd(numberString);
	}
	break;
	}
	}
	return newList;
	}
	public static String convertLast9CharsIntoDigits(String mainString){
	String intString = mainString.substring(mainString.length()-9);
	return intString;
	}
	public static String getHigherDigits(String string){
	String temp = "";
	for(int i = 0; i < string.length()-9; i++){
	temp+= string.charAt(i);
	}
	return temp;
	}
	public static String addLists(LinkedList list1, LinkedList list2){
	String result = ""; // the result of the addition will be a string as it may be too long
	String temp = "";
	byte carry = 0; //carry is a single byte which will store only 1 digit number
	int sum = 0;
	String sumString = ""; // This is the string after parsing int sum to string
	boolean lastOfList1 = false; //These store whether list1 or 2 have ended or not.
	boolean lastOfList2 = false;;
	while(list1.listPointer!= null || list2.listPointer!= null){
	/*This if-else ladder will check if any node is null and therefore, not take into consideration
	A node will be null when one of the 2 numbers is much larger than the second
	*/
	if(list1.listPointer == null){
	sum = carry + Integer.parseInt(list2.listPointer.info);
	lastOfList1 = true;
	}
	else if(list2.listPointer == null){
	sum = carry + Integer.parseInt(list1.listPointer.info);
	lastOfList2 = true;
	}
	else{
	sum = carry + (Integer.parseInt(list1.listPointer.info) + Integer.parseInt(list2.listPointer.info));
	}
	//end of if-else ladder-1
	/* This ladder will check whether the number is greater than SENTINEL i.e.
	* whether a carry is generated or not
	*/
	if(sum/SENTINEL != 0){
	carry = Byte.parseByte(Integer.toString(sum/SENTINEL)); // V IMP STEP : Use Of Wrapper Classes Byte, Integer and String
	sum = sum % SENTINEL;
	}
	else{
	carry = 0;
	temp = "";
	}
	//end of if-else ladder-2
	sumString = Integer.toString(sum);
	for (int i = 0; i < 9-sumString.length(); i++) {
	temp += "0";
	}
	temp += sumString;
	sumString = temp;
	temp = sumString + result;
	result = temp;
	if(!lastOfList1){
	list1.listPointer = list1.listPointer.address;
	}
	if(!lastOfList2){
	list2.listPointer = list2.listPointer.address;
	}
	}
	return result;
	}
	}

view raw Addition Of Two Numbers hosted with ❤ by GitHub

NOTE: A more elegent solution will be to input the number from Most Significant Digits and keep pushing the nodes into a stack. Thus, we will have 2 stacks for 2 numbers. Now, all we need to do is add the node pointed by the top of each stack with each other and and keep pushing it into a "result" stack.