从列表中高效地获取/删除第一个元素的方法是什么？

Question

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

第一种方法：

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

第二种方法

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

我的列表里有很多元素。

• 有没有偏好使用哪一个？
• 上述两者之间的区别是什么？从性能角度来看，它们是否是同一件事情？如果我们有很多元素，这里涉及到的复杂性是什么？

最有效的方法是什么。

- user1950349

---

a) 定义性能。有许多要测量的变量，例如时间、效率、内存使用等等。 b) 编写一些测试代码，使用秒表（类，而非物理）和类似的工具进行基准测试并找出结果。 - D. Ben Knoble

“最有效的方法是什么？” 取决于您的情况。请参见https://dev59.com/Y3RC5IYBdhLWcg3wW_tk。 - Shar1er80

Answer 1

您应该使用LinkedList。

背景：

实际上，LinkedList#removeFirst 更有效率，因为它在双向链表上操作，移除第一个元素基本上只需要将其从列表头部取消链接并更新下一个元素为第一个元素（复杂度O(1)）:

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#remove 操作的是一个内部数组结构，需要通过复制子数组将所有后续元素向左移动一位（时间复杂度为 O(n)）：

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 可以直接访问指定索引处的元素，因为它是在一个数组上操作。

我对于效率的经验法则如下：

• 如果与读取操作相比，您有大量的添加/删除操作（例如： get），则使用 LinkedList；
• 如果您有很多读取操作而不是添加/删除操作，则使用 ArrayList。

- Ben-Hur Langoni Junior

Answer 2

如果比较“删除第一个元素”的内容是ArrayList和LinkedList类之间的话，显然LinkedList胜出。

从链表中删除一个元素的成本是O(1)，而从数组（即ArrayList）中删除则需要O(n)。

- PNS

Answer 3

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

LinkedList删除元素需要恒定时间。 ArrayList可能需要线性时间来删除第一个元素（为确认此点，我需要检查实现，不是Java专家）。

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

- Zlol

---

Java中的ArrayList不是双端的，因此在删除第一个项目时需要移动所有内容。对于大型列表，ArrayList比LinkedList更节省空间，因为LinkedList对于每个项目（值、下一个和上一个）使用3个引用，而ArrayList每个项目只需要一个引用加未使用的空间。 - Raniz

不要忘记包装对象也会占用内存。 - user2982130

@Raniz 感谢您增加了详细信息。仅想澄清一下，我所说的“空间效率更高”是指在从链表中移除元素时，链表会缩小；而对于ArrayList，在删除操作后ArrayList不会重新调整大小。尽管trimToSize()方法可以帮助解决这个问题。 - Zlol

Answer 4

我认为你需要的是一个ArrayDeque（在java.util中不公正地被忽视的类）。它的removeFirst方法与LinkedList一样以O(1)的速度执行，同时通常显示出ArrayList更好的空间和时间特性。它是在数组中实现的循环队列。

你应该非常少使用LinkedList。我作为Java程序员17年来只用过一次，并且事后感到后悔。

- Ole V.V.

---

你也可以使用 List.subList(...)，请查看我的回答：https://dev59.com/zl0a5IYBdhLWcg3wLV8G#46211629。 - Roland

你可以这样做，@Roland。但如果添加和删除同时进行，我无法看出它如何实用。如果列表只填充一次，之后只进行删除操作，那么 subList() 应该是可以的。 - Ole V.V.

Answer 5

List.subList(int fromIndex, int toIndex)

返回此列表中指定的fromIndex（包括）和toIndex（不包括）之间的部分视图。

适用于ArrayList，其中删除第一个元素的复杂度为O(n)。

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

- Roland

Answer 6

使用链表是远比其他方式更快。

链表

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

数组列表

对于数组列表，它必须将所有元素向后移动一个位置，以保持基础数组的正确性。

- J Blaz

Answer 7

删除ArrayList的第一个元素是O(n)。对于链表来说是O(1)，因此我会选择它。

查看ArrayList的文档

大小、isEmpty、get、set、iterator和listIterator操作在常数时间内完成。添加操作以平均常数时间运行，即添加n个元素需要O(n)的时间。所有其他操作都以线性时间运行（粗略地说）。与LinkedList实现相比，常数因子较低。

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

- Cacho Santa

---

O(n)？这要么是笔误，要么就是我的list.remove(0)理解有误。你能请教一下它为什么是O(n)吗？ - Praba

@prabugp 这不是打字错误。 - Cacho Santa

@prabugp 后面的元素必须被移动。 - Sotirios Delimanolis

啊.. 糟糕！谢谢。 - Praba

Answer 8

正如其他人正确指出的那样，除了非常短的列表之外，LinkedList 在删除第一个元素时比 ArrayList 更快。

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

- Patricia Shanahan

Answer 9

第三种方法。

它是通过java.util.Queue接口暴露的。LinkedList是该接口的一种实现。

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

就性能而言，poll()方法与removeFirst()方法相当。实际上，在底层它使用的是removeFirst()方法。

- Alexander Petrov