出于纯粹的兴趣，我正在尝试设计一种可以容纳任意大整数的类型。我想支持四种基本操作[+, -, *, /]并优化这些操作的速度。
我在考虑某种双向链表和一个位标志来指示正值或负值。但我不太确定如何添加，例如，添加到大量不同尺寸。我是否应该走到两个数字的最后一个元素，然后返回（使用第二个反向指针指向前一个元素）。
123456789 //一个大数 + 123 //另一个不同大小的大数
如果我可以拥有任意大的内存，那么这个任务的最佳数据结构是什么？
对于算术运算的最坏情况复杂性，我将不胜感激。谢谢！
在这种情况下，通常人们会选择一个数组/向量，也许是 little-endian（最低有效字优先）。如果您实现就地操作，在增长数组时使用一个常数因子，那么重新分配的摊销复杂度仍然是 O(1)。
所有操作都应该在 O(n) 运行时间内可行，其中 n 是输入的大小。编辑：不，当然，乘法和除法需要更多，这个答案说它至少是 O(N log N)。
只是出于好奇：为什么要重新实现轮子？在这里找到一个 Java 实现。C# 也有一个 .NET 4.0。虽然自己实现它可能是一个很好的练习（我记得自己做过一次），但如果您只需要该功能，那么它已经存在于许多计算环境中。