Adding two BigInts using linked lists in C

Question

While trying to learn more about linked lists, I thought I should try the exercise of reading two BigInts from an input file and then adding them up. My strategy was to store the two numbers in two different linked lists and then add the entries of the linked lists while traversing through them. I have my implementation down below and it will be great if somebody could review what I have done here. The current implementation is geared towards adding two numbers. It will be great if somebody could give me a few pointers on extending it for an arbitrary number of BigInts.

My "input.txt" is as follows:

65368023423432568512973371196238845129776544789456 553245642579324556736835497210698463523456234 

And my implementation is as follows:

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct node{ int data; struct node* next; } LList; LList* pushToResult(LList* resultList,int entry){ LList * temp = malloc(sizeof(LList)); temp -> data = entry; temp -> next = resultList; resultList = temp; return resultList; } LList* convertToList(LList * list,char* line){ //Get the size of the string //Create a new list int i; int strSize = strlen(line); LList * temp = NULL; for(i=0;i<strSize-1;i++){ char num = line[i]; if(temp == NULL){ temp = malloc(sizeof(LList)); temp -> data = num - '0'; temp -> next = NULL; }else{ LList * current = malloc(sizeof(LList)); current -> data = num - '0'; current -> next = temp; temp = current; } } list = temp; return list; } void printList(LList * list){ LList * counter = list; while( counter != NULL){ printf(" %d ",counter -> data); counter = counter -> next; } printf("\n\n"); } int main(){ //Read number 1 from the input file into a linked list //The unit's place is the head and the mot significant number is the tail //Read number 2 from the input file into a linked list //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; ssize_t read; size_t len = 0; char * line = NULL; int carry = 0; LList* num1 = NULL; LList* num2 = NULL; LList* result = NULL; //Opening the file for the input FILE * input = fopen("input.txt","r"); if(input == NULL){ exit(EXIT_FAILURE); } while((read = getline(&line,&len,input)) != -1){ printf("Read the line %s",line); //If it's the first line if(counter == 0){ //printf("Counter is 0\n"); num1 = convertToList(num1,line); printf("Printing the list containing the num1(it will be in reversed order)\n"); printList(num1); }else{ num2 = convertToList(num2,line); printf("Printing the list containing the num2(it will be in reversed order)\n"); printList(num2); } counter++; } //Closing the input file 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 / 10; int leftOver = carry % 10; 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); } 

Answer 1

Just two things:

1. In convertToList() you don't really use the first argument at all. You can code that function with receiving only the (read-only) input string.

   LList *convertToList(const char *line) { /* ... */ return temp; } 

2. You really should get into the habit of releasing memory once you no longer need it. For each malloc() there should be a free(). This includes the result from getline().

3. (extra) Don't comment the obvious

    //Closing the input file fclose(input); 

   This is OK though :)

    //Get the carry and the left over int carryOver = carry / 10; int leftOver = carry % 10; 

Answer 2

If you want to make it more (memory) efficient and thereby also faster, you could make every list node represent 9 digits from the input. Your highest possible value in a node would be 999999999 and adding two of these would still not overflow the range of int. You are thus encoding your values base 1000000000. Of course, you could also try using long long and encode 18 digits of a value in a node.

I know that you are primarily interested in learning about linked lists, but I think learning to use them efficiently is part of that task.