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;
   

• sc_ray: Thanks for your response. Can you clarify which malloced elements can I free in this code. Being a newbie to C I lack the intuition about when to free the elements. I thought since every element of the Linked List is in use, I do not need to free any elements. It will be great to hear your rationale for free'ing any of these elements.
• pmg: Current Operating System will free the memory your program leaked once the program finishes but it is a good idea to free it yourself nonetheless! You can free the memory allocated in pushToResult() and convertToList() at the end of main, after the call to printList() (I'd make a function for that and name it something like freeList()). As for the memory allocated with getline() you can free that at the end of the loop, right before (or after) closing the input file.

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.

• sc_ray: Thanks for your response. Can you explain what you meant by "You are thus encoding your values base 1000000000."?
• pmg: In your struct node what values can the element data have? 0 to 9, 10 distinct values. That's the base. Base 10. If you allowed data to have values 0 and 1 only, that would be base 2; for values from 0 to 15 would be base 16, ...