Linked Lists in C

I won't get into the C part of it, but in terms of a linked list,
for example, the first input
1 8888888888 2222222222
To take input, start reading the line
1: adding
[space]: begin new bigInteger
8: create a LL element, with the value 8, pointing to null. Keep the pointer to this element
8: create a LL element, with the value 8, pointing to the previous element
[...]
8: ditto. Keep a pointer to this element.
[space]: end bigInteger, return the pointer to the previous element as the bigInteger. Begin another bigInteger
2: do the same as before, with returning a pointer to the final element when you hit the end of the line.


With them stored in backwards order like this, adding and subtracting are simple iterations over the linked lists - the output bigInteger's first element is the sum of the 2 first elements, next is the sum of next two, etc., with carries included to complicate things slightly.

Personally I would only use their given headers for the first elements of the bigIntegers, and have the next ones go

Code:

struct integer* combine(integer* a, integer* b, integer carry, integer sign)
// In this case, you'd have
{
  integer temp <- a.digit + sign*b.digit + carry
  this.digit <- temp%10
  this.next <- addsub(a.next, b.next, temp/10, sign)
}

Note that this will only work as written if you override integer division to give the wanted results. You need it to floor at all times, instead of truncating toward zero.

Code:

sign*abs(temp/10)

This would be the easiest solution I see.

In fact I would probably have

Code:

struct integer* add(struct integer *p, struct integer *q)
  return combine(p,q,0,1);
struct integer* subtract(struct integer*p, struct integer*q)
  return combine(p,q,0,-1);

The rest of the functions look a lot like this aside from printing. Print would have to go something like (using pseudocode again here)

Code:

print (integer* a)
{
if (a.next == null ptr)
  print a.digit
else
  print(a.next);
  print a.digit
}

I'm not familiar with how deep you can recurse in C++ but I suspect it's taken care of by the compiler.