0

我正在运行一个动态编程函数,我在整个过程中携带一个字符串列表。

随着时间的推移,我会在这个列表的末尾添加新的字符串,有时我可能会删除最后一个元素。现在我正在使用一个可变的 ListBuffer,+=用于追加和.trimEnd(1)删除。

一旦我的动态编程过程完成,我需要能够有效地访问该列表/序列/等的每个元素,并且按顺序(我插入的第一个项目将首先被访问,而我插入的最后一个项目将是最后一个访问)。

我也尝试过 ArrayBuffers,但它们似乎都太慢了。我正在尝试加快这个过程,我想知道我是否正在使用具有 O(n) 操作的数据结构,而可能有一些东西需要 O(1) 时间操作。

4

1 回答 1

2

一个简单的单链表将为您描述的附加/丢弃部分提供 O(1)。最坏的情况是,如果您需要在处理之前在最后反转列表,那将是一次支付一次的 O(n) 操作。

请注意,如果您沿着这条路走,在累积阶段,“第一个”和“最后一个”将被颠倒(您将通过获取列表的尾部添加项目并删除第一个项目)。

于 2015-06-17T17:22:21.783 回答