Member Avatar for gretty

Hello

I have a task to perform an addition of 2 Big Integers. Each Big Integer is stored in a linked list in reversed order. Is my add function correct?

For eg;
we have 2 Big Ints to add together

First BigInt = 245 { strored in the linked list as 5 - 4 - 2 }
2nd BigInt = 23 { strored in the linked list as 3 - 2 }

bigInt bigInt::add(bigInt J)
{ 
       // Write this function correctly.
       // You could simply insert an appropriate loop
       // where indicated below.
       int i, j, k, s;
       int carry = 0;
       node * currentp = firstp;
       node * currentJp = J.firstp;
       node * result;
       makeEmpty(result);
       
       // Insert an appropriate loop here.
       // Build up result using comp.

       while (currentp != NULL) {
              
              i = currentp->data + currentJp->data + carry;
              if (i>=10) {
                  carry = 1;
                  i = i%10;
              }
              else carry = 0;
              
              result = comp(result,i);
              currentp = currentp->next;
              currentJp = currentJp->next;
       }
      
       invert(result); // result needs to be inverted to obtain correct order of digits.
       bigInt K(result);
       return K;
}

Whole source code:

#include "bigInt.h"
#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

// Definition of node
struct node
{
       int data;
       node * next;
};

/* Member functions of the class bigInt

node * comp(node * L, int x); // returns composition of L and x 
                              // (i.e. the list obtained by inserting a new node containing x
                              // at the head of L)

class bigInt
{
      public:
              bigInt add(bigInt J); 
      
       private:
              node * firstp;
};          
*/

bigInt bigInt::add(bigInt J)
{ 
       // Write this function correctly.
       // You could simply insert an appropriate loop
       // where indicated below.
       int i, j, k, s;
       int carry = 0;
       node * currentp = firstp;
       node * currentJp = J.firstp;
       node * result;
       makeEmpty(result);
       
       // Insert an appropriate loop here.
       // Build up result using comp.

       while (currentp != NULL) {
              
              i = currentp->data + currentJp->data + carry;
              if (i>=10) {
                  carry = 1;
                  i = i%10;
              }
              else carry = 0;
              
              result = comp(result,i);
              currentp = currentp->next;
              currentJp = currentJp->next;
       }
      
       invert(result); // result needs to be inverted to obtain correct order of digits.
       bigInt K(result);
       return K;
}


node * comp(node * L, int x)
{
     node *newp = new node;
     newp->data = x;
     newp->next = L;
     
     return newp;     
}

My lecturer gave us half of the function 'add' already done but I haven't used all of the variables in the template. Why did they give us so many variables??

Template given by lecturer:

bigInt bigInt::add(bigInt J)
{ 
       // Write this function correctly.
       // You could simply insert an appropriate loop
       // where indicated below.
       int i, j, k, s;
       int carry = 0;
       node * currentp = firstp;
       node * currentJp = J.firstp;
       node * result;
       makeEmpty(result);
       
       // Insert an appropriate loop here.
       // Build up result using comp.
      
       invert(result); // result needs to be inverted to obtain correct order of digits.
       bigInt K(result);
       return K;
}
  • 1 Contributor
  • 1 Reply
  • 420 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by gretty

Dani AI

Generated

Short diagnosis (based on 's post): the provided add loop assumes both lists are the same length and dereferences currentJp unconditionally. That will either crash or produce wrong results when one operand is shorter (e.g. 245 + 23). The implementation also doesn't robustly handle the final carry or empty-list cases. The extra template variables (j, k, s) were likely left to give students placeholders for intermediate values or alternate approaches — they are optional.

Fix strategy (concise, reliable):

  • Iterate while either list has nodes or there is a carry: process all digits and the final carry.
  • Read each digit defensively (treat missing nodes as 0) instead of dereferencing a possibly NULL pointer.
  • Compute carry with integer division (carry = sum / 10) and digit with modulo (digit = sum % 10).
  • Either append digits to a tail (so no final reversal is needed) or keep using comp and then invert once at the end.
  • Make the function signature accept a const reference (e.g. const bigInt &J) to avoid an unnecessary copy.

Quick, safe loop (illustrative; does not duplicate the original posted code):

node *p = firstp, *q = J.firstp;
node *result = NULL;
int carry = 0;
while (p || q || carry) {
    int a = p ? p->data : 0;
    int b = q ? q->data : 0;
    int s = a + b + carry;
    carry = s / 10;
    result = comp(result, s % 10);   // or append at tail to avoid later invert
    if (p) p = p->next;
    if (q) q = q->next;
}
invert(result); // only if comp() was used to build head-first

Other practical notes: test edge cases (999+1 -> 1000, zeros, very different lengths), check that makeEmpty initializes result to NULL, and inspect comp/invert for correct pointer ownership to avoid leaks.

Member Avatar for gretty

Please help :(

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.