Java数据结构数组列表与链接列表

Question

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

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

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

这个比那个好吗？如果是这样,以什么方式？

Answer 1

在Java中,LinkedList该类实现了该Queue接口.这意味着它可以作为一个队列.如果你使用,.add()你将把东西放在列表的末尾(队列),如果你使用.remove(),你将从列表的头部(队列)中提取东西.

从a中检索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).但是你每次都需要移开头部.