Java 从列表中获取/删除第一个元素的有效方法？

Efficient way to get/remove first element from the list?

提问by user1950349

I want to take out and remove first element from the List. I can see, I have two options:

我想从列表中取出并删除第一个元素。我可以看到，我有两个选择：

First Approach:

第一种方法：

LinkedList<String> servers = new LinkedList<String>();
....
String firstServerName = servers.removeFirst();

Second Approach

第二种方法

ArrayList<String> servers = new ArrayList<String>();
....
String firstServerName = servers.remove(0);

I have lot of elements in my list.

我的列表中有很多元素。

• Is there any preference which one we should use?
• And what is the difference between the above two? Are they technically same thing in terms of performance? What is the complexity involve here if we have lot of elements?

• 我们应该使用哪一种？
• 而以上两者有什么区别呢？在性能方面，它们在技术上是否相同？如果我们有很多元素，这里涉及的复杂性是什么？

What is the most efficient way to do this.

什么是最有效的方法来做到这一点。

回答by J Blaz

Using a linked list is by far faster.

使用链表要快得多。

LinkedList

链表

It will just reference the nodes so the first one disappears.

它只会引用节点，因此第一个节点会消失。

ArrayList

数组列表

With an Array List it has to move all elements back one spot to keep the underlying array proper.

对于数组列表，它必须将所有元素移回一个位置以保持底层数组正确。

回答by Cacho Santa

Removing the first element of an ArrayList is O(n). For the linked list is O(1), so I'll go with that.

删除 ArrayList 的第一个元素是 O(n)。因为链表是 O(1)，所以我会这样做。

Check the ArrayList documentation

检查 ArrayList文档

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。add 操作在分摊常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都在线性时间内运行（粗略地说）。与 LinkedList 实现相比，常量因子较低。

This guys actually got the OpenJDK source link

这家伙实际上得到了 OpenJDK 源代码链接

回答by PNS

If the comparison for "remove first" is between the ArrayListand the LinkedListclasses, the LinkedListwins clearly.

如果“先删除”的比较是在类ArrayList和LinkedList类之间，则LinkedList明显获胜。

Removing an element from a linked list costs O(1), while doing so for an array (array list) costs O(n).

从链表中删除元素成本O(1)，同时为数组（数组列表）成本这样做O(n)。

回答by Zlol

Make sure you understand the difference between LinkedList and ArrayList. ArrayList is implemented using Array.

确保您了解 LinkedList 和 ArrayList 之间的区别。ArrayList 是使用 Array 实现的。

LinkedList takes constant time to remove an element. ArrayList might take linear time to remove the first element (to confirm I need to check the implementation, not java expert here).

LinkedList 需要恒定的时间来删除元素。ArrayList 可能需要线性时间来删除第一个元素（确认我需要检查实现，而不是这里的 java 专家）。

Also I think LinkedList is more efficient in terms of space. Because ArrayList would not (and should not) re-size the array every time an element is removed, it takes up more space than needed.

另外我认为 LinkedList 在空间方面更有效。因为 ArrayList 不会（也不应该）在每次删除元素时重新调整数组的大小，所以它占用的空间比需要的要多。

回答by Patricia Shanahan

As others have rightly pointed out, LinkedList is faster than ArrayList for removal of the first element from anything other than a very short list.

正如其他人正确指出的那样，LinkedList 比 ArrayList 更快，可以从非常短的列表以外的任何内容中删除第一个元素。

However, to make your choice between them you need to consider the complete mix of operations. For example, if your workload does millions of indexed accesses to a hundred element list for each first element removal, ArrayList will be better overall.

但是，要在它们之间做出选择，您需要考虑完整的操作组合。例如，如果您的工作负载在每次删除第一个元素时对一百个元素列表进行数百万次索引访问，则 ArrayList 总体上会更好。

回答by Ben-Hur Langoni Junior

In practical terms, LinkedList#removeFirstis more efficient since it's operating over a doubly-linked list and the removal of first element basically consist in only unlinking it from the head of the list and update the next element to be the first one:

实际上，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;
}

ArrayList#removeis operating over an internal array which requires shiftting all subsequents elements one position to the left by copying over the subarray:

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;
}

On the other hand, LinkedList#getoperation requires traversing half of the entire list for retrieving an element at a specified index - in worst case scenario. ArrayList#getwould directly access the element at the specified index since it's operating over an array.

另一方面，LinkedList#get操作需要遍历整个列表的一半以检索指定索引处的元素 - 在最坏的情况下。ArrayList#get将直接访问指定索引处的元素，因为它对数组进行操作。

My rule of thumbs for efficiency here would be:

我在这里提高效率的经验法则是：

• Use LinkedListif you do a lot of add/removein comparison with retrieval operations (e.g.: get);
• Use ArrayListif you do a lot of retrieval operations in comparison with add/remove.

• 使用LinkedList，如果你做了很多的add/remove在检索操作比较（例如：get）;
• 使用ArrayList，如果你使用比较做了很多检索操作中add/ remove。

回答by Alexandar Petrov

Third Aproach.

第三个方法。

It is exposed by the java.util.Queue interface. LinkedList is an implementation of this interface.

它由 java.util.Queue 接口公开。LinkedList 是这个接口的一个实现。

The Queue interface is exposing the E poll() method which effectively removes the head of the List (Queue).

Queue 接口公开了 E poll() 方法，该方法有效地删除了列表（队列）的头部。

In terms of performance the poll() method is comparable to removeFirst(). Actually it is using under the hood the removeFirst() method.

在性能方面， poll() 方法可与 removeFirst() 相媲美。实际上它在幕后使用 removeFirst() 方法。

回答by Ole V.V.

I think that what you need is an ArrayDeque(an unfairly overlooked class in java.util). Its removeFirstmethod performs in O(1) as for LinkedList, while it generally shows the better space and time characteristics of ArrayList. It's implemented as a circular queue in an array.

我认为您需要的是一个ArrayDeque（在 中被不公平地忽视的类java.util）。它的removeFirst方法对于 来说在 O(1) 中执行LinkedList，而它通常表现出更好的空间和时间特性ArrayList。它被实现为数组中的循环队列。

You should very rarely use LinkedList. I did once in my 17 years as Java programmer and regretted in retrospect.

您应该很少使用LinkedList. 我在 17 年的 Java 程序员生涯中做过一次，现在回想起来很后悔。

回答by Roland

In case of ArrayListremoving the first element has complexity O(n), so as an alternative you can get the first element and instead of removing it just call List.subList(int fromIndex, int toIndex):

如果ArrayList删除第一个元素的复杂度为 O(n)，因此作为替代，您可以获得第一个元素，而不是删除它，只需调用 List.subList(int fromIndex, int toIndex)：

final String firstServerName = servers.get(0);
servers = servers.subList(1, servers.size());