java - Java 数据结构数组列表与链表

Question

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

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

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

这个比那个好吗？如果有，以什么方式？

score 7 · Accepted Answer

在 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)。但是您每次都需要移除头部。

1 回答 1