作为一项可选任务，我正在考虑编写自己的 BigInteger 类实现，我将在其中提供自己的加法、减法、乘法等方法。
这将是任意长的整数，甚至是数百位数。
在对这些数字进行数学运算时，逐个数字并不难，您认为代表我的“BigInteger”的最佳数据结构是什么？
起初我正在考虑使用数组，但后来我想在大的加法或乘法之后我仍然可能会溢出（数组插槽用完）。这是否是使用链表的好案例，因为我可以使用 O(1) 时间复杂度来处理数字？
有没有比链表更适合的其他数据结构？我的数据结构所持有的类型应该是我可以使用的最小整数类型吗？
另外，我应该注意如何存储“进位”变量吗？它本身应该属于我的“BigInteger”类型吗？
查看David R. Hanson的《 C 接口和实现》一书。它有 2 章关于该主题，涵盖了向量结构、字长和您可能遇到的许多其他问题。
它是为 C 编写的，但大部分适用于 C++ 和/或 Java。如果你使用 C++，它会更简单一些，因为你可以使用类似std::vector的东西来为你管理数组分配。
哇，这里有一些……有趣的答案。我建议阅读一本书，而不是尝试整理所有这些相互矛盾的建议。
也就是说，C/C++ 也不适合这项任务。大整数是一种扩展精度数学。大多数 CPU 提供指令以与普通数学相当或相同的速度（每条指令的位数）处理扩展精度数学。当您添加 2^32+2^32 时，答案是 0……但处理器的 ALU 也有一个特殊的进位输出，程序可以读取和使用它。
C++ 无法访问该标志，C 也没有办法。你必须使用汇编程序。
只是为了满足好奇心，您可以使用标准布尔算法来恢复进位等。但是下载现有库会更好。
始终使用可以完成所需工作的最小 int 类型（字节）。链表应该可以很好地工作，因为您不必担心溢出。
如果您使用二叉树（其叶子是整数），您可以通过更简单的分治算法获得链表的所有优点（无限位数等）。在这种情况下，您没有一个单一的基地，而是有许多取决于您工作的水平。
如果这样做，则需要使用 BigInteger 进行进位。您可能会认为它是“整数链表”方法的一个优势，进位始终可以表示为一个整数（这对于任何基数都是正确的，而不仅仅是基数 10，因为大多数答案似乎都假设您应该使用。 ..在任何基础上，进位总是一个数字）
我不妨这么说：当你可以使用 2^30 或 2^31 时，使用 base 10 将是一种可怕的浪费。
访问链表的元素很慢。我认为数组是要走的路，有很多边界检查和运行时数组根据需要调整大小。
澄清：遍历链表和遍历数组都是 O( n ) 操作。但是遍历链表需要在每一步都引用一个指针。仅仅因为两种算法都具有相同的复杂性，并不意味着它们都需要相同的时间来运行。分配和释放链表中的n 个节点的开销也将比单个大小为n的数组的内存管理要重得多，即使该数组必须调整几次。
根据经验，请使用std::vector代替std::list，除非您需要经常在序列中间插入元素。向量往往更快，因为它们是连续存储的，因此受益于更好的空间局部性（现代平台上的主要性能因素）。
确保使用平台自然的元素。如果您想独立于平台，请使用long. 请记住，除非您有一些特殊的编译器内在函数可用，否则您需要一个至少两倍大的类型来执行乘法运算。
我不明白你为什么要让进位成为一个大整数。进位是用于加法的单个位和用于乘法的元素大小。
确保您阅读了 Knuth 的计算机编程艺术，其中在很大程度上描述了与任意精度算术有关的算法。
我会说一个整数数组。
我会说一个 char 的 std::vector （因为它只能保存 0-9）（如果你打算在 BCD 中工作）
如果不是 BCD，则使用 int 向量（你没有说清楚）
链接列表的空间开销要少得多
所有的建议都说“除非你有充分的理由，否则不要使用向量”
Array 确实是天作之合。我认为当你的内存用完时抛出 OverflowException 是可以接受的。老师会看到对细节的关注。
乘法大约使数字加倍，加法最多增加 1。创建一个足够大的数组来存储运算结果很容易。
进位最多是乘法中的一位长数字（9*9 = 1，进位 8）。一个 int 就可以了。
std::vector<bool>或者std::vector<unsigned int>可能是你想要的。您将不得不push_back()或resize()在它们上，因为您需要更多空间来进行乘法运算等。此外，如果您使用两个恭维，请记住 push_back 正确的符号位。