# Adding two BigIntegers by putting mutiple digits in a linked list

Based on feedback on an earlier question, I decided to implement the addition of two big ints by putting multiple digits in a node of a linked list. Can somebody take a look at my code and let me know if I am on the right track.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct node{
int data;
struct node* next;
} LList;

void printList(LList * list);

LList* pushToResult(LList* resultList,int entry){
LList * temp = malloc(sizeof(LList));
temp -> data = entry;
temp -> next = resultList;
resultList = temp;
return resultList;
}

char* substr(char const* input,size_t start,size_t len){
char *nstr = malloc(len+1);
memcpy(nstr,input+start,len);
nstr[len] = '\0';
return nstr;
}

LList* convertToList(char* line){
int i;
int strSize = strlen(line);
//Eight elements in every node
int maxelem = 8;
int currentPartition = 0;
int currentIndex = 0;
int totalPartitions = strSize/maxelem;
LList* temp = NULL;

for(i = 0;i < strSize - 1;i = i+maxelem){
if(currentPartition >= totalPartitions){
break;
}

char * currStr = substr(line,i,maxelem);
int number = atoi(currStr);
if(temp == NULL){
temp = malloc(sizeof(LList));
temp -> data = number;
temp -> next = NULL;
}else{
LList * current = malloc(sizeof(LList));
current -> data = number;
current -> next = temp;
temp = current;
}
currentIndex = i;
currentPartition++;
}
currentIndex = currentIndex + maxelem;
if((currentIndex > 0) && (currentIndex < (strSize - 1))){
char * remainingStr = substr(line,currentIndex,strSize-1);
int remainingNum = atoi(remainingStr);
LList * current = malloc(sizeof(LList));
current -> data = remainingNum;
current -> next = temp;
temp = current;
}
return temp;
}

void printList(LList * list){
LList * counter = list;
while( counter != NULL){
printf(" %d ",counter -> data);
counter = counter -> next;
}
printf("\n\n");
}

int main(){
//The unit's place is the head and the most significant number is the tail
//The unit's place is the head and the most significant number is the tail
//Create temporary List where the elements will be added
//Create the carry variable that will consist of the element's carry over after addition

int counter = 0;
size_t len = 0;
char * line = NULL;

int carry = 0;
LList* num1 = NULL;
LList* num2 = NULL;
LList* result = NULL;

FILE * input = fopen("input.txt","r");
if(input == NULL){
exit(EXIT_FAILURE);
}
//If it's the first line
if(counter == 0){
num1 = convertToList(line);
printf("Printing the list containing the num1(it will be in reversed order)\n");
printList(num1);
}else{
num2 = convertToList(line);
printf("Printing the list containing the num2(it will be in reversed order)\n");
printList(num2);
}
counter++;
}

fclose(input);

while((num1 != NULL) || (num2 != NULL)){
if(num1 != NULL){
carry = carry + (num1->data);
num1 = num1 -> next;
}
if(num2 != NULL){
carry = carry + (num2 -> data);
num2 = num2 -> next;
}
//Get the carry and the left over
int carryOver = carry / 100000000;
int leftOver = carry % 100000000;

//put the left over in the result linked list
//printf("Pushing the result into the result list");
result = pushToResult(result,leftOver);
carry = carryOver;

}
//Done with traversing the linked lists,if the carry is zero no need to push the value to the result
//else push the value to the result
if(carry != 0){
result = pushToResult(result,carry);
}

//Print the result here
printf("Printing out the result of the addition\n");
printList(result);

}

-
@palacsint I don't think the compiler requires you to type-cast void* from malloc when it's C (not C++). – ChrisW Mar 15 '14 at 13:19
@ChrisW: Thanks, renaming from .cpp to .c makes compilable with gcc. Close vote retracted. – palacsint Mar 15 '14 at 13:31

Aside from the glaring bug, the major theme I see is that you can strive to generalize your code.

Examples:

1. Instead of reading from input.txt, read from stdin. For less work, the user gets more flexibility.

2. Why limit the program to adding two numbers, when you could add n numbers? It may be counterintuitive, but writing a program to add many lines of numbers would take less code, since you don't have to copy-and-paste the code to handle num1 and num2. (Start with an empty list, which represents an accumulator with an initial 0 value.)

3. In ConvertToList(), you don't need a special case for if(temp == NULL){ … } — the general case works just fine. Also, it's weird that your temp variable has a longer lifespan than current. Therefore, I would consider temp to be misnamed. I suggest head instead.

-

By inspection, I see memory leaks everywhere. Every malloc() should have a corresponding free(), and there isn't a single call to free().

-

Your calculator gives erroneous results due to incorrect partition alignment when converting the input into linked lists. For example:

$cat input.txt 122223 45555555555555555556$ ./cr44425
Printing the list containing the num1(it will be in reversed order)

Printing the list containing the num2(it will be in reversed order)
5556  55555555  45555555

Printing out the result of the addition
45555555  55555555  5556


I expect the sum to be

45555555555555555556
+             122223
====================
45555555555555677779


(In my opinion, aggregating the digits to reduce the number of list nodes adds a lot of complication for questionable gains.)

-
Thanks for your input. Would it be possible to consolidate all your answers so that I can accept it. – sc_ray Mar 16 '14 at 4:30