Add two numbers stored as digit lists

Why it matters

A plain int in C++ holds a limited range. On the usual 32-bit setup it stops at 2,147,483,647. A number with 30 digits does not fit in the standard integer types. Programs that handle very large counts, exact money amounts or cryptographic keys need numbers of any size, so they store the digits themselves. A common way to do that is a linked list where each node holds one digit.

Adding two such numbers is also a classic interview question. The task is to take two lists and return a new list that holds their sum. The problem looks small, but it checks three things at once. Can you walk two lists side by side? Do you carry the extra ten from one column to the next? Do you handle the cases where one list runs out first, or where the sum ends with an extra digit? The basics lesson in this module shows how to walk a list with a pointer, and this lesson assumes you can do that.

The idea: school addition on a list

Start with the method you learned at school. Write 342 above 465 with the last digits lined up. Work from the right side:

Column 1: 2 + 5 = 7. Write 7.
Column 2: 4 + 6 = 10. Ten does not fit in one digit, so write 0 and pass 1 to the next column. That 1 is the carry.
Column 3: 3 + 4 + 1 (the carry) = 8. Write 8.

The answer is 807.

A list can do the same thing. The only change is the order of the digits. In a list, the first node is the head, and you start at the head. So the list stores the ones digit first, which is the reverse of how we write numbers on paper. The number 342 is stored as the list 2 -> 4 -> 3. The head holds 2, the ones digit, and the last node holds 3, the hundreds digit.

Here are the three numbers from this lesson in both forms:

Number	Stored list, head first
342	`2 -> 4 -> 3`
465	`5 -> 6 -> 4`
807	`7 -> 0 -> 8`

Storing the ones digit first has a useful effect. You can start both lists at their heads and move forward one node at a time. Each step handles the next column, from right to left, and the result grows at its end. You never need to find the end of a list before you start.

Two arithmetic tools: remainder and quotient

Every column total is a whole number from 0 up to 19. The largest case is 9 + 9 + 1, where 1 is the carry from the column before. Two integer operations split a total into the digit to write and the carry to pass on.

total % 10 is the remainder after dividing by 10. It is the last digit of the total, which is the digit to write.
total / 10 is the quotient, the whole number of tens. Division between two integers drops the fraction, so 14 / 10 is 1, not 1.4.

Some examples:

Total 7: 7 % 10 is 7 (write 7), and 7 / 10 is 0 (no carry).
Total 10: 10 % 10 is 0 (write 0), and 10 / 10 is 1 (carry 1).
Total 19: 19 % 10 is 9 (write 9), and 19 / 10 is 1 (carry 1).

Because the total never goes above 19, the carry is always 0 or 1.

Building the loop step by step

The core of the solution is one loop. Each pass through the loop handles one column. The loop has to keep going in three cases:

The first list still has a node.
The second list still has a node.
The carry is not zero, so one more digit must be written even though both lists are finished.

In C++ the condition looks like this:

while (a != nullptr || b != nullptr || carry != 0) {

Inside the loop, the steps are:

Start the column total with the carry from the previous column.
If the first list still has a node, add its digit and move that pointer to the next node.
Do the same for the second list.
Add a new node to the end of the result that holds sum % 10.
Set the carry to sum / 10.

The result list starts empty, so the code uses a dummy node, a placeholder node that is not part of the answer. The first real digit is attached to the dummy's next, so the code does not need a special case for the first node. When the loop ends, the answer is dummy.next. The swap lesson later in this module uses the same trick.

Here is the core function on its own:

Node* add_digit_lists(const Node* a, const Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    int carry = 0;
    while (a != nullptr || b != nullptr || carry != 0) {
        int sum = carry;
        if (a != nullptr) {
            sum += a->digit;
            a = a->next;
        }
        if (b != nullptr) {
            sum += b->digit;
            b = b->next;
        }
        tail->next = new Node(sum % 10);
        tail = tail->next;
        carry = sum / 10;
    }
    return dummy.next;
}

The function does not change the input lists. It reads them through const Node* pointers and builds a new list. The caller owns the new list and has to free it.

Reading the loop line by line

Each line does one small job, so it helps to read them one at a time.

int sum = carry; starts the column total with the carry from the column before. On the first pass the carry is 0, because nothing came before the ones column.
if (a != nullptr) checks that the first list still has a node. If it does, sum += a->digit; adds that digit.
a = a->next; moves the pointer to the next node. The parameter a is a copy of the caller's pointer, so this change only affects this function. The caller's list is still whole when the function returns.
tail->next = new Node(sum % 10); creates a node that holds the digit to write, and links it after the last node of the result.
tail = tail->next; moves tail to that new node, so the next pass adds its node after it. This is the same idea as the tail pointer in the basics lesson.
carry = sum / 10; keeps the tens part of the total for the next column.

The stored order is what keeps this simple. If the most significant digit came first, the code would have to reach the end of each list before it could start, or reverse both lists first. Each of those costs an extra walk and more pointer changes. Storing the ones digit first lets one forward walk do the whole job.

The full program

The program below includes the node type, two helpers that convert between text and a digit list, the function above, a free_list function that deletes every node, and a main function that runs five sums. The helpers convert "342" into the list 2 -> 4 -> 3 and back again, so you can read the output as ordinary numbers.

C++ · editable

#include <algorithm>
#include <iostream>
#include <string>
#include <string_view>

struct Node {
    int digit;
    Node* next;
    explicit Node(int d) : digit(d), next(nullptr) {}
};

// Builds a digit list from text such as "342".
// The last character becomes the head, so the list stores the ones digit first.
Node* from_text(std::string_view text) {
    Node dummy(0);
    Node* tail = &dummy;
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        tail->next = new Node(*it - '0');
        tail = tail->next;
    }
    return dummy.next;
}

// Reads the digits back as a normal number, most significant digit first.
std::string to_text(const Node* head) {
    std::string text;
    for (const Node* p = head; p != nullptr; p = p->next) {
        text.push_back(static_cast<char>('0' + p->digit));
    }
    std::reverse(text.begin(), text.end());
    return text;
}

// Shows the digits in the order they are stored, joined by arrows.
std::string list_text(const Node* head) {
    std::string out;
    for (const Node* p = head; p != nullptr; p = p->next) {
        if (!out.empty()) out += " -> ";
        out += std::to_string(p->digit);
    }
    return out;
}

Node* add_digit_lists(const Node* a, const Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    int carry = 0;
    while (a != nullptr || b != nullptr || carry != 0) {
        int sum = carry;
        if (a != nullptr) {
            sum += a->digit;
            a = a->next;
        }
        if (b != nullptr) {
            sum += b->digit;
            b = b->next;
        }
        tail->next = new Node(sum % 10);
        tail = tail->next;
        carry = sum / 10;
    }
    return dummy.next;
}

void free_list(Node* head) {
    while (head != nullptr) {
        Node* next = head->next;
        delete head;
        head = next;
    }
}

void run_case(std::string_view x, std::string_view y) {
    Node* a = from_text(x);
    Node* b = from_text(y);
    Node* sum = add_digit_lists(a, b);
    std::cout << x << " + " << y << " = " << to_text(sum) << "\n";
    std::cout << "  stored as: " << list_text(a) << "  +  " << list_text(b)
              << "  =  " << list_text(sum) << "\n";
    free_list(a);
    free_list(b);
    free_list(sum);
}

int main() {
    run_case("342", "465");
    run_case("99", "1");
    run_case("123", "98765");
    run_case("5", "5");
    run_case("0", "0");
    return 0;
}

Expected output:

342 + 465 = 807
  stored as: 2 -> 4 -> 3  +  5 -> 6 -> 4  =  7 -> 0 -> 8
99 + 1 = 100
  stored as: 9 -> 9  +  1  =  0 -> 0 -> 1
123 + 98765 = 98888
  stored as: 3 -> 2 -> 1  +  5 -> 6 -> 7 -> 8 -> 9  =  8 -> 8 -> 8 -> 8 -> 9
5 + 5 = 10
  stored as: 5  +  5  =  0 -> 1
0 + 0 = 0
  stored as: 0  +  0  =  0

The stored as line shows the list in the order the nodes are stored. The first value is the ones digit. Read the = part of each line and compare it with the number on the left.

Worked examples

Example 1: 342 + 465

Follow the first case in the output. The two lists are 2 -> 4 -> 3 and 5 -> 6 -> 4. Each loop pass handles one column.

Pass 1: carry is 0. The first list gives 2 and the second gives 5. The total is 7. The code writes 7, and the carry becomes 0.
Pass 2: carry is 0. The first list gives 4 and the second gives 6. The total is 10. The code writes 0, and the carry becomes 1.
Pass 3: carry is 1. The first list gives 3 and the second gives 4. The total is 1 + 3 + 4 = 8. The code writes 8, and the carry becomes 0.

Both lists are now finished, and the carry is 0, so the loop stops. The result is 7 -> 0 -> 8, which reads as 807.

Example 2: lists of unequal length

Now take 123 and 98765. The first list has three nodes, and the second has five. The loop keeps going after the first list runs out, and it adds only the digits that are left.

Column 1: 3 + 5 = 8. Write 8, carry 0.
Column 2: 2 + 6 = 8. Write 8, carry 0.
Column 3: 1 + 7 = 8. Write 8, carry 0.
Column 4: the first list has no node left, so the total is just 8. Write 8, carry 0.
Column 5: the first list has no node left, so the total is just 9. Write 9, carry 0.

From column 4 onward the first list is nullptr, so the if (a != nullptr) check skips it. The total is only the digit from the second list plus the carry. The result is 8 -> 8 -> 8 -> 8 -> 9, which reads as 98888.

Notice that the if checks are what make this work. Without them, the code would read from a null pointer. The mistakes section shows what that looks like.

Example 3: a final carry with no digits left

Take 99 + 1. Both sums end in a carry that has nowhere to go in the lists.

Pass 1: 9 + 1 = 10. Write 0, carry 1. The first list moves to its second node, which is also 9. The second list is now finished.
Pass 2: 9 + carry 1 = 10. Write 0, carry 1. Both lists are finished now.
Pass 3: neither list has a node, but the carry is 1, so the loop runs. The total is 1. Write 1, carry 0.

The loop stops because the carry is 0. The result is 0 -> 0 -> 1, which reads as 100. The loop condition with carry != 0 is what makes the third pass happen. This case is the most common place for a bug, so the mistakes section starts with it.

Common mistakes

Forgetting the final carry

If the loop condition has only the two list checks, the code stops too early. Here is that version with the carry check removed from the condition:

while (a != nullptr || b != nullptr) {

Changing only that one line makes the program print a wrong answer. This is the real output from the modified program:

99 + 1 = 00
  stored as: 9 -> 9  +  1  =  0 -> 0

The carry of 1 is dropped, so the answer is 0 instead of 100. The fix is to put carry != 0 back into the condition.

Reading `digit` from a null pointer

Each list can run out at a different time, so each read of ->digit needs a check that the pointer is not nullptr first. If the if (b != nullptr) check is removed, the program reads from a null pointer as soon as the second list runs out. The modified program was built with -fsanitize=address,undefined, which is a compiler option that adds checks for memory and arithmetic errors. Its report looked like this:

bug_null.cpp:55:23: runtime error: member access within null pointer of type 'const struct Node'
AddressSanitizer:DEADLYSIGNAL
==173826==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x5ceb8c602248 bp 0x7ffccb63c100 sp 0x7ffccb63c040 T0)
==173826==The signal is caused by a READ memory access.
==173826==Hint: address points to the zero page.
    #0 0x5ceb8c602248 in add_digit_lists(Node const*, Node const*) bug_null.cpp:55

Read the first line first. It names the type that was null and gives the line number. The process id and addresses change on each run, but the words null pointer and the function name stay the same. A plain build without the sanitizer may only print Segmentation fault and stop.

Forgetting to free the result and the inputs

Each new Node needs one delete. If run_case skips the free_list(a); line, the inputs are never freed. Removing that line and running with the sanitizer gave this report:

Direct leak of 16 byte(s) in 1 object(s) allocated from:
...
SUMMARY: AddressSanitizer: 160 byte(s) leaked in 10 allocation(s).

Each node is 16 bytes on this build, and the report counts 10 nodes from the five cases. The leak is not visible in the normal output, which is why the sanitizer is useful when you practise with lists.

Building the lists in the wrong order

The addition only works if the head holds the ones digit. If you build 342 with the hundreds digit first, the stored list is 3 -> 4 -> 2, and the loop adds 3 and 5 in the first column. The answer is wrong even though the loop is correct. When a list-based number gives strange results, print the stored order first, the way list_text does in the program above.

Practice

Exercise 1: Trace 58 + 67 by hand

Write the two lists in stored order and work through each column. Give the final stored list and the number it means.

Show the answer

Column 1: 8 + 7 = 15. Write 5, carry 1. Column 2: 5 + 6 + 1 = 12. Write 2, carry 1. Both lists are finished and the carry is 1, so write 1. The stored list is 5 -> 2 -> 1, which means 125.

Exercise 2: Add 1 to 999

Use from_text and add_digit_lists to add 1 to 999, then print the stored list and the number.

Show the answer

Node* nines = from_text("999");
Node* one = from_text("1");
Node* result = add_digit_lists(nines, one);
std::cout << list_text(result) << "\n";
std::cout << to_text(result) << "\n";

The stored list is 0 -> 0 -> 0 -> 1, and the number is 1000. The carry runs through all three columns and then creates a fourth digit with no input nodes left.

Exercise 3: Read a stored list

Without running any code, say which number each stored list means: 7 -> 0 -> 8 and 0 -> 0 -> 0 -> 1.

Show the answer

7 -> 0 -> 8 is 807, because the head is the ones digit and the last node is the hundreds digit. 0 -> 0 -> 0 -> 1 is 1000, because the last node is the thousands digit.

Exercise 4: Why the carry check matters for 5 + 5

Explain what happens to 5 + 5 if the loop condition has no carry != 0 part.

Show the answer

Both lists have one node. The first pass adds 5 + 5 = 10, writes 0, and sets the carry to 1. Without the carry check, the loop ends now, and the result is only 0. The 1 is lost. With the check, the loop runs once more, writes 1, and the result is 0 -> 1, which means 10. The program prints 5 + 5 = 10 with the check in place.

Exercise 5: Count the digits in a list

Write a function int digit_count(const Node* head) that returns the number of nodes in a digit list. Then say what it returns for from_text("1000").

Show the answer

int digit_count(const Node* head) {
    int count = 0;
    for (const Node* p = head; p != nullptr; p = p->next) {
        ++count;
    }
    return count;
}

For from_text("1000") it returns 4, because the list has four nodes. This is the same walk the other functions use, with a counter added.

Summary

Storing one digit per node lets a number grow past the limit of any built-in type.
The head holds the ones digit, so addition starts at the head and moves forward one column at a time.
For each column, total % 10 is the digit to write and total / 10 is the carry to pass on.
The loop must keep running while either list has a node or the carry is not zero, which handles unequal lengths and a final carry.
Check for nullptr before reading ->digit, and free every node you create.

Add two numbers stored as digit lists

Why it matters

The idea: school addition on a list

Two arithmetic tools: remainder and quotient

Building the loop step by step

Reading the loop line by line

The full program

Worked examples

Example 1: 342 + 465

Example 2: lists of unequal length

Example 3: a final carry with no digits left

Common mistakes

Forgetting the final carry

Reading digit from a null pointer

Forgetting to free the result and the inputs

Building the lists in the wrong order

Practice

Exercise 1: Trace 58 + 67 by hand

Exercise 2: Add 1 to 999

Exercise 3: Read a stored list

Exercise 4: Why the carry check matters for 5 + 5

Exercise 5: Count the digits in a list

Summary

Stuck? Ask the tutor

Reading `digit` from a null pointer