-2

我有一个随机生成的数字列表,并希望将它们存储在一个结构中,然后按照它们生成的顺序将它们从结构中删除。

所以,我需要一个最好先删除的数据结构。

链表和数组列表都删除了 O(1)

这个比那个好吗?如果有,以什么方式?

4

1 回答 1

7

在 Java 中,LinkedList类实现了Queue接口。这意味着它作为一个队列工作。如果你使用.add(),你会把东西放在列表的末尾(队列),如果你使用.remove(),你会把东西从列表的头(队列)拉出来。

从 an 中检索ArrayList是 O(1),但删除不是。考虑以下:

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(1);
al.add(2);
al.add(3);

您的清单al现在是{1, 2, 3}

你现在做:al.remove(0)

之后,al就是{2, 3}。但要做到这一点,一旦你删除了列表的头部,头部之后的所有其他对象都需要向下移动一个单位。所以实际上是 O(n)。如果要移除尾部,则移除时间仅为 O(1)。但是您每次都需要移除头部。

于 2012-12-09T11:38:38.580 回答