我应该使用什么数据结构来创建自己的"BigInteger"类？

Question

作为一个可选的赋值,我正在考虑编写自己的BigInteger类实现,在那里我将提供自己的加法,减法,乘法等方法.

这将是任意长整数,甚至数百位长.

在对这些数字进行数学计算时,逐位数字并不难,您认为最好的数据结构代表我的"BigInteger"是什么？

起初我正在考虑使用一个数组,但后来我认为在一次大的加法或乘法之后我仍然可能会溢出(用完数组插槽).这是一个使用链表的好例子,因为我可以处理O(1)时间复杂度的数字？

是否有一些其他数据结构甚至比链表更适合？我的数据结构所保存的类型应该是我可用的最小可能整数类型吗？

另外,我应该小心如何存储我的"carry"变量？它本身应该是我的"BigInteger"类型吗？

Answer 1

我会说一个整数数组。