我想取出并从列表中删除第一个元素。我所看到的,我有两个选择:
第一种方法:
LinkedList<String> servers = new LinkedList<String>();
....
String firstServerName = servers.removeFirst();
第二条本办法
ArrayList<String> servers = new ArrayList<String>();
....
String firstServerName = servers.remove(0);
我有很多我的列表中的元素。
什么是做到这一点的最有效方法。
如果“首先删除”的比较是ArrayList
和LinkedList
类之间的LinkedList
明显胜出。
从链表删除元素收费O(1)
,而这样做的数组(数组列表)成本O(n)
。
请确保你理解的LinkedList和ArrayList的区别。 ArrayList的使用数组实现的。
链表需要一定的时间,以除去的元素。 ArrayList中可能需要线性时间删除第一个元素(以确认我需要检查的实施,这里就不Java专家)。
此外,我认为LinkedList的是在空间方面更有效率。因为ArrayList中不会(且不应)重新大小的阵列的每个元件被去除时,它占用比所需要的更多的空间。
在实际应用中,LinkedList#removeFirst
是更有效,因为它的运行在一个双向链表和去除第一要素的基本构成为只从列表的头部断开链接,并更新下一个元素是第一个:
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
qazxsw POI是通过内部阵列需要换挡所有子序列元件的一个位置移动到左通过复制在子阵列操作:
ArrayList#remove
在另一方面,public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
操作需要遍历整个列表的一半用于检索指定索引处的元素 - 在最坏的情况下。 LinkedList#get
将直接指定索引处访问该元素,因为它的操作过的阵列。
在这里,我的大拇指效率的规则是:
ArrayList#get
)相比,做了很多LinkedList
/ add
的使用remove
;get
/ ArrayList
相比做了很多检索操作的使用add
。除去一个ArrayList的第一个元素是O(n)。对于链表为O(1),所以我也有去。
检查的ArrayList remove
大小的isEmpty,获取,设置迭代器和操作的ListIterator在固定时间内运行。该加载操作在固定的时间运行时,也就是,加入n个元素需要O(n)的时间。其他所有操作都以线性时间运行(粗略地讲)。相比LinkedList实现的常数因子较低。
这家伙居然拿到了OpenJDK源码documentation
使用链表是迄今为止速度更快。
链表
它只是将参考节点,以便第一个消失。
数组列表
与一个数组列表它具有所有元素向后移动一个点,以保持潜在的阵列正确。
正如其他人正确地指出,LinkedList的是比ArrayList的从不是一个很短的列表中的其他任何拆除的第一个元素的更快。
然而,让他们之间的你自己的选择需要考虑操作的完整组合。例如,如果你的工作量确实的索引数以百万计的访问为每个第一元素移除百个元素的列表,ArrayList的将是更好的整体。
我认为,你需要的是一个link(在ArrayDeque
不公平的忽视类)。其java.util
方法执行在O(1)作为用于removeFirst
,但通常示出LinkedList
的更好的空间和时间特性。它实施为一个阵列的圆形队列。
你应该很少使用ArrayList
。我在17年的Java程序员做了一次,现在回想起来后悔。
在LinkedList
除去第一要素的情况下,具有复杂度为O(n)的,所以作为替代,你可以得到第一个元素,而不是删除它只是调用ArrayList的:
List.subList(int fromIndex, int toIndex)
第三条道路。
它是由java.util.Queue中的接口暴露出来。 LinkedList的是这个接口的实现。
队列接口被暴露对E poll()方法,其有效地除去列表(队列)的头部。
在性能方面的poll()方法相当于removeFirst()。实际上它是使用在引擎盖下的removeFirst()方法。