我有一个随机生成的数字列表,并希望将它们存储在一个结构中,然后按照它们生成的顺序将它们从结构中删除。
所以,我需要一个最好先删除的数据结构。
链表和数组列表都删除了 O(1)
这个比那个好吗?如果有,以什么方式?
我有一个随机生成的数字列表,并希望将它们存储在一个结构中,然后按照它们生成的顺序将它们从结构中删除。
所以,我需要一个最好先删除的数据结构。
链表和数组列表都删除了 O(1)
这个比那个好吗?如果有,以什么方式?
在 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)。但是您每次都需要移除头部。